The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform -critical hypergraphs
From MaRDI portal
Publication:6166161
DOI10.1007/S40879-023-00660-XzbMATH Open1528.05068arXiv2204.02859OpenAlexW4384698624WikidataQ123106455 ScholiaQ123106455MaRDI QIDQ6166161FDOQ6166161
Publication date: 2 August 2023
Published in: European Journal of Mathematics (Search for Journal in Brave)
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 -uniform -critical hypergraph. Consequently, an asymptotically tight upper bound for the maximum order of a -uniform -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.
Full work available at URL: https://arxiv.org/abs/2204.02859
Cites Work
- On generalized graphs
- Critical hypergraphs and interesting set-pair systems
- Title not available (Why is that?)
- A Theorem on k-Saturated Graphs
- Upper bound on the order of tau-critical hypergraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Petruska's question on planar convex sets
- The Szemerédi-Petruska conjecture for a few small values
- Eckhoff's problem on convex sets in the plane
- An asymptotic resolution of a conjecture of Szemerédi and Petruska
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)
