The critical bias for the Hamiltonicity game is (1+đ(1))đ/lnđ
From MaRDI portal
Publication:3074554
Abstract: We prove that in the biased 1:b Hamiltonicity Maker-Breaker game, played on the edges of the complete graph K_n, Maker has a winning strategy for b(n)<=(1-o(1))n/ln n, for all large enough n.
Recommendations
- The speed and threshold of the biased perfect matching and Hamilton cycle games
- A Hamiltonian game on \(K_{n,n}\)
- The biased, distance-restricted \(n\)-in-a-row game for small \(p\)
- A non-trivial upper bound on the threshold bias of the oriented-cycle game
- On the biased \(n\)-in-a-row game
- On the Hamiltonicity of the k-regular graph game
- On two problems regarding the Hamiltonian cycle game
- A sharp threshold for the Hamilton cycle MakerâBreaker game
- scientific article; zbMATH DE number 1354920
- Asymptotic random graph intuition for the biased connectivity game
Cites work
- scientific article; zbMATH DE number 3815680 (Why is no real title available?)
- scientific article; zbMATH DE number 3970795 (Why is no real title available?)
- Asymptotic random graph intuition for the biased connectivity game
- Biased Positional Games
- Biased positional games and small hypergraphs with large covers
- Combinatorial Games
- Fast winning strategies in maker-breaker games
- Hamiltonian circuits in random graphs
- Hamiltonicity thresholds in Achlioptas processes
- On two problems regarding the Hamiltonian cycle game
- Random graphs.
Cited in
(46)- Avoider-Enforcer games played on edge disjoint hypergraphs
- Maker-breaker games on random geometric graphs
- Maker-breaker percolation games. II: Escaping to infinity
- Maker-Breaker games on randomly perturbed graphs
- Avoider-forcer games on hypergraphs with small rank
- Waiter-Client and Client-Waiter planarity, colorability and minor games
- Biased positional games and small hypergraphs with large covers
- Multistage positional games
- Creating cycles in walker-breaker games
- On the odd cycle game and connected rules
- Fast embedding of spanning trees in biased maker-breaker games
- Biased games on random boards
- Sharp thresholds for half-random games. I.
- Sharp thresholds for half-random games. II
- Winning fast in biased maker-breaker games
- Maker-Breaker total domination game on cubic graphs
- A threshold for the maker-breaker clique game
- Hamiltonian games
- ChvĂĄtal-ErdĹs condition for pancyclicity
- Maker Breaker on digraphs
- Fast strategies in Waiter-Client games
- Fast winning strategies for staller in the maker-breaker domination game
- A Hamiltonian game on \(K_{n,n}\)
- Random-player maker-breaker games
- Fast embedding of spanning trees in biased maker-breaker games
- Manipulative waiters with probabilistic intuition
- Connector-breaker games on random boards
- Generating random graphs in biased maker-breaker games
- The threshold bias of the clique-factor game
- MakerâBreaker percolation games I: crossing grids
- Walker-breaker games on \(G_{n, p}\)
- Hamilton cycles in pseudorandom graphs
- A non-trivial upper bound on the threshold bias of the oriented-cycle game
- Hamiltonian maker-breaker games on small graphs
- Biased orientation games
- Efficient winning strategies in random-turn maker-breaker games
- A strategy for isolator in the toucher-isolator game on trees
- Complexity of maker-breaker games on edge sets of graphs
- The toucher-isolator game
- The speed and threshold of the biased perfect matching and Hamilton cycle games
- Generalized pairing strategies -- a bridge from pairing strategies to colorings
- Spanning Structures in WalkerâBreaker Games
- \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
- Robust Hamiltonicity of Dirac graphs
- On the Hamiltonicity of the k-regular graph game
- Graph Tilings in Incompatibility Systems
This page was built for publication: The critical bias for the Hamiltonicity game is (1+đ(1))đ/lnđ
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3074554)
