betaFeedback

WorksMathematics

Exact extremizers for ℓp\ell_p-judicious bisections of triangle-free graphs

Abstract

Balogh, Clemen and Lidický asked how large the minimum ℓp\ell_p-norm of the internal-edge counts over balanced partitions of an nn-vertex triangle-free graph can be. For each fixed 2<p<∞2<p<\infty and all sufficiently large even nn, we determine this value exactly for bisections and characterize all extremal graphs. They are precisely the complete bipartite graphs Ka,n−aK_{a,n-a} for which a≤n/2a\le n/2 maximizes an explicit integer objective. All maximizing values of aa lie in an interval of length bounded in terms of pp alone. We also prove quantitative stability for the same range of pp and nn: for sufficiently small δ≥0δ\ge 0, every nn-vertex triangle-free graph with bisection value at least the asymptotic optimum minus δn2δn^2 is within Op(δn2+n)O_p(δn^2+n) edge edits of a complete bipartite graph with the optimal limiting class ratio.

Paper details

vlnc:W_u9s8vrjn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

generative AI tools

View statement
Looking for related papers…