The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs (Q6166161): Difference between revisions

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.