On a conjecture of Szemerédi and Petruska

Adam S. Jobson, André E. Kézdy, Tim Pervenecki

Published 2019-04-09Version 1

Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemer\'edi and Petruska proved $n\leq 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n\leq{m+2\choose 2}$. Gy\'arf\'as, Lehel, and Tuza improved the bound, proving $n\leq 2m^2+m$. Here we combine a decomposition process introduced by Szemer\'edi and Petruska with the skew version of Bollob\'as's theorem to prove $n\leq m^2 + 6m + 2$. This also improves an upper bound for the maximum order of a $\tau$-critical $3$-uniform hypergraph with transverval number $m$.