Intersection statements for systems of sets
type: Item
instance of: scholarly article
title: Intersection statements for systems of sets
zbMATH Open document ID: 0883.05123
author: A. G. Meyer
author: Walter A. Deuber
author: David S. Gunderson
author: Alexandr Kostochka
author: P. Erdős
published in: Journal of Combinatorial Theory. Series A
publication date: 1997-11-25T00:00:00Z
review text: A collection of sets is called a \(\Delta\)-system if any two sets have the same intersection. Let \(f(k,r)\) be the least integer such that any collelction of \(f(k,r)\) \(k\)-element sets contains a \(\Delta\)-system consisting of \(r\) sets. \textit{P. Erdös} and \textit{R. Rado} [J. Lond. Math. Soc. 44, 467-479 (1969; Zbl 0172.29601)] proved that \((r-1)^k< f(k,r)< k!(r-1)^k\) and conjectured that \(f(k,r)<C^k\) for some constant \(C\). Erdös offered \$1000 for a proof or disproof of this for \(r=3\). The paper under review concerns a related problem. Let \(F(n,r)\) be the greatest integer such that there exists a collection of subsets of an \(n\)-element set which does not contain a \(\Delta\)-system consisting of \(r\) sets. \textit{P. Erdös} and \textit{E. Szemerédi} [J. Comb. Theory, Ser. A 24, 308-313 (1978; Zbl 0383.05002)] showed that \(F(n,3)<2^{n-\sqrt{n}/10}\) and \(F(n,r)>(1+c_r)^n\), where the constant \(c_r\to 1\) as \(r\to\infty\). The authors provide new lower bounds for \(F(n,r)\) which are constructive and improve the previous best probabilistic results. They also prove a new upper bound. Moreover, for certain \(n\) it is shown that \(F(n,3)\geq 1.551^{n-2}\).
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1076897
zbMATH Keywords: \(\Delta\)-system
reviewed by: Andrew Vince
MaRDI profile type: Publication
full work available at URL: jcta.1997.2778
OpenAlex ID: W2110313351
cites work: On set systems not containing delta systems
cites work: Intersection theorems for systems of sets
cites work: On finite \(\Delta\)-systems
cites work: On finite Delta-systems. II
cites work: Intersection theorems for systems of sets (III)
cites work: Intersection Theorems for Systems of Sets
cites work: Intersection Theorems for Systems of Sets (II)
cites work: Combinatorial properties of systems of sets
cites work: Forbidden Intersections
cites work: Q5689011
cites work: An intersection theorem for systems of sets
DOI: 10.1006/JCTA.1997.2778
description: scientific article; zbMATH DE number 1076897