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

DOI10.1016/J.DISC.2023.113469MaRDI QIDQ6041571zbMATH OpenOpenAlexWikidataFDO

Authors André E. Kézdy, Jeno Lehel

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.11573

zbMATH Keywords

hypergraphsextremal set theorytransversal number

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15) Extremal set theory (05D05)

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'edi and Petruska proved $nleq8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $nleqm+2choose2$. This problem is known to be equivalent to determining the maximum order of a $au$-critical $3$-uniform hypergraph with transversal number $m$ (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, $nleqfrac34m^2+m+1$, was obtained by Tuza using the machinery of $au$-critical hypergraphs. Here we propose an alternative approach, a combination of the iterative decomposition process introduced by Szemer'edi and Petruska with the skew version of Bollob'as's theorem on set pair systems. The new approach improves the bound to $nleqm+2choose2+O(m^{5/3})$, resolving the conjecture asymptotically.

Recommendations

• The Szemerédi-Petruska conjecture for a few small values
• Improved bounds on a generalization of Tuza's conjecture
• Asymptotic solution of a Turán-type problem
• Transversal numbers of uniform hypergraphs
• A generalization of Tuza's conjecture

Cites work

• scientific article; zbMATH DE number 3472051 (Why is no real title available?)
• An extremal problem for two families of sets
• Critical hypergraphs and interesting set-pair systems
• Intersection patterns of convex sets
• On generalized graphs
• The Szemerédi-Petruska conjecture for a few small values
• Upper bound on the order of tau-critical hypergraphs

Cited in

(4)

• An asymptotic resolution of a problem of Plesník
• The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs
• scientific article; zbMATH DE number 4173466 (Why is no real title available?)
• The Szemerédi-Petruska conjecture for a few small values

This page was built for publication: An asymptotic resolution of a conjecture of Szemerédi and Petruska

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041571)