Proof of a conjecture of Frankl and Füredi
type: Item
instance of: scholarly article
title: Proof of a conjecture of Frankl and Füredi
zbMATH Open document ID: 0882.05120
author: Gurumurthi V. Ramanan
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-02-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1076894
zbMATH Keywords: modular Ray-Chaudhuri-Wilson theorem
zbMATH Keywords: linear algebraic method
Wikidata QID: Q122917057
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
OpenAlex ID: W1981753242
cites work: Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems
cites work: A Note on Fisher's Inequality for Balanced Incomplete Block Designs
cites work: Erdös–Ko–Rado Theorem—22 Years Later
cites work: Q3770569
cites work: Q3693528
cites work: Intersection theorems with geometric consequences
cites work: An extension of a Frankl-Füredi theorem
cites work: Q5663904
cites work: A short proof of Fisher's inequality
cites work: An extension of a theorem of the Bruijn and Erdős on combinatorial designs
cites work: On generalizations of the deBruijn-Erdős theorem
cites work: On the decomposition ofkn into complete bipartite graphs
DOI: 10.1006/JCTA.1997.2774
description: scientific article; zbMATH DE number 1076894