The jump of the clique chromatic number of random graphs
The jump of the clique chromatic number of random graphs
复制标题
随机图的团色数的跳跃
DOI：
10.1002/rsa.21128
复制
发表时间：
2023
影响因子：
1
通讯作者：
Warnke, Lutz
中科院分区：
文献类型：
--
作者：
Lichev, Lyuben;Mitsche, Dieter;Warnke, Lutz
图的团色数是顶点着色的最小色数，因此没有最大团是单色的。2016年，McDiarmid， Mitsche和Prałat注意到，当我们将边缘概率p $$ p $$增加no(1) $$ {n}^{o(1)} $$时，随机图Gn的团色数p $$ {G}_{n,p} $$在p≈n−1/2 $$ p\approx {n}^{-1/2} $$附近变化nΩ(1) $$ {n}^{\Omega (1)} $$，但将这种令人惊讶的“跳跃”现象的细节保留为一个开放的问题。我们解决了这个问题，即解决了随机图Gn，p $$ {G}_{n,p} $$在边缘概率p≈n−1/2 $$ p\approx {n}^{-1/2} $$周围团色数的多项式“跳跃”的性质。我们的证明使用了近似和浓度参数的混合，这使我们能够(i)超越以前工作中使用的Janson不等式，（ii）确定Gn，p $$ {G}_{n,p} $$的团色数，直至任何边概率p $$ p $$的对数因子。
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 McDiarmid, Mitsche and Prałat noted that around p≈n−1/2$$ p\approx {n}^{-1/2} $$ the clique chromatic number of the random graph Gn,p$$ {G}_{n,p} $$ changes by nΩ(1)$$ {n}^{\Omega (1)} $$ when we increase the edge‐probability p$$ p $$ by no(1)$$ {n}^{o(1)} $$, but left the details of this surprising “jump” phenomenon as an open problem. We settle this problem, that is, resolve the nature of this polynomial “jump” of the clique chromatic number of the random graph Gn,p$$ {G}_{n,p} $$ around edge‐probability p≈n−1/2$$ p\approx {n}^{-1/2} $$. Our proof uses a mix of approximation and concentration arguments, which enables us to (i) go beyond Janson's inequality used in previous work and (ii) determine the clique chromatic number of Gn,p$$ {G}_{n,p} $$ up to logarithmic factors for any edge‐probability p$$ p $$.
登录
查看更多内容
影响因子：
0.7
作者：
G. Joret;Piotr Micek;B. Reed;M. Smid
通讯作者：
M. Smid
恒星的上尾界
DOI：
10.37236/8493
发表时间：
2020
期刊：
The Electronic Journal of Combinatorics
影响因子：
--
作者：
Šileikis, Matas;Warnke, Lutz
通讯作者：
Warnke, Lutz
关于上尾估计中缺失的日志
DOI：
10.1016/j.jctb.2019.05.003
发表时间：
2019
期刊：
Series B
影响因子：
--
作者：
Warnke, Lutz
通讯作者：
Warnke, Lutz
通过修改限制拉姆齐比赛
影响因子：
0.9
作者：
Guo, He;Warnke, Lutz
通讯作者：
Warnke, Lutz
无 K4 进程何时停止？
影响因子：
1
作者：
L. Warnke
通讯作者：
L. Warnke