Exact exponent constant for tournament path powers

Open Problem: exact constant in the exponent · arXiv:2010.05735

arXiv Informal medium confidence— first stated 2021-02-16

Authors: Nemanja Draganić, François Dross, Jacob Fox, António Girão, Frédéric Havet, Dániel Korándi, William Lochet, David Munhá Correia, Alex Scott, Benny Sudakov

Status open high confidence

The open problem asks for the exact constant $c$ in the exponent such that every $n$-vertex tournament contains the $k$-th power of a directed path of length $n/2^{ck}$; the source paper establishes the form is $n/2^{\Theta(k)}$ with lower bound constant optimisable to $c \approx 3.9$ and upper bound constant $c = 1$ (from Yuster's construction). A follow-up paper (arXiv:2105.12484, Gir\~ao and Kor\'{a}ndi, 2021) studies the related problem of partitioning tournaments into at most $2^{ck}$ $k$-th powers of paths (tight up to the exponential constant) but does not address the exact constant for containment. No subsequent work resolving the exact value of $c$ was found in a thorough web search.

Cited literature (1)

partial Powers of paths and cycles in tournaments (2021)

António Girão, Dániel Korándi · arXiv preprint · arXiv:2105.12484

Shows any tournament can be partitioned into at most $2^{ck}$ $k$-th powers of directed paths (tight up to the exponential constant), a related but distinct result that does not determine the exact constant for the containment problem.

Reviewer notes. The specific open problem is to find the exact value of $c$ in $n/2^{ck}$, where the current gap is $c \in [1, \approx 3.9]$. The follow-up arXiv:2105.12484 is verified and relevant to the broader topic but addresses tournament decomposition, not containment. No paper resolving the exact constant was found after an exhaustive 5-call web search spanning 2021–2026.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It would be interesting to find the exact value of the constant factor in the exponent. Optimizing our proof can yield a lower bound of $n/2^{ck+o(k)}$ with $c \approx 3.9$, but is unlikely to give the correct bound.

Context

Theorem 1 and Yuster's construction together show that the optimal guaranteed length of the $k$-th power of a directed path in any $n$-vertex tournament has the form $n/2^{\Theta(k)}$. The paper provides a lower bound $n/2^{4k+6k}$ and an upper bound $k(k+1)n/2^k$, leaving a gap in the constant in the exponent.

Notes. Stated in prose without a labelled environment; verbatim phrasing 'It would be interesting to find the exact value of the constant factor in the exponent.'

Source paper

Powers of paths in tournaments
Nemanja Draganić, François Dross, Jacob Fox, António Girão, Frédéric Havet, Dániel Korándi, William Lochet, David Munhá Correia, Alex Scott, Benny Sudakov · 2021-02-16
https://arxiv.org/abs/2010.05735 PDF source