On 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)$. Tuza proved the best known bound, $n\le \frac{3}{4}{m}^2+m+1$, using the machinery of $\tau$-critical hypergraphs. Here we propose an alternative approach, combining a decomposition process introduced by Szemerédi and Petruska with the skew version of Bollobás's theorem to prove $n\le m^2+6m+2$. While the bound obtained here is weaker than Tuza's bound, it is a proof-of-concept for a different approach and a call to apply dimension bounds from linear algebra.

9 pages, no figures: Version 2 reflects new information about the best known upper bound. We are very grateful to Zsolt Tuza for alerting us to the best known upper bound, $\frac{3}{4}{m}^2+m+1$, for the maximum order of a $\tau$-critical $3$-uniform hypergraph with transversal number $m$