The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs (Q6166161): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q123106455, #quickstatements; #temporary_batch_1721950759712 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q123106455 / rank | |||
Normal rank |
Revision as of 00:57, 27 July 2024
scientific article; zbMATH DE number 7721445
Language | Label | Description | Also known as |
---|---|---|---|
English | The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs |
scientific article; zbMATH DE number 7721445 |
Statements
The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs (English)
0 references
2 August 2023
0 references
In this article, the authors establish a correspondence between the maximum number of vertices of 3-uniform \(\tau\)-critical hypergraphs and the Szemerédi-Petruska conjecture [\textit{E. Szemerédi} and \textit{G. Petruska}, Stud. Sci. Math. Hung. 7, 363--374 (1973; Zbl 0302.05002)]. \textit{A. Gyarfas} et al. [J. Comb. Theory, Ser. B 33, 161--165 (1982; Zbl 0498.05050)] had already observed, via a straightforward but unpublished argument, this equivalence. The authors also present open problems, and applications of the Szemerédi-Petruska conjecture to combinatorial geometry. A hypergraph \(H=(V,E)\) is \(\tau\)-critical if it has no isolated vertices (that is, every vertex belongs to some edge) and \(\tau(H-e)=\tau(H)-1\), where \(H-e\) is the partial hypergraph with vertex set \(V\) and edge set \(E\setminus{e}\). An \(r\)-uniform hypergraph \(H\) on \(n\) vertices is defined to be an \(r\)-uniform \((n,k)\)-witness hypergraph provided its clique number \(\omega(H)=k\) and the \(k\)-cliques of \(H\) have no common vertex. The Szemerédi and Petruska conjecture [loc. cit.] states that, in terms of \(m=n-k\), the maximum number of vertices of a \(3\)-uniform \((n,k)\)-witness hypergraph is \(\binom{m+2}{2}\). Note that in particular, in the case \(r=2\) the order of an \((n, k)\)-witness graph is at most \(2m\) by the Hajnal-Folkmann lemma.
0 references
extremal set theory
0 references
hypergraphs
0 references