The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛

DOI10.1090/S0894-0347-2010-00678-9zbMATH Open1205.91042arXiv0909.2744OpenAlexW2079376502WikidataQ105585021 ScholiaQ105585021MaRDI QIDQ3074554FDOQ3074554

Authors: Michael Krivelevich 

Publication date: 9 February 2011

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

hypergraphcomplete graphHamiltonicitymaker breaker game

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Games involving graphs (91A43)

Cites Work

• Random graphs.
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Combinatorial Games
• On two problems regarding the Hamiltonian cycle game
• Fast winning strategies in maker-breaker games
• Hamiltonian circuits in random graphs
• Title not available (Why is that?)
• Biased positional games and small hypergraphs with large covers
• Hamiltonicity thresholds in Achlioptas processes
• Title not available (Why is that?)

Cited In (46)

• Maker-Breaker games on randomly perturbed graphs
• Avoider-Enforcer games played on edge disjoint hypergraphs
• Maker-breaker percolation games. II: Escaping to infinity
• Avoider-forcer games on hypergraphs with small rank
• Multistage positional games
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Biased positional games and small hypergraphs with large covers
• Creating cycles in walker-breaker games
• Biased games on random boards
• On the odd cycle game and connected rules
• Fast embedding of spanning trees in biased maker-breaker games
• Sharp thresholds for half-random games. I.
• Sharp thresholds for half-random games. II
• Maker-Breaker total domination game on cubic graphs
• Winning fast in biased maker-breaker games
• A threshold for the maker-breaker clique game
• Chvátal-Erdős condition for pancyclicity
• Hamiltonian games
• 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}\)
• Manipulative waiters with probabilistic intuition
• Fast embedding of spanning trees in biased maker-breaker games
• Random-player maker-breaker games
• Connector-breaker games on random boards
• Generating random graphs in biased maker-breaker games
• The threshold bias of the clique-factor game
• Walker-breaker games on \(G_{n, p}\)
• Maker–Breaker percolation games I: crossing grids
• Hamilton cycles in pseudorandom graphs
• Hamiltonian maker-breaker games on small graphs
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• 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
• Spanning Structures in Walker–Breaker Games
• Generalized pairing strategies -- a bridge from pairing strategies to colorings
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Robust Hamiltonicity of Dirac graphs
• Graph Tilings in Incompatibility Systems
• On the Hamiltonicity of the \(k\)-regular graph game
• Maker-breaker games on random geometric graphs

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)