Hamiltonicity thresholds in Achlioptas processes

DOI10.1002/rsa.20302zbMath1204.60016arXiv0804.4707OpenAlexW3083030149MaRDI QIDQ3057066

Eyal Lubetzky, Michael Krivelevich, Benjamin Sudakov

Publication date: 24 November 2010

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

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

zbMATH Keywords

randomHamilton cyclesgraph processesAchiloptas processes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Eulerian and Hamiltonian graphs (05C45)

Related Items

Packing Directed Hamilton Cycles Online, Packing Hamilton Cycles Online, Anagram-Free Colourings of Graphs, 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, Anagram-free colorings of graphs, A geometric Achlioptas process, Sharp thresholds in adaptive random graph processes, Recent advances in percolation theory and its applications, Small subgraphs in random graphs and the power of multiple choices, Aggregation models with limited choice and the multiplicative coalescent, Ramsey games with giants, The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛, Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process, The Kőnig graph process, The Bohman-Frieze process near criticality, Delaying satisfiability for random 2SAT, Cores of random graphs are born Hamiltonian, Waiter-client and client-waiter Hamiltonicity games on random graphs

Cites Work

• Unnamed Item
• On two Hamilton cycle problems in random graphs
• Birth control for giants
• Balanced online Ramsey games in random graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• An algorithm for finding Hamilton paths and cycles in random graphs
• Hamiltonian circuits in random graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• Online balanced graph avoidance games
• Avoiding a giant component
• Hamilton cycles in 3-out
• Ramsey games with giants
• Online Ramsey Games in Random Graphs
• Local resilience of graphs
• Avoiding small subgraphs in Achlioptas processes
• Balanced Allocations
• Creating a Giant Component
• The isoperimetric constant of the random graph process
• Embracing the giant component