Counterexample to the Frankl-Pach conjecture for uniform, dense families (Q1382415): Difference between revisions

A family \(\mathcal F\) is a set of subsets of \(\{1,\dots,n\}\). It is \(l\)-uniform if for all \(F \in {\mathcal F}\) holds that \(|F|=l\), while it is \(l\)-dense if there is a \(D \subset \{1,\dots,n\}\) such that \(|D|=l\) and \(|\{F \cap D:F \in {\mathcal F}\}|=2^n\). Frankl and Pach showed earlier that if \(|{\mathcal F}|> {n \choose l-1}\) for an \(l\)-uniform family \(\mathcal F\), then \(\mathcal F\) is also \(l\)-dense. They conjectured that for every \(l\)-uniform, but not \(l\)-dense family \(\mathcal F\) the inequality \(|{\mathcal F}|\leq {n-1 \choose l-1}\) holds. The authors give a simple counterexample which shows the conjecture is false. The example also disproves a conjecture of Frankl and Watanabe (for \(n>k>l>2\)), which states that for every \(k\)-uniform, but not \(l\)-dense family \(\mathcal F\) the inequality \(|{\mathcal F}|\leq {n-k+l-1 \choose l-1}\) holds when \(n>n_0(k)\).