Premium
An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
Author(s) -
Hilton A. J. W.
Publication year - 1977
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-15.3.369
Subject(s) - intersection (aeronautics) , reading (process) , citation , set (abstract data type) , computer science , information retrieval , mathematics , combinatorics , library science , discrete mathematics , engineering , linguistics , programming language , philosophy , aerospace engineering
In this note we prove the following theorem. THEOREM 1. Let k, t #s 1. Let s/ t = {A n , A t2 A lrt } be sets of subsets of {1, ..., m}, where U U r t), A hh * 0 (l < 'i < h < U l < h < r «i (C)' if m/k ^ t, bounds are best possible. If t ^ 2, a/?rf m ^ 2k when t = 2, and r x ^ ... ^ r f and (m\ there is equality in the bounds then either i\ = I I, r 2 = ... = r t = 0 if m/k ^ /, or \ k J (m-\ \ r, = ... =r t =y k \ if m/k I m\ Of course the bound I 1 corresponds to the case when j / t (say) consists of lm-\ \ all ^-subsets of {1, ..., m). To obtain r x +... +r t = t j 1 is also simple: for each \k~\ I i, 1 ^ i ^ /, we let J/,-consist of all A>subsets of {1,..., m} which contain the element 1. There is no ambiguity in the statement of the theorem when m/k — t, for the two bounds then have the same value. When / = 1 the theorem is trivially true, so we shall henceforth assume that t ^ 2. The Erdos-Ko-Rado theorem [3] is a consequence of this theorem [take t ^ m/k and let s# x = ... =s/ t ]. First we explain the fundamental structural ideas which give rise to the theorem.