d(s) asymptotics in minimum-outdegree subdigraphs

Open problem: closing the gap for $d(s)$ · arXiv:2210.12699

arXiv Informal medium confidence— first stated 2022-10-23

Status open medium confidence

The open problem of closing the gap $\Omega(\log s) < s/2 - d(s) < O(\sqrt{s\log s})$ remains unresolved. The source paper (Steiner, arXiv:2210.12699, published Journal of Graph Theory 2024) established the lower bound $\Omega(\log s)$ by disproving Alon's conjecture that $s/2 - d(s) = O(1)$, while the upper bound $O(\sqrt{s\log s})$ is due to Alon's probabilistic argument. A paper titled 'New results on a problem of Alon' appeared in Discrete Mathematics (2024), but its arXiv preprint could not be located and its content could not be verified within the search limit.

Reviewer notes. A paper 'New results on a problem of Alon' appeared in Discrete Mathematics 2024 (ScienceDirect pii S0012365X24004680) which is directly relevant by title, but the ScienceDirect page returned HTTP 403 and no arXiv preprint was found within the 5-call limit. It is unclear whether it improves the bounds or addresses a related but different Alon problem. The gap $\Omega(\log s) < s/2 - d(s) < O(\sqrt{s\log s})$ should be regarded as open with medium confidence pending verification of that paper.

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

Informal. It remains an interesting open problem to close the gap between the lower and upper bounds: $\Omega(\log s) < \frac{s}{2} - d(s) < O(\sqrt{s\log s})$, where $d(s)$ denotes the largest integer such that every $2n$-vertex digraph of minimum out-degree at least $s$ contains an $n$-vertex subdigraph of minimum out-degree at least $d(s)$.

Context

After disproving Alon's problem, the authors note that the true asymptotic behaviour of $\frac{s}{2} - d(s)$ lies somewhere between $\Omega(\log s)$ (established by their construction) and $O(\sqrt{s\log s})$ (established by Alon's probabilistic argument). The precise asymptotics of $d(s)$ remain open.

Notes. Stated in prose without a labelled environment; PDF source may garble some exponent notation.

Source paper

Subdigraphs of prescribed size and outdegree
Raphael Steiner · 2022-10-23
https://arxiv.org/abs/2210.12699 PDF source