{"id":"arxiv/2610.21381","url":"https://arxiv.org/abs/2610.21381","tags":["math.CO"],"score":0,"title":"Optimally large cuts in both directions","domain":"math.CO","source":"arxiv","authors":["Frederic Folz","Mykhaylo Tyomkyn"],"reviews":0,"subject":"math.CO","summary":"We prove that for every integer $d\\ge2$ and all sufficiently large $m$, every digraph with $m$ edges and minimum outdegree at least $d$ has a vertex bipartition for which each directed cut is of size at least \\[\\left\\lceil\\frac{d-1}{2(2d-1)}m+\\frac{d^2}{2(2d-1)}\\right\\rceil.\\] The bound is sharp for infinitely many $m$. This answers for large graphs a question of Scott and proves a conjecture of Lee, Loh, and Sudakov. For $d=2$ we prove that $\\lceil m/6\\rceil$ is achievable for all $m$. We also establish a stability result characterizing near-extremal graphs.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}