Optimal bisections of directed graphs
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:VREBRIV7record.jsonopen to challenge →
classification
math.CO
keywords
directedarcsbisectionsgraphsleastoptimaladmitsanswer
read the original abstract
In this paper, motivated by a problem of Scott and a conjecture of Lee, Loh and Sudakov we consider bisections of directed graphs. We prove that every directed graph with $m$ arcs and minimum semidegree at least $d$ admits a bisection in which at least $\left(\frac{d}{2(2d+1)}+o(1)\right)m$ arcs cross in each direction. This provides an optimal bound as well as a positive answer to a question of Hou and Wu in a stronger form.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.