Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper resolves a long-standing conjecture by Scott regarding the optimal error term in the partitioning of 3-uniform hypergraphs. Specifically, it proves that any 3-uniform hypergraph with $m$ edges can be partitioned into $k$ vertex sets such that the number of edges within each part is bounded by $m/k^3 + O_k(m^{2/3})$. This result tightens the error term from $O_k(m^{6/7})$ to $O_k(m^{2/3})$, providing a more precise understanding of hypergraph partitioning.
The optimal $O(m^{2/3})$ error term for partitioning 3-uniform hypergraphs is finally established, improving upon previous bounds.
Let $k\ge2$ be a fixed integer. Bollobás and Scott proved that every $3$-uniform hypergraph with $m$ edges admits a partition of its vertex set into $k$ parts such that each part spans at most $m/k^3+O_k(m^{6/7})$ edges. Scott later suggested that the error term should be $O_k(m^{2/3})$. In this paper, we show that every $3$-uniform hypergraph with $m$ edges admits a partition into $k$ parts such that each part spans at most $m/k^3+O_k(m^{2/3})$ edges, thereby establishing the proposed error term.