Avoiding small subgraphs in Achlioptas processes
From MaRDI portal
Publication:3608317
DOI10.1002/RSA.20254zbMath1182.05112arXiv0708.0443OpenAlexW2951119921MaRDI QIDQ3608317
Michael Krivelevich, Po-Shen Loh, Benjamin Sudakov
Publication date: 4 March 2009
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0708.0443
Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Combinatorial probability (60C05) Graph minors (05C83)
Related Items (17)
Picker-chooser fixed graph games ⋮ Getting a Directed Hamilton Cycle Two Times Faster ⋮ Random k -SAT and the power of two choices ⋮ On the Power of Choice for Boolean Functions ⋮ Finding Hamilton cycles in random graphs with few queries ⋮ A geometric Achlioptas process ⋮ On Balanced Coloring Games in Random Graphs ⋮ Small subgraphs in random graphs and the power of multiple choices ⋮ Offline thresholds for Ramsey-type games on random graphs ⋮ Hamiltonicity thresholds in Achlioptas processes ⋮ On balanced coloring games in random graphs ⋮ Ramsey games with giants ⋮ Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process ⋮ The Bohman-Frieze process near criticality ⋮ Delaying satisfiability for random 2SAT ⋮ Probabilistic intuition holds for a class of small subgraph games ⋮ Waiter-client and client-waiter Hamiltonicity games on random graphs
Cites Work
- Birth control for giants
- Compactness results in extremal graph theory
- Avoiding a giant component
- Memoryless Rules for Achlioptas Processes
- Concentration of non‐Lipschitz functions and applications
- Product rule wins a competitive game
- Creating a Giant Component
- A phase transition for avoiding a giant component
- Embracing the giant component
This page was built for publication: Avoiding small subgraphs in Achlioptas processes
