Abstract
Consider a -uniform hypergraph of order with clique number such that the intersection of all its -cliques is empty. Szemerédi and Petruska proved , for fixed , and they conjectured the sharp bound . This problem is known to be equivalent to determining the maximum order of a -critical -uniform hypergraph with transversal number (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, , 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 , resolving the conjecture asymptotically.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.