On several judicious partitioning problems of graphs and hypergraphs
Abstract
Judicious partition problems ask for vertex partitions of graphs or hypergraphs that optimize several quantities simultaneously. In this paper, we investigate judicious partitions of graphs and hypergraphs in which each class meets many edges and establish the following results. (1) Every hypergraph with nonnegative edge weights and all edges of size at most $2$ has a bipartition in which each vertex class meets edges of total weight at least (w1−Δ1)/2+2w2/3, where wi is the total weight of the edges of size i, and Δ1 is the maximum weight of an edge of size $1$. (2) Every hypergraph with all edges of size at most $3$ has a bipartition in which each vertex class meets at least m1/2+3m2/4+7m3/8+o(m1+m2+m3) edges, where mi is the number of edges of size i. (3) For any integer k≥4, every graph with m≥2(k−1)(k−2) edges has a partition into k classes, each meeting at least $2m/(2k-1)$ edges. Both the coefficient of m and the edge threshold are best possible. (4) For all sufficiently large m, every $4$-uniform hypergraph with m edges has a partition into four classes, each meeting at least 4m/7 edges. The first three statements are conjectures of Bollobás and Scott, and the last is a conjecture of Bollobás and Thomason on 4-uniform hypergraphs. All of the above results are best possible.
Related
- The O(m2/3) error term for judicious partitions of 3-uniform hypergraphs
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- Exact extremizers for ℓp-judicious bisections of triangle-free graphs
- Bidirectional Labeling with b-values in Directed Graphs and Decision Hypergraphs
- Solutions to several problems on infinite sumset configurations
BibTeX
@misc{lin2026several,
title = {{On several judicious partitioning problems of graphs and hypergraphs}},
author = {Siwei Lin and Qinghou Zeng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19800},
eprint = {2610.19800},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19800},
}
RIS
TY - UNPB
TI - On several judicious partitioning problems of graphs and hypergraphs
AU - Siwei Lin
AU - Qinghou Zeng
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19800
UR - https://arxiv.org/abs/2610.19800
AB - Judicious partition problems ask for vertex partitions of graphs or hypergraphs that optimize several quantities simultaneously. In this paper, we investigate judicious partitions of graphs and hypergraphs in which each class meets many edges and establish the following results. (1) Every hypergraph with nonnegative edge weights and all edges of size at most $2$ has a bipartition in which each vertex class meets edges of total weight at least (w_1−Δ_1)/2+2w_2/3, where w_i is the total weight of the edges of size i, and Δ_1 is the maximum weight of an edge of size $1$. (2) Every hypergraph with all edges of size at most $3$ has a bipartition in which each vertex class meets at least m_1/2+3m_2/4+7m_3/8+o(m_1+m_2+m_3) edges, where m_i is the number of edges of size i. (3) For any integer k≥4, every graph with m≥2(k−1)(k−2) edges has a partition into k classes, each meeting at least $2m/(2k-1)$ edges. Both the coefficient of m and the edge threshold are best possible. (4) For all sufficiently large m, every $4$-uniform hypergraph with m edges has a partition into four classes, each meeting at least 4m/7 edges. The first three statements are conjectures of Bollobás and Scott, and the last is a conjecture of Bollobás and Thomason on 4-uniform hypergraphs. All of the above results are best possible.
ER -