The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform -critical hypergraphs

DOI10.1007/S40879-023-00660-XMaRDI QIDQ6166161zbMATH OpenOpenAlexWikidataFDO

Authors André E. Kézdy, Jeno Lehel

Publication date 2 August 2023

Published in European Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphsextremal set theory

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: Recently we asymptotically resolved the long-standing Szemer'edi and Petruska conjecture. Several decades ago Gy'arf'as et al. observed, via a straightforward but unpublished argument, that this conjecture is equivalent to the problem of determining the maximum order of a $3$-uniform $au$-critical hypergraph. Consequently, an asymptotically tight upper bound for the maximum order of a $3$-uniform $au$-critical hypergraph follows from our recent work, reawakening interest in this equivalence. In this companion paper we supply a simple proof of this equivalence. We also present related background with open problems, and mention combinatorial geometry applications of the Szemer'edi and Petruska conjecture.

Recommendations

• An asymptotic resolution of a conjecture of Szemerédi and Petruska
• The Szemerédi-Petruska conjecture for a few small values
• A short proof of Erdős' conjecture for triple systems
• On Erdős' extremal problem on matchings in hypergraphs
• scientific article; zbMATH DE number 736291

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 3472051 (Why is no real title available?)
• scientific article; zbMATH DE number 3333195 (Why is no real title available?)
• A Theorem on k-Saturated Graphs
• An asymptotic resolution of a conjecture of Szemerédi and Petruska
• Critical hypergraphs and interesting set-pair systems
• Eckhoff's problem on convex sets in the plane
• On generalized graphs
• Petruska's question on planar convex sets
• The Szemerédi-Petruska conjecture for a few small values
• Upper bound on the order of tau-critical hypergraphs

This page was built for publication: The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs

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