Set systems with few disjoint pairs (Q1878795): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q105584600, #quickstatements; #temporary_batch_1711055989931 |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-003-0033-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1985046307 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q105584600 / rank | |||
Normal rank |
Latest revision as of 00:48, 22 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