Subdivision of a transitive tournament in digraphs with large outdegree.

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.

For $k\ge1$, the transitive tournament $T_k$ has vertices $1,\ldots,k$ and arcs $i\to j$ whenever $i<j$. A subdivision replaces every arc by a directed path with the same endpoints, all internal vertices of these paths distinct and disjoint from the tournament's branch vertices. Write $\delta^+(D)$ for the minimum outdegree of a finite simple digraph $D$.

Statement recorded in the supplied source.

Does there exist a function $f:\mathbb N\to\mathbb Z_{\ge0}$ such that, for every $k$ and every $D$ with $\delta^+(D)\ge f(k)$, the digraph $D$ contains a subdivision of $T_k$? The source singles out existence of $f(5)$ as a test case. [S2]

Short English statement

Does sufficiently large minimum outdegree force a subdivision of any prescribed transitive tournament?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3268 (OPG-46680). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Subdivision of a transitive tournament in digraphs with large outdegree., original node 46680, statement and mathematical discussion. https://www.openproblemgarden.org/op/subdivision_of_a_transitive_tournament_in_digraphs_with_large_outdegree.