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 Pralat noted that around p \approx n^{-1/2} the clique chromatic number of the random graph G_{n,p} changes by n^{\Omega(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an open problem. We settle this problem, i.e., resolve the nature of this polynomial `jump' of the clique chromatic number of the random graph G_{n,p} around edge-probability 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 G_{n,p} up to logarithmic factors for any edge-probability p.
翻译：图形的分色色数是顶端颜色中最小的颜色数, 因而没有最大分色是单色的。 2016年, McDiarmid、 Mitsche 和 Pralat 指出, 随机图形 G ⁇ n, p} 通过 n ⁇ Omega (1)} 来增加边际概率, 但将这个惊人现象的细节留作开放的问题。 我们解决了这个问题, 也就是说, 解决了随机图形 G ⁇ n 、 p} 边缘- 概率 p\ pprox n ⁇ -1/2} 的多元色数的“ 跳跃 ” 性质。 我们的证据使用了近似和集中参数的组合, 使我们能够 (i) 超越先前工作中使用的 Janson 的不平等性, 并且 (ii) 确定 G ⁇ n 、 p} 至任何边际概率的对数的对数。
相关内容
微信扫码咨询专知VIP会员