Sharp thresholds in adaptive random graph processes

DOI10.1002/RSA.21197MaRDI QIDQ6201040zbMATH OpenFDO

Authors Calum MacRury

Publication date 25 March 2024

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

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

zbMATH Keywords

random graph processessharp thresholdsonline decision-making

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: Suppose that $K_n$ is the complete graph on vertex set $[n]$, and $D$ is a distribution on subsets of its edges. The $mathcalD$-adaptive random graph process (or $mathcalD$-process) is a single player game in which the player is initially presented the empty graph on $[n]$. In each step, a subset of edges of $K_n$, say $X$, is independently sampled from $mathcalD$ and presented to the player. The player then adaptively selects precisely one edge $e$ from $X$, and adds $e$ to its current graph. For a fixed (edge) monotone graph property, the objective of the player is to force the graph to satisfy the property in as few steps as possible. Through appropriate choices of $mathcalD$, the $mathcalD$-process generalizes well-studied adaptive processes, such as the Achlioptas process and the semi-random graph process. We prove a theorem which gives a sufficient condition for the existence of a sharp threshold for the property $mathcalP$ in the $mathcalD$-process. We apply our theorem to the semi-random graph process and prove the existence of a sharp threshold when $mathcalP$ corresponds to being Hamiltonian or to containing a perfect matching. These are the first results for the semi-random graph process which show the existence of a sharp threshold when $mathcalP$ corresponds to containing a extit{sparse} spanning graph. Using a separate analytic argument, we show that each sharp threshold is of the form $C_{mathcalP}n$ for some fixed constant $C_{mathcalP}>0$. This answers two of the open problems proposed by Ben-Eliezer et al. (SODA 2020) in the affirmative. Unlike similar results which establish sharp thresholds for certain distributions and properties, we establish the existence of sharp thresholds without explicitly identifying asymptotically optimal strategies.

Recommendations

• Power of \(k\) choices in the semi-random graph process
• Subgraph games in the semi-random graph process and its generalization to hypergraphs
• Hamilton cycles in the semi-random graph process
• Perfect matchings in the semirandom graph process
• Semi-random process without replacement

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3073237 (Why is no real title available?)
• Avoiding a giant component
• Concentration Inequalities and Martingale Inequalities: A Survey
• Hamilton cycles in the semi-random graph process
• Hamiltonicity thresholds in Achlioptas processes
• Perfect matchings in the semirandom graph process
• Proof of the satisfiability conjecture for large \(k\)
• Semi-random graph process
• Sharp thresholds of graph properties, and the $k$-sat problem
• 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

Cited in

(2)

• Cliques, chromatic number, and independent sets in the semi-random process
• Subgraph games in the semi-random graph process and its generalization to hypergraphs

This page was built for publication: Sharp thresholds in adaptive random graph processes

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