Counterexample to the Frankl-Pach conjecture for uniform, dense families
type: Item
instance of: scholarly article
title: Counterexample to the Frankl-Pach conjecture for uniform, dense families
zbMATH Open document ID: 0886.05109
DOI: 10.1007/BF01200912
published in: Combinatorica
publication date: 1998-03-26T00:00:00Z
review text: 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)\).
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1134682
zbMATH Keywords: hypergraphs
zbMATH Keywords: uniform families
zbMATH Keywords: dense families
author: Levon H. Khachatrian
author: Rudolf Ahlswede
MaRDI profile type: Publication
Wikidata QID: Q123281023
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: On disjointly representable sets
cites work: Density results for uniform families
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
full work available at URL: https://doi.org/10.1007/bf01200912
OpenAlex ID: W1964675587
description: scientific article; zbMATH DE number 1134682