Premium
Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
Author(s) -
BenEliezer Omri,
Gishboliner Lior,
Hefetz Dan,
Krivelevich Michael
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20963
Subject(s) - combinatorics , mathematics , discrete mathematics , multiplicative function , bounded function , random graph , vertex (graph theory) , degree (music) , regular graph , graph , line graph , graph power , mathematical analysis , physics , acoustics
In this paper, we study the following recently proposed semi‐random graph process: starting with an empty graph on n vertices, the process proceeds in rounds, where in each round we are given a uniformly random vertex v , and must immediately (in an online manner) add to our graph an edge incident with v . The end goal is to make the constructed graph satisfy some predetermined monotone graph property. Alon asked whether every given bounded‐degree spanning graph can be constructed with high probability in O ( n ) rounds. We answer this question positively in a strong sense, showing that any n ‐vertex graph with maximum degree Δ can be constructed with high probability in ( 3 Δ / 2 + o ( Δ ) ) n rounds. This is tight up to a multiplicative factor of 3 + o Δ ( 1 ) . We also obtain tight bounds for the number of rounds necessary to embed bounded‐degree spanning trees, and consider a nonadaptive variant of this setting.