Maximal intersecting family
From Wikipedia, the free encyclopedia
A maximal intersecting family(MIF) of k-sets (i.e., sets with cardinality k, where k is a natural number) is a family of sets Z satisfying the following:
- Every element of Z is a k-set.
- Every pair of elements of Z has a nonempty intersection.
- There exists no family of sets Y satisfying the above two conditions which is a proper superset of Z.
The last condition states that Z is the maximal set (with respect to set inclusion) satifying the first two conditions. A maximal intersecting family of k-sets is called a MIF(k).
An example of a MIF(2) is { {1,2}, {2,3}, {3,1} }. A general example of a MIF(k) is the set of all subsets of cardinality k of a given set of cardinality 2k-1.