2020/06/01 by Liu, Guanwu, Yu, Xingxing
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2006.01116
Scott asked the question of determining cd such that if D is a digraph with m arcs and minimum outdegree d≥ 2 then V(D) has a partition V1, V2 such that min\e(V1,V2),e(V2, V1)\≥ cdm, where e(V1,V2) (respectively, e(V2,V1)) is the number of arcs from V1 to V2 (respectively, from V2 to V1). Lee, Loh, and Sudakov showed that c2=1/6+o(1) and c3=1/5+o(1), and conjectured that cd= (d-1)/(2(2d-1))+o(1) for d≥ 4. In this paper, we show c4=3/14+o(1) and prove some partial results for d≥ 5.