pipette
ESEspañol

Exact extremizers for -judicious bisections of triangle-free graphs

Shufei Wu

Preprint

In the authors' words

Balogh, Clemen and Lidick\'y asked how large the minimum -norm of the internal-edge counts over balanced partitions of an -vertex triangle-free graph can be. For each fixed and all sufficiently large even , we determine this value exactly for bisections and characterize all extremal graphs. They are precisely the complete bipartite graphs for which maximizes an explicit integer objective. All maximizing values of lie in an interval of length bounded in terms of alone. We also prove quantitative stability for the same range of and : for sufficiently small , every -vertex triangle-free graph with bisection value at least the asymptotic optimum minus is within edge edits of a complete bipartite graph with the optimal limiting class ratio.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.