Hypergraphs without a large star (Q1061141): Difference between revisions

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\).