Covering random graphs with monochromatic trees

DOI10.1002/RSA.21120MaRDI QIDQ6074874zbMATH OpenOpenAlexFDO

Authors Domagoj Bradač, Matija Bucić

Publication date 19 October 2023

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(5)

• Large monochromatic components in colorings of complete hypergraphs
• 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

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)