Covering random graphs with monochromatic trees

DOI10.1002/RSA.21120zbMATH Open1525.05153arXiv2109.02569OpenAlexW4308750680MaRDI QIDQ6074874FDOQ6074874

Authors: Domagoj Bradač, Matija Bucić 

Publication date: 19 October 2023

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Given an $r$-edge-coloured complete graph $K_n$, how many monochromatic connected components does one need in order to cover its vertex set? This natural question is a well-known essentially equivalent formulation of the classical Ryser's conjecture which, despite a lot of attention over the last 50 years, still remains open. A number of recent papers consider a sparse random analogue of this question, asking for the minimum number of monochromatic components needed to cover the vertex set of an $r$-edge-coloured random graph $mathcalG(n,p)$. Recently, Buci'{c}, Kor'{a}ndi and Sudakov established a connection between this problem and a certain Helly-type local to global question for hypergraphs raised about 30 years ago by ErdH{o}s, Hajnal and Tuza. We identify a modified version of the hypergraph problem which controls the answer to the problem of covering random graphs with monochromatic components more precisely. To showcase the power of our approach, we essentially resolve the $3$-colour case by showing that $(logn/n{)}^{1/4}$ is a threshold at which point three monochromatic components are needed to cover all vertices of a $3$-edge-coloured random graph, answering a question posed by Kohayakawa, Mendonc{c}a, Mota and Sch"ulke. Our approach also allows us to determine the answer in the general $r$-edge coloured instance of the problem, up to lower order terms, around the point when it first becomes bounded, answering a question of Buci'c, Kor'andi and Sudakov.

Full work available at URL: https://arxiv.org/abs/2109.02569

Recommendations

• Covering 3-edge-colored random graphs with monochromatic trees
• Monochromatic cycle covers in random graphs
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Vertex coverings by monochromatic cycles and trees
• Monochromatic coverings and tree Ramsey numbers
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs

zbMATH Keywords

thresholdshypergraphsrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Vertex covers by monochromatic pieces -- a survey of results and problems
• On generalized graphs
• Title not available (Why is that?)
• Monochromatic cycle partitions in random graphs
• Helly property in finite set systems
• Title not available (Why is that?)
• Partitioning random graphs into monochromatic components
• Transversals in uniform hypergraphs with property \((p,2)\)
• Local constraints ensuring small representing sets
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Monochromatic cycle covers in random graphs
• Small transversals in uniform hypergraphs
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Transversals in uniform hypergraphs with property (7, 2)
• Covering 3-edge-colored random graphs with monochromatic trees

Cited In (5)

• Monochromatic cycle covers in random graphs
• Vertex coverings by monochromatic cycles and trees
• Covering 3-coloured random graphs with monochromatic trees
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• Large monochromatic components in colorings of complete hypergraphs

This page was built for publication: Covering random graphs with monochromatic trees

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