1. An asymptotic resolution of a conjecture of Szemer\'{e}di and Petruska
- Author
-
Kézdy, André E. and Lehel, Jenő
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,05D05, 05C65 - 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\'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}$. 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\leq \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\'edi and Petruska with the skew version of Bollob\'as's theorem on set pair systems. The new approach improves the bound to $n\leq {m+2 \choose 2} + O(m^{{5}/{3}})$, resolving the conjecture asymptotically., Comment: 23 pages, no figures. Completes project begun in "On a conjecture of Szemer\'edi and Petruska", arXiv:1904.04921v2
- Published
- 2022