Short Proof of Erd\H os Conjecture for Triple Systems

Abstract

In 1965 Erd\H os conjectured that for all $k\ge 2$, $s\ge 1$ and $n\ge k(s+1)$, an $n$-vertex $k$-uniform hypergraph $\F$ with $ν(\F)=s$ cannot have more than \newline $\max \{(\genfrac{}{}{0ex}{}{sk+k-1}{k}),(\genfrac{}{}{0ex}{}{n}{k})-(\genfrac{}{}{0ex}{}{n-s}{k})\}$ edges. It took almost fifty years to prove it for triple systems. In 2012 we proved the conjecture for all $s$ and all $n\ge 4(s+1)$. Then Łuczak and Mieczkowska (2013) proved the conjecture for sufficiently large $s$ and all $n$. Soon after, Frankl proved it for all $s$. Here we present a simpler version of that proof which yields Erd\H os's conjecture for $s\ge 33$. Our motivation is to lay down foundations for a possible proof in the much harder case $k=4$, at least for large $s$.

15 pages, 1 figure