Proof of a conjecture of Frankl and Füredi (Q1369678): Difference between revisions

Let \(\mathcal F\) be a set system on the \(n\)-element underlying set \(X.\) This nice paper fully proves the well-known Frankl-Füredi conjecture: If \(1 \leq |E\cap F|\leq k\) holds for all pairs from \(\mathcal F\), then \[ |{\mathcal F}|\leq \sum_{i=0}^k{n-1 \choose i}. \] After several partial results by P. Frankl, Z. Füredi, L. Pyber, H. S. Snevily, etc., this paper solves completely the problem. The proof generalizes R. Palisse's linear algebraic method. The method is powerful enough to prove a more general version of the original conjecture, where the cardinalities of the pairwise intersections belong to an arbitrary but fixed \(k\)-element set of integers.