A bipartite Erdős-Ko-Rado theorem (Q2366030)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 223123
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A bipartite Erdős-Ko-Rado theorem |
scientific article; zbMATH DE number 223123 |
Statements
A bipartite Erdős-Ko-Rado theorem (English)
0 references
29 June 1993
0 references
This paper gives a new proof for the following result: Let \(F_ 1\) and \(F_ 2\) be nonvoid families on an \(n\)-element underlying set containing at most \(k\)-element (at least \((n-k)\)-element, resp.) subsets. Furthermore assume that \(F_ 1\cup F_ 2\) is inclusion free. Then \[ | F_ 1|+| F_ 2|\leq 1+{n\choose k}-{n-k\choose k}. \] (The extremal systems are described, as well.) This result is the well- known Hilton-Milner theorem [Q. J. Math., Oxf. II. Ser. 18, 369-384 (1967; Zbl 0168.262)] in a complemented form.
0 references
Erdős-Ko-Rado theorem
0 references
shifting technique
0 references
Hamiltonian cycle
0 references
Hilton- Milner theorem
0 references
0.8646037578582764
0 references
0.8374924063682556
0 references
0.8372015357017517
0 references
