Avoiding small subgraphs in Achlioptas processes

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

zbMATH Keywords

random graphthresholdAchlioptas processsmall subgraph

Mathematics Subject Classification ID

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