TY - JOUR

T1 - Covering random graphs with monochromatic trees

AU - Bradač, Domagoj

AU - Bucić, Matija

N1 - Funding Information:
Domagoj Bradač's research was supported in part by SNSF Grant 200021_196965.
Publisher Copyright:
© 2022 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.

PY - 2023/5

Y1 - 2023/5

N2 - Given an (Formula presented.) -edge-colored complete graph (Formula presented.), 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 (Formula presented.) -edge-colored random graph (Formula presented.). Recently, Bucić, Korá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 Erdő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-color case by showing that (Formula presented.) is a threshold at which point three monochromatic components are needed to cover all vertices of a 3-edge-colored random graph, answering a question posed by Kohayakawa, Mendonça, Mota, and Schülke. Our approach also allows us to determine the answer in the general (Formula presented.) -edge colored instance of the problem, up to lower order terms, around the point when it first becomes bounded, answering a question of Bucić, Korándi, and Sudakov.

AB - Given an (Formula presented.) -edge-colored complete graph (Formula presented.), 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 (Formula presented.) -edge-colored random graph (Formula presented.). Recently, Bucić, Korá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 Erdő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-color case by showing that (Formula presented.) is a threshold at which point three monochromatic components are needed to cover all vertices of a 3-edge-colored random graph, answering a question posed by Kohayakawa, Mendonça, Mota, and Schülke. Our approach also allows us to determine the answer in the general (Formula presented.) -edge colored instance of the problem, up to lower order terms, around the point when it first becomes bounded, answering a question of Bucić, Korándi, and Sudakov.

KW - hypergraphs

KW - random graphs

KW - thresholds

UR - http://www.scopus.com/inward/record.url?scp=85141645208&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85141645208&partnerID=8YFLogxK

U2 - 10.1002/rsa.21120

DO - 10.1002/rsa.21120

M3 - Article

AN - SCOPUS:85141645208

SN - 1042-9832

VL - 62

SP - 545

EP - 563

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3

ER -