Set systems with few disjoint pairs
type: Item
instance of: scholarly article
title: Set systems with few disjoint pairs
zbMATH Open document ID: 1045.05083
author: Béla Bollobás
author: Imre Leader
published in: Combinatorica
publication date: 2004-09-08T00:00:00Z
review text: An old theorem of \textit{P. Frankl} [J. Comb. Theory, Ser. A 22, 249--251 (1977; Zbl 0363.05010)] and \textit{R. Ahlswede} [J. Comb. Theory, Ser. B 28, 164--167 (1980; Zbl 0441.05036)] states that any set system with at least \(\left | [n]^{\geq r} \right | \) elements has at least as many disjoint pairs as the set system \([n]^{\geq r}.\) This paper gives a new proof of this fact as well as a fairly good lower bound on the minimum number of disjoint pairs as a function of the size of a general system. The main tool of the proof is the new notion of a fractional set system.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 2099907
zbMATH Keywords: intersecting families
zbMATH Keywords: Kneser graph
zbMATH Keywords: Erdős-Ko-Rado theorem
zbMATH Keywords: fractional set system
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: s00493-003-0033-0
OpenAlex ID: W1985046307
Wikidata QID: Q105584600
DOI: 10.1007/S00493-003-0033-0
description: scientific article; zbMATH DE number 2099907