Bounds for Unions of Several Parts in Balanced Graph Partitions
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 28 de septiembre. arXiv. Preprint, todavía sin revisión por pares.