{"id":"arxiv/2608.09728","url":"https://arxiv.org/abs/2608.09728","tags":["math.CO"],"score":0,"title":"Prescribed-order subdigraphs with large minimum out-degree","domain":"math.CO","source":"arxiv","authors":["Bin Chen","Lanchao Wang"],"reviews":0,"subject":"math.CO","summary":"Alon introduced $d(s)$ as the largest integer $d$ such that every digraph on $2n$ vertices with minimum out-degree at least $s$ contains a subdigraph on $n$ vertices with minimum out-degree at least $d$. He proved that $s/2-d(s)=O(\\sqrt{s\\log s})$, and further asked whether this deficit can be bounded by an absolute constant. Steiner answered this question in the negative by constructing suitable tournaments, and showed that $s/2-d(s)=Ω(\\log s)$. Using a different construction, we show that the deficit grows at least on the square-root scale, rather than merely logarithmically, improving the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}