Bounds for Unions of Several Parts in Balanced Graph Partitions
In the authors' words
Let and . We study balanced -partitions of a graph for which the union of any parts induces few edges. We show that every graph with vertices and edges admits a balanced partition 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 , our result confirms a conjecture of Bollob\'as and Scott in a stronger form.
Main resultThe abstract does not state a limitation.
Appeared: Monday, September 28. arXiv. Preprint, not yet peer-reviewed.