Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process. Issue 4 (27th September 2020)

• Record Type: Journal Article
• Authors: Ben‐Eliezer, Omri; Gishboliner, Lior; Hefetz, Dan; Krivelevich, Michael
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 892
• Page End: 919
• Publication Date: 2020-09-27
• Subjects: embedding spanning graphs -- semi‐random graph process; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20963
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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.