Hypergraphs without a large star
type: Item
instance of: scholarly article
title: Hypergraphs without a large star
zbMATH Open document ID: 0569.05042
DOI: 10.1016/S0012-365X(85)80009-1
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Let r, t be positive integers; \({\mathcal F}^ a \)set system of rank r. The authors prove: If \(| {\mathcal F}| >\left( \begin{matrix} r+t\\ r\end{matrix} \right)\), then there exists \(F_ 0,...,F_{t+1}\in {\mathcal F}\) and points \(p_ 0,...,p_{t+1}\) which satisfy the conditions \(p_ i\in F_ i\) and \(p_ i\not\in F_ j\) for \(i\neq j\). (P. Frankl and J. Pach have conjectured that the analogous problem for r-graphs is in closed connection with the r uniform Turán's problem.) There exist a lot of non-isomorphic extremal set systems for this problem. The proof of the theorem above is made through the next, slightly stronger, Sauer-type theorem. If \({\mathcal F}\) is a set system of rank r, and \(| {\mathcal F}| >\left( \begin{matrix} r+t\\ r\end{matrix} \right)\) then there exists a set \(Y=\{y_ 1,...,y_{t+1}\}\) such that \(Y\cap F_ 0=\emptyset\) and \(Y\cap F_ i=\{y_ i\}\) if \(1\leq i\leq t+1\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3908478
zbMATH Keywords: stars in hypergraphs
zbMATH Keywords: r-uniform hypergraphs
zbMATH Keywords: Sauer theorem
zbMATH Keywords: Turán's problem
author: Zoltán Füredi
author: Zsolt Tuza
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: Properties of (0,1)-matrices with no triangles
cites work: Hypergraphs with no special cycles
cites work: On generalized graphs
cites work: Q3880849
cites work: An extremal problem for two families of sets
cites work: On the trace of finite sets
cites work: On disjointly representable sets
cites work: Q3222197
cites work: Covers in hypergraphs
cites work: On the density of families of sets
cites work: Helly-type hypergraphs and Sperner families
cites work: Q3708835
full work available at URL: s0012-365x(85)80009-1
OpenAlex ID: W2030713385
description: scientific article; zbMATH DE number 3908478