Partitioning random graphs into monochromatic components

MaRDI QIDQ510329zbMATH OpenFDO

Authors Deepak Bal, Louis DeBiasio

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.09168, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p18

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Ramsey theoryrandom graphsRyser's conjecture

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Abstract: ErdH{o}s, Gy'arf'as, and Pyber (1991) 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 Lov'asz (1975) in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa (1995) shows that a partition into $r$ monochromatic components is possible for sufficiently large $r$-colored complete graphs. We start by extending Haxell and Kohayakawa's result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if $pgeleft(frac27lognnight{)}^{1/3}$, then a.a.s. in every $2$-coloring of $G(n,p)$ there exists a partition into two monochromatic components, and for $rgeq2$ if $pllleft(fracrlognnight{)}^{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 Gy'arf'as (1977) about large monochromatic components in $r$-colored complete graphs. We show that if $p=fracomega(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))fracnr-1$.

Review text

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}\).

Recommendations

• Monochromatic cycle partitions in random graphs
• Partitioning by monochromatic trees
• Monochromatic cycle covers in random graphs
• Large monochromatic components in multicolored bipartite graphs
• Bounded monochromatic components for random graphs

Cites work

• An improved bound for the monochromatic cycle partition number
• Calculating Ramsey numbers by partitioning colored graphs
• Coloring the edges of a random graph without a monochromatic giant component
• Combinatorial theorems relative to a random set
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Generalizing the Ramsey problem through diameter
• Highly connected monochromatic subgraphs of multicolored graphs
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• Introduction to Random Graphs
• Large monochromatic components in edge colorings of graphs: A survey
• Local connectivity of a random graph
• Maximum degree and fractional matchings in uniform hypergraphs
• Monochromatic cycle partitions of graphs with large minimum degree
• Monochromatic Paths in Graphs
• Partition of graphs and hypergraphs into monochromatic connected parts
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Partitioning by monochromatic trees
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Path Ramsey number for random graphs
• Ramsey games with giants
• Ryser's conjecture for tripartite 3-graphs
• Some Ramsey-Turán type problems and related questions
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Threshold Functions for Ramsey Properties
• Vertex coverings by monochromatic cycles and trees

Cited in

(18)

• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Vertex covering with monochromatic pieces of few colours
• Bounded monochromatic components for random graphs
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Generalizations and strengthenings of Ryser's conjecture
• Monochromatic partitions in local edge colorings
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Monochromatic cycle partitions in random graphs
• Covering 3-edge-colored random graphs with monochromatic trees
• Coloring the edges of a random graph without a monochromatic giant component
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Covering random graphs with monochromatic trees
• Large monochromatic components in colorings of complete hypergraphs
• Covering 3-coloured random graphs with monochromatic trees
• Large monochromatic components in expansive hypergraphs
• The power of many colours
• Partitioning problems via random processes
• Monochromatic partitions in 2-edge-coloured bipartite graphs

This page was built for publication: Partitioning random graphs into monochromatic components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510329)