{"id":"arxiv/2609.30927","url":"https://arxiv.org/abs/2609.30927","tags":["math.CO"],"score":0,"title":"Bounds for Unions of Several Parts in Balanced Graph Partitions","domain":"math.CO","source":"arxiv","authors":["Zhanping Yang"],"reviews":0,"subject":"math.CO","summary":"Let $k\\ge3$ and $1\\le \\ell\\le k-1$. We study balanced $k$-partitions of a graph for which the union of any $\\ell$ parts induces few edges. We show that every graph $G$ with $n$ vertices and $m$ edges admits a balanced partition $V_1,\\ldots,V_k$ such that \\begin{equation*} \\max_{\\substack{A\\in\\binom{[k]}{\\ell}}}e_G\\left(\\bigcup_{i\\in A}V_i\\right)\\le\\frac{\\ell^2}{k^2}m+\\frac{\\ell^2(k-\\ell)}{k^2}(n-1)+\\frac{\\ell(k-\\ell)}{k(k-1)}\\sqrt{\\left(\\binom{k}{\\ell}-1\\right)m}. \\end{equation*} In the case $\\ell=2$, our result confirms a conjecture of Bollobás and Scott in a stronger form.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}