Small subgraphs in random graphs and the power of multiple choices

DOI10.1016/j.jctb.2010.12.008zbMath1226.05229OpenAlexW2024436752MaRDI QIDQ536648

Henning Thomas, Reto Spöhel, Torsten Mütze

Publication date: 19 May 2011

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2010.12.008

zbMATH Keywords

random graphthresholdsmall subgraphachlioptas processpower of choices

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (9)

Picker-chooser fixed graph games ⋮ Random k -SAT and the power of two choices ⋮ A geometric Achlioptas process ⋮ On Balanced Coloring Games in Random Graphs ⋮ On balanced coloring games in random graphs ⋮ Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process ⋮ The Bohman-Frieze process near criticality ⋮ Probabilistic intuition holds for a class of small subgraph games ⋮ Waiter-client and client-waiter Hamiltonicity games on random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Birth control for giants
• Balanced online Ramsey games in random graphs
• Threshold functions
• Online balanced graph avoidance games
• Avoiding a giant component
• Offline thresholds for Ramsey-type games on random graphs
• Hamiltonicity thresholds in Achlioptas processes
• Online Ramsey Games in Random Graphs
• Avoiding small subgraphs in Achlioptas processes
• Threshold functions for small subgraphs
• Paths in graphs
• Creating a Giant Component
• Embracing the giant component

This page was built for publication: Small subgraphs in random graphs and the power of multiple choices