Premium
An Extremal Set‐Intersection Theorem
Author(s) -
Chvátal V.
Publication year - 1974
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-9.2.355
Subject(s) - intersection (aeronautics) , element (criminal law) , combinatorics , set (abstract data type) , mathematics , point (geometry) , discrete mathematics , computer science , geometry , geography , political science , law , programming language , cartography
Let S be a set with n elements and F a set of k ‐point subsets of S , n ⩾ k + 1 ⩾ 5. If | F |> (n − 1k − 1)then there is a subset G = { X l , X 2 , .., X k } of F such that, for each i , all the k −1 sets in G —{ X 1 } have at least one element in common but all the k sets in G have no element in common.