Partitioning random graphs into monochromatic components (Q510329): Difference between revisions

Summary: \textit{P. Erdős} et al. [J. Comb. Theory, Ser. B 51, No. 1, 90--95 (1991; Zbl 0766.05062)] conjectured that every \(r\)-colored complete graph can be partitioned into at most \(r-1\) monochromatic components; this is a strengthening of a conjecture of \textit{L. Lovász} [Mat. Lapok 26, 209--264 (1977; Zbl 0397.05040)] and Ryser (see [\textit{. J. R. Henderson}, Permutation decompositions of (0, 1)-matrices and decomposition transversals. Pasadena, CA: California Institute of Technology (PhD Thesis) (1970)]) in which the components are only required to form a cover. An important partial result of \textit{P. E. Haxell} and \textit{Y. Kohayakawa} [J. Comb. Theory, Ser. B 68, No. 2, 218--222 (1996; Zbl 0861.05018)] shows that a partition into \(r\) monochromatic components is possible for sufficiently large \(r\)-colored complete graphs. We start by extending P. E. Haxell and Y. Kohayakawa's result [loc. cit.] to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if \(p\geq \left(\frac{27\log n}{n}\right)^{1/3}\), then a.a.s. in every 2-coloring of \(G(n,p)\) there exists a partition into two monochromatic components, and for \(r\geq 2\) if \(p\ll \left(\frac{r\log n}{n}\right)^{1/r}\), then a.a.s. there exists an \(r\)-coloring of \(G(n,p)\) such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of \textit{A. Gyárfás} [``Partition covers and blocking sets in hypergraphs'', MTA SZTAKI Tanulmányok 71 (1977)] about large monochromatic components in \(r\)-colored complete graphs. We show that if \(p=\frac{\omega(1)}{n}\), then a.a.s. in every \(r\)-coloring of \(G(n,p)\) there exists a monochromatic component of order at least \((1-o(1))\frac{n}{r-1}\).