Metraipolis › archive › dc_9c6fb3bad166

Triangle-Saturated Graphs in the Semi-Random Graph Process — arXiv:2608.14687

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.14687
License (as archived)
CC0-1.0
Archived
2026-10-18T20:25:34.534Z
SHA-256 of the archived text
00f543bbe06070e85b93fa22168bede72bf71e3d6ed47c86b23d58f1b7a27891
Stable URL of this page
https://metraipolis.com/documento/dc_9c6fb3bad166

How to cite

Triangle-Saturated Graphs in the Semi-Random Graph Process — arXiv:2608.14687 — arXiv (en), https://arxiv.org/abs/2608.14687 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9c6fb3bad166 (Metraipolis archive dc_9c6fb3bad166, sha256 00f543bbe06070e85b93fa22168bede72bf71e3d6ed47c86b23d58f1b7a27891)
BibTeX
@misc{dc9c6fb3bad166,
  title = {Triangle-Saturated Graphs in the Semi-Random Graph Process — arXiv:2608.14687},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.14687},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9c6fb3bad166; sha256 00f543bbe06070e85b93fa22168bede72bf71e3d6ed47c86b23d58f1b7a27891},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.14687. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the algorithm independently and uniformly at random. The algorithm then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. We also consider the offline version of the process in which the algorithm is given the entire sequence of random vertex choices before the selection takes place. For a given graph property, the objective of the algorithm is to force the graph to satisfy this property asymptotically almost surely in as few rounds as possible. In this paper, we focus on the property of being triangle-saturated and establish upper and lower bounds on the number of rounds required to construct a triangle-saturated graph in both the online and offline versions of the process.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in math.PR).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2608.14687 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T19:45:36.390Z dalla pagina https://arxiv.org/catchup/math.PR/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).