2023/09/12 by Pu Gao, Gao, Pu, Hidde Koerts +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2309.05881
openalex publication_date 2023/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the semi-random graph process, and a variant process recently suggested by Nick Wormald. We show that these two processes are asymptotically equally fast in constructing a semi-random graph G that has property \mathcal P, for the following examples of \mathcal P: - \mathcal P is the set of graphs containing a d-degenerate subgraph, where d≥ 1 is fixed; - \mathcal P is the set of k-connected graphs, where k≥ 1 is fixed. In particular, our result of the k-connectedness above settles the open case k=2 of the original semi-random graph process. We also prove that there exist properties \mathcal P where the two semi-random graph processes do not construct a graph in \mathcal P asymptotically equally fast. We further propose some conjectures on \mathcal P for which the two processes perform differently.