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

DOI10.1016/J.DISC.2023.113469zbMATH Open1515.05132arXiv2208.11573OpenAlexW4366607789WikidataQ123359761 ScholiaQ123359761MaRDI QIDQ6041571FDOQ6041571

Authors: André E. Kézdy, Jeno Lehel 

Publication date: 31 May 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

hypergraphsextremal set theorytransversal number

Mathematics Subject Classification ID

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

Cites Work

• On generalized graphs
• An extremal problem for two families of sets
• Intersection patterns of convex sets
• Critical hypergraphs and interesting set-pair systems
• Upper bound on the order of tau-critical hypergraphs
• Title not available (Why is that?)
• The Szemerédi-Petruska conjecture for a few small values

Cited In (4)

• Title not available (Why is that?)
• The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs
• An asymptotic resolution of a problem of Plesník
• 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)