Hamiltonicity thresholds in Achlioptas processes
From MaRDI portal
Abstract: In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are presented with K=K(n) edges, chosen uniformly at random from the missing ones, and are asked to add one of them to the current graph. The goal is to create a Hamilton cycle as soon as possible. We show that this problem has three regimes, depending on the value of K. For K=o(log n), the threshold for Hamiltonicity is (1+o(1))nlog n /(2K), i.e., typically we can construct a Hamilton cycle K times faster that in the usual random graph process. When K=omega(log n) we can essentially waste almost no edges, and create a Hamilton cycle in n+o(n) rounds with high probability. Finally, in the intermediate regime where K=Theta(log n), the threshold has order n and we obtain upper and lower bounds that differ by a multiplicative factor of 3.
Recommendations
Cites work
- An algorithm for finding Hamilton paths and cycles in random graphs
- Avoiding a giant component
- Avoiding small subgraphs in Achlioptas processes
- Balanced Allocations
- Balanced online Ramsey games in random graphs
- Birth control for giants
- Creating a Giant Component
- Embracing the giant component
- Hamilton cycles in 3-out
- Hamiltonian circuits in random graphs
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Local resilience of graphs
- On two Hamilton cycle problems in random graphs
- Online balanced graph avoidance games
- Online Ramsey games in random graphs
- Ramsey games with giants
- Sudden emergence of a giant k-core in a random graph
- The isoperimetric constant of the random graph process
Cited in
(26)- Anagram-free colorings of graphs
- Waiter-client and client-waiter Hamiltonicity games on random graphs
- The Bohman-Frieze process near criticality
- Delaying satisfiability for random 2SAT
- Cores of random graphs are born Hamiltonian
- Getting a directed Hamilton cycle two times faster
- Ramsey games with giants
- The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
- Packing directed Hamilton cycles online
- Packing Hamilton cycles online
- Anagram-free colourings of graphs
- Random k-SAT and the power of two choices
- Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
- The Kőnig graph process
- Avoiding small subgraphs in Achlioptas processes
- On the connectivity threshold of Achlioptas processes
- On the power of choice for Boolean functions
- Recent advances in percolation theory and its applications
- Aggregation models with limited choice and the multiplicative coalescent
- Small subgraphs in random graphs and the power of multiple choices
- Sharp thresholds in adaptive random graph processes
- Linear colouring of binomial random graphs
- Fast construction on a restricted budget
- Constructing Hamilton cycles and perfect matchings efficiently (extended abstract)
- Building Hamiltonian cycles in the semi-random graph process in less than 2n rounds
- A geometric Achlioptas process
This page was built for publication: Hamiltonicity thresholds in Achlioptas processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057066)
