Set systems with few disjoint pairs (Q1878795): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:02, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Set systems with few disjoint pairs |
scientific article |
Statements
Set systems with few disjoint pairs (English)
0 references
8 September 2004
0 references
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.
0 references
intersecting families
0 references
Kneser graph
0 references
Erdős-Ko-Rado theorem
0 references
fractional set system
0 references