Hamilton cycles in the semi-random graph process

DOI10.1016/J.EJC.2021.103423MaRDI QIDQ2237858zbMATH OpenOpenAlexFDO

Authors Pu Gao, Calum MacRury, Paweł Prałat, Bogumił Kamiński

Publication date 28 October 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in $(2+4e^{-2}+0.07+o(1)),n<2.61135,n$ rounds, assuming that a specific non-convex optimization problem has a negative solution (a premise we numerically support). Assuming that this technical condition holds, this improves upon the previously best known upper bound of $3,n$ rounds. We also show that the previously best lower bound of $(ln2+ln(1+ln2)+o(1)),n$ is not tight.

Recommendations

• scientific article; zbMATH DE number 1496581
• Hamiltonian cycles in random regular graphs
• Hamilton cycles in random graphs with a fixed degree sequence
• Hamilton cycles in a class of random directed graphs
• scientific article; zbMATH DE number 17675
• Hamilton cycles in the line graph of a random graph
• Hamilton cycles in random geometric graphs
• Hamilton Cycles in Random Regular Digraphs

Cites work

• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• scientific article; zbMATH DE number 7273765 (Why is no real title available?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Hamilton cycles in 3-out
• Hamiltonian circuits in random graphs
• JuMP: a modeling language for mathematical optimization
• Julia: a fresh approach to numerical computing
• Multi-Start Methods
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Semi-random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process

Cited in

(8)

• Semi-random graph process
• Hamiltonicity thresholds in Achlioptas processes
• Perfect matchings in the semirandom graph process
• Cliques, chromatic number, and independent sets in the semi-random process
• Subgraph games in the semi-random graph process and its generalization to hypergraphs
• Sharp thresholds in adaptive random graph processes
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Power of \(k\) choices in the semi-random graph process

Describes a project that uses

Uses Software

• Julia
• Ipopt
• Maple

This page was built for publication: Hamilton cycles in the semi-random graph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237858)