Partitionning a tournament into k-strongly connected subtournaments.

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 tournament is an orientation of a finite complete graph. For $r\geq1$, a tournament is strongly $r$-connected if it has more than $r$ vertices and remains strongly connected after deletion of fewer than $r$ vertices. This convention excludes a one-vertex part. For $W\subseteq V(T)$, $T[W]$ is the induced subtournament.

Statement recorded in the supplied source.

Given arbitrary positive integers $k_1,\ldots,k_p$, does there exist an integer $g(k_1,\ldots,k_p)$ such that every strongly $g(k_1,\ldots,k_p)$-connected tournament $T$ has a partition $V(T)=V_1\sqcup\cdots\sqcup V_p$ with every $T[V_i]$ a nontrivial strongly $k_i$-connected tournament? [S2] [S3]

Short English statement

Can enough initial connectivity guarantee a partition into induced tournaments with any prescribed positive connectivity requirements?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3279 (OPG-47643). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Partitionning a tournament into k-strongly connected subtournaments., node 47643, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/partitionning_a_tournament_into_k_strongly_connected_subtournaments.
• S3 António Girão and Shoham Letzter, Partitioning a tournament into sub-tournaments of high connectivity (2022), abstract. https://arxiv.org/abs/2210.17371.