Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper investigates judicious partitioning problems for graphs and hypergraphs, aiming to simultaneously optimize multiple criteria related to edge intersections within vertex classes. The authors establish new bounds for hypergraphs with edges of size at most 2 and 3, and for graphs partitioned into $k$ classes, resolving several conjectures by Bollobás and Scott/Thomason. Key results include proving that every hypergraph with non-negative edge weights and edges of size at most 2 has a bipartition where each class meets edges of total weight at least $(w_1-Δ_1)/2+2w_2/3$, and that for $k\ge4$, every graph with $m\ge2(k-1)(k-2)$ edges has a $k$-partition where each class meets at least $2m/(2k-1)$ edges.
Resolving long-standing conjectures, this work proves tight bounds for judicious graph and hypergraph partitions, showing that optimal edge coverage is achievable even with multiple partitions.
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\ge4$, every graph with $m\ge2(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.