Judiciously 3-partitioning 3-uniform hypergraphs

Hunter Spink, Marius Tiba

Published 2018-10-03Version 1

Bollob\'as, Reed and Thomason proved every $3$-uniform hypergraph $\mathcal{H}$ with $m$ edges has a vertex-partition $V(\mathcal{H})=V_1 \sqcup V_2 \sqcup V_3$ such that each part meets at least $\frac{1}{3}(1-\frac{1}{e})m$ edges, later improved to $0.6m$ by Halsegrave and improved asymptotically to $0.65m+o(m)$ by Ma and Yu. We improve this asymptotic bound to $\frac{19}{27}m+o(m)$, which is best possible up to the error term, resolving a special case of a conjecture of Bollob\'as and Scott.