Judiciously 3-partitioning 3-uniform hypergraphs
classification
🧮 math.CO
keywords
fracbollobedgesimprovedmathcalsqcupuniformasymptotic
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.