Splitting a digraph with minimum outdegree constraints

Definitions and mathematical statement

Let $D=(V,A)$ be a finite simple loopless digraph; two opposite arcs between a pair are allowed. The outdegree $d_D^+(v)$ is the number of arcs leaving $v$, and the minimum outdegree is $\delta^+(D)=\min_vd_D^+(v)$. For $X\subseteq V$, the induced subdigraph $D[X]$ retains precisely the arcs with both endpoints in $X$.

For every positive integer $d$, ask whether a finite integer $f(d)$ exists such that every $D$ with $\delta^+(D)\ge f(d)$ admits a partition \[ V=X\mathbin{\dot\cup}Y,\qquad X,Y\ne\varnothing, \qquad\delta^+(D[X])\ge d,\quad\delta^+(D[Y])\ge d. \] If a threshold exists, $f(d)$ denotes the least possible one. The desired bound depends only on $d$, not on the order of the digraph. Arcs between the parts do not contribute to either required outdegree, and there is no balancing condition on their cardinalities.

This states the intended threshold problem: the source’s abbreviated sentence says minimum outdegree $d$ where its function $f(d)$ must occur. The latter reading would generally fail already for small examples and would leave the threshold undefined. The two parts need only satisfy their internal minimum outdegree conditions; they are not required to be strongly connected or to induce tournaments. An answer should settle finite existence for every $d$, with quantitative bounds providing additional information.

Short English statement

Does sufficiently large minimum outdegree, depending only on d, force a partition into two nonempty induced digraphs each of minimum outdegree at least d?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3265 (OPG-46456), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Splitting a digraph with minimum outdegree constraints. Original problem and discussion. http://www.openproblemgarden.org/op/splitting_a_digraph_with_minimum_outdegree_constraints.
• S3 N. Alon, Splitting digraphs, Combinatorics, Probability and Computing 15 (2006). https://web.math.princeton.edu/~nalon/PDFS/split.pdf.