PreprintarXiv licencearXiv
Bounds for Unions of Several Parts in Balanced Graph Partitions
Abstract
Let k≥3 and 1≤ ℓ≤ k−1. We study balanced k-partitions of a graph for which the union of any ℓ parts induces few edges. We show that every graph G with n vertices and m edges admits a balanced partition V1,…,Vk such that maxsubstackA∈binom[k]ℓeG(⋃i∈ AVi)≤ℓ2/k2m+(ℓ2(k−ℓ))/k2(n−1)+(ℓ(k−ℓ))/(k(k−1))√((binomkℓ−1)m). In the case ℓ=2, our result confirms a conjecture of Bollobás and Scott in a stronger form.
Related
- On partitions with bounded multiplicity restrictions on even parts and with the largest part being odd
- Maximum length and size of simultaneous core partitions with distinct parts
- A uniform proof approach for congruences modulo 3 for partitions with k-colored odd parts
- Congruences modulo powers of $7$ for partitions with colored odd parts
- Untrodden pathways in the study of partitions with parts separated by parity
BibTeX
@misc{yang2026bounds,
title = {{Bounds for Unions of Several Parts in Balanced Graph Partitions}},
author = {Zhanping Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.30927},
eprint = {2609.30927},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30927},
}
RIS
TY - UNPB
TI - Bounds for Unions of Several Parts in Balanced Graph Partitions
AU - Zhanping Yang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2609.30927
UR - https://arxiv.org/abs/2609.30927
AB - Let k≥3 and 1≤ ℓ≤ k−1. We study balanced k-partitions of a graph for which the union of any ℓ parts induces few edges. We show that every graph G with n vertices and m edges admits a balanced partition V_1,…,V_k such that max_substackA∈binom[k]ℓe_G(⋃_i∈ AV_i)≤ℓ^2/k^2m+(ℓ^2(k−ℓ))/k^2(n−1)+(ℓ(k−ℓ))/(k(k−1))√((binomkℓ−1)m). In the case ℓ=2, our result confirms a conjecture of Bollobás and Scott in a stronger form.
ER -