2022/04/06 by Kézdy, André E., Lehel, Jenő
#05C65 (secondary) #05D05 (primary) 05D15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2204.02859
Recently we asymptotically resolved the long-standing Szemerédi and Petruska conjecture. Several decades ago Gyárfás et al. observed, via a straightforward but unpublished argument, that this conjecture is equivalent to the problem of determining the maximum order of a 3-uniform τ-critical hypergraph. Consequently, an asymptotically tight upper bound for the maximum order of a 3-uniform τ-critical hypergraph follows from our recent work, reawakening interest in this equivalence. In this companion paper we supply a simple proof of this equivalence. We also present related background with open problems, and mention combinatorial geometry applications of the Szemerédi and Petruska conjecture.