2022/08/24 by André E. Kézdy, Kézdy, André E., Jenő Lehel +1
Engineering · Mathematics · #05C65 #05D05 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2208.11573
openalex publication_date 2022/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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≤ 8m2+3m, for fixed m=n-k, and they conjectured the sharp bound n ≤ m+2 \choose 2. This problem is known to be equivalent to determining the maximum order of a τ-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≤ (3)/(4)m2+m+1, was obtained by Tuza using the machinery of τ-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≤ m+2 \choose 2 + O(m^5/3), resolving the conjecture asymptotically.