An asymptotic resolution of a conjecture of Szemerédi and Petruska

Abstract

Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemerédi and Petruska proved $n\le 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n\le \left(\genfrac{}{}{0ex}{}{m+2}{2}\right)$. This problem is known to be equivalent to determining the maximum order of a $\tau$-critical $3$-uniform hypergraph with transversal number $m$ (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, $n\le \frac{3}{4}{m}^2+m+1$, was obtained by Tuza using the machinery of $\tau$-critical hypergraphs. Here we propose an alternative approach, a combination of the iterative decomposition process introduced by Szemerédi and Petruska with the skew version of Bollobás's theorem on set pair systems. The new approach improves the bound to $n\le \left(\genfrac{}{}{0ex}{}{m+2}{2}\right)+O(m^{5/3})$, resolving the conjecture asymptotically.

arXiv comment23 pages, no figures. Completes project begun in "On a conjecture of Szemerédi and Petruska", arXiv:1904.04921v2