Edge-disjoint Hamilton cycles in highly strongly connected tournaments.

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite tournament is a digraph having exactly one of $u\to v$ and $v\to u$ for every pair of distinct vertices. It is strongly $r$-connected if it has more than $r$ vertices and deleting any set of fewer than $r$ vertices leaves a strongly connected digraph. A directed Hamilton cycle visits every vertex exactly once. A regular tournament of order $n$ has indegree and outdegree $(n-1)/2$ at every vertex.

Statement recorded in the supplied source.

For every integer $k\geq2$, does there exist an integer $f(k)$ such that every strongly $f(k)$-connected tournament contains $k$ pairwise arc-disjoint directed Hamilton cycles? The accompanying regular-tournament question (Kelly's conjecture) asks whether every regular tournament of order $n$ has an arc decomposition into $(n-1)/2$ directed Hamilton cycles. [S2] [S3]

Short English statement

The historical questions ask for many disjoint Hamilton cycles from sufficiently high connectivity, and for a full Hamilton decomposition of every regular tournament.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3278 (OPG-47031). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Edge-disjoint Hamilton cycles in highly strongly connected tournaments., node 47031, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/edge_disjoint_hamilton_cycles.
• S3 Daniela Kühn, John Lapinskas, Deryk Osthus and Viresh Patel, Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments (2013), abstract. https://arxiv.org/abs/1303.4213.