Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 16 min ago
PreprintarXiv licencearXiv

Optimally large cuts in both directions

  • Frederic Folz
  • Mykhaylo Tyomkyn
Open at sourcePDFDOICite

Abstract

We prove that for every integer d≥2 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 ⌈(d−1)/(2(2d−1))m+d2/(2(2d−1))⌉. 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 ⌈ m/6⌉ is achievable for all m. We also establish a stability result characterizing near-extremal graphs.

Related

  1. Improved Bounds on the Rate of Convergence to Stationarity of the M/M/N Queue as Both the Number of Servers and the Arrival Rate Grow Large
    Alexander Zeifman, Yacov Satin, Rostislav Razumchik
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  2. Optimally pseudorandom K4-free graphs
    Jie Han, Ferdinand Ihringer, Hendrik Van Maldeghem
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Counterexamples and Sufficient Conditions: Comments on "Optimally-Transported Generalized Method of Moments"
    Masahiro Kato
    arXivPreprintCC BY-NC-ND 4.0Full textStatisticsarXiv
  4. When can Optimally Trained Transformers Achieve Near-Lossless Token Prediction for non-Markovian Data?
    Kağan Akman, Jake Feldman Starosta, Naci Saldi +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlProbabilityarXiv
  5. Optimally Emulating Smooth Functions for Bayesian Analyses
    Scott Pratt, Oleh Savchuk, Eren Erdogan +4
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{folz2026optimally,
  title = {{Optimally large cuts in both directions}},
  author = {Frederic Folz and Mykhaylo Tyomkyn},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21381},
  eprint = {2610.21381},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21381},
}
RIS
TY  - UNPB
TI  - Optimally large cuts in both directions
AU  - Frederic Folz
AU  - Mykhaylo Tyomkyn
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21381
UR  - https://arxiv.org/abs/2610.21381
AB  - We prove that for every integer d≥2 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 ⌈(d−1)/(2(2d−1))m+d^2/(2(2d−1))⌉. 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 ⌈ m/6⌉ is achievable for all m. We also establish a stability result characterizing near-extremal graphs.
ER  -