Proof of a conjecture of Frankl and Füredi (Q1369678)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Proof of a conjecture of Frankl and Füredi |
scientific article |
Statements
Proof of a conjecture of Frankl and Füredi (English)
0 references
1 February 1998
0 references
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.
0 references
modular Ray-Chaudhuri-Wilson theorem
0 references
linear algebraic method
0 references