Lehel's conjecture states that every 2-edge-colouring of K_n admits a partition of its vertex set into two monochromatic cycles. It was proven for sufficiently large n by {\L}uczak, R\"odl, and Szemer\'edi in 1998, later improved by Allen in 2008, and fully resolved by Bessy and Thomass\'e in 2010. In this paper, we consider a rainbow analogue of Lehel's conjecture in the setting of properly edge-coloured complete graphs. We prove that, for sufficiently large n, every properly edge-coloured Kn admits a partition of its vertex set into two vertex-disjoint rainbow cycles
Pedro Araújo, Xiao-Chuan Liu, Taísa L. Martins et al.· 0 citations
The celebrated result of Johansson, Kahn and Vu determined the threshold order for clique factors in random graphs, and subsequent work identified the sharp threshold and the corresponding hitting-time phenomenon. In this paper we study the probability that there is no $K_r$-factor above the threshold and, more generally, the probability that the largest $K_r$-matching covers less than $n-s$ vertices of $G(n,p)$. For every fixed $r\ge3$, throughout the range $$n^{-2/r}(\log n)^{1/\binom r2}\ll p\ll n^{-2/(r+1)},\qquad n-s\in r\mathbb Z,\qquad s=o(n),$$ we prove $$\mathbb P\bigl(\phi_r^s(G(n,p))=0\bigr)=\exp\left(-\Theta_r\!\left((s+1)\frac{\mu_r(n,p)}n\right)\right),$$ where $\phi_r^s(G)$ is the number of $K_r$-matchings covering exactly $n-s$ vertices and $\mu_r(n,p):=\binom nrp^{\binom r2}$. The lower bound is given by $s+1$ vertices which lie in no copy of $K_r$. For the upper bound we develop an iterable one-root version of the Johansson--Kahn--Vu method. As a structural consequence, we show that the remainder of $G(n,p)$ outside every maximal $K_r$-matching has an almost-perfect $K_{r-1}$-matching throughout the sparse clique window. Independently, we prove a central limit theorem for the maximum $K_r$-matching number. Combining these inputs and a structural theorem for $r=2$ from our earlier work, we prove a central limit theorem for the chromatic number of very dense random graphs: for every $r\ge2$ and $n^{-2/r}(\log n)^{1/\binom r2}\ll p\ll n^{-2/(r+1)},$ $$\frac{\chi(G(n,1-p))-\mathbb E\chi(G(n,1-p))}{\sqrt{\mu_{r+1}(n,p)}/r}\xrightarrow{\mathrm d}\mathcal N(0,1),\qquad\operatorname{Var}\bigl(\chi(G(n,1-p))\bigr) \sim\frac{\mu_{r+1}(n,p)}{r^2}.$$ This settles the Surya--Warnke conjecture throughout the interior of every clique window with $r\ge2$, strengthening its concentration prediction to a Gaussian limit with asymptotically exact variance.
Zhi-Fei Yan· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
