Semi-random graph process

DOI10.1002/RSA.20887MaRDI QIDQ5113951zbMATH OpenOpenAlexFDO

Authors Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg, Clara Shikhelman, Miloš Stojaković, O. Parczyk

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02259

zbMATH Keywords

random graphsgraph processesone-player games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on $n$ vertices. In every round of the process, one vertex $v$ of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to $v$. For various natural monotone increasing graph properties $P$, we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies $P$. Along the way, we show that the process is general enough to approximate (using suitable strategies) several well-studied random graph models.

Recommendations

• Semi-random process without replacement
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Hamilton cycles in the semi-random graph process
• Perfect matchings in the semirandom graph process

Cited in

(10)

• Power of \(k\) choices in the semi-random graph process
• Semi-random process without replacement
• Sharp thresholds in adaptive random graph processes
• Subgraph games in the semi-random graph process and its generalization to hypergraphs
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Cliques, chromatic number, and independent sets in the semi-random process
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Hamilton cycles in the semi-random graph process
• Perfect matchings in the semirandom graph process
• On the power of choice for Boolean functions

This page was built for publication: Semi-random graph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113951)