Semi-random graph process

DOI10.1002/RSA.20887zbMATH Open1442.05203arXiv1805.02259OpenAlexW2981917538MaRDI QIDQ5113951FDOQ5113951

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)

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.

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

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

zbMATH Keywords

random graphsgraph processesone-player games

Mathematics Subject Classification ID

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

Cited In (10)

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

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)