Sharp thresholds in adaptive random graph processes

DOI10.1002/RSA.21197arXiv2207.14469MaRDI QIDQ6201040FDOQ6201040

Authors: Calum MacRury 

Publication date: 25 March 2024

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Concentration Inequalities and Martingale Inequalities: A Survey
• Proof of the satisfiability conjecture for large \(k\)
• Sharp thresholds of graph properties, and the $k$-sat problem
• Avoiding a giant component
• Hamiltonicity thresholds in Achlioptas processes
• Title not available (Why is that?)
• Hamilton cycles in the semi-random graph process
• Semi-random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Perfect matchings in the semirandom 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)