pipette
ENEnglish

Optimally large cuts in both directions

Frederic Folz, Mykhaylo Tyomkyn

Preprint

En palabras de los autores

We prove that for every integer and all sufficiently large , every digraph with edges and minimum outdegree at least 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 . This answers for large graphs a question of Scott and proves a conjecture of Lee, Loh, and Sudakov. For we prove that is achievable for all . We also establish a stability result characterizing near-extremal graphs.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.