On a conjecture of Szemerédi and Petruska

2019/04/09 by Jobson, Adam S., Kézdy, André E., Pervenecki, Tim
#05C65 #05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1904.04921

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≤ 8m²+3m, for fixed m=n-k, and they conjectured the sharp bound n≤m+2\choose 2. Tuza proved the best known bound, n≤ (3)/(4)m²+m+1, using the machinery of τ-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≤ m² + 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.

Related

• An asymptotic resolution of a conjecture of Szemerédi and Petruska
• The Szemerédi-Petruska conjecture for a few small values
• The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform τ-critical hypergraphs
• The size of a hypergraph and its matching number
• New bounds on a generalization of Tuza's conjecture