Sharp thresholds in adaptive random graph processes

DOI10.1002/rsa.21197arXiv2207.14469MaRDI QIDQ6201040

Unnamed Author, 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

sharp thresholdsrandom graph processesonline decision-making

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Hamilton cycles in the semi-random graph process
• Avoiding a giant component
• Proof of the Satisfiability Conjecture for Large k
• Hamiltonicity thresholds in Achlioptas processes
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Concentration Inequalities and Martingale Inequalities: A Survey
• Sharp thresholds of graph properties, and the $k$-sat problem
• 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
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs