An asymptotic resolution of a conjecture of Szemerédi and Petruska

preprint2022arXivOpen access

Abstract

Consider a 33-uniform hypergraph of order nn with clique number kk such that the intersection of all its kk-cliques is empty. Szemerédi and Petruska proved n≤8m2+3mn\leq 8m^2+3m, for fixed m=n−km=n-k, and they conjectured the sharp bound n≤(m+22)n \leq {m+2 \choose 2}. This problem is known to be equivalent to determining the maximum order of a ττ-critical 33-uniform hypergraph with transversal number mm (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, n≤34m2+m+1n\leq \frac{3}{4}m^2+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+22)+O(m5/3)n\leq {m+2 \choose 2} + O(m^{{5}/{3}}), resolving the conjecture asymptotically.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.