preprint · arXiv (Cornell University) · 2022
The semi-random tree process
Cited by 3Open access
Abstract
The online semi-random graph process is a one-player game which starts with the empty graph on $n$ vertices. At every round, a player (called Builder) is presented with a vertex $v$ chosen uniformly at random and independently from previous rounds, and constructs an edge of their choice that is incident to $v$. Inspired by recent advances on the semi-random graph process, we define a family of generalised online semi-random models. We analyse a particular instance that shares similar features with the original semi-random graph process and determine the hitting times of the classical graph properties minimum degree $k$, $k$-connectivity, containment of a perfect matching, a Hamiltonian cycle and an $H$-factor for a fixed graph $H$ possessing an additional tree-like property. Along the way, we derive a few consequences of the famous Aldous-Broder algorithm that may be of independent interest.
Cite this paper
Burova, S., & Lichev, L. (2022). The semi-random tree process. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2204.07376
Burova, Sofiya, and Lyuben Lichev. “The semi-random tree process.” arXiv (Cornell University), 2022, https://doi.org/10.48550/arxiv.2204.07376.
Burova, Sofiya, and Lyuben Lichev. 2022. “The semi-random tree process.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2204.07376.
Burova, S. and Lichev, L. (2022) ‘The semi-random tree process’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2204.07376.
@misc{burova2022semi,
title = {{The semi-random tree process}},
author = {Burova, Sofiya and Lichev, Lyuben},
journal = {arXiv (Cornell University)},
year = {2022},
doi = {10.48550/arxiv.2204.07376}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.