On the Maximum of the Sum of the Sizes of Non-trivial Cross-Intersecting Families

Let n >= 2k >= 4 be integers, (([n])(k)) the collection of k-subsets of [n] = {1,..., n}. Two families F, G subset of (([n])(k)) are said to be cross-intersecting if F boolean AND G not equal empty set for all F is an element of F and G is an element of G. A family is called non-trivial if the intersection of all its members is empty. The best possible bound vertical bar F vertical bar + vertical bar G vertical bar <= ((n)(k)) - 2((n-k)(k)) + ((n-2k)(k)) + 2 is established under the assumption that F and G are non-trivial and cross-intersecting. For the proof a strengthened version of the so-called shifting technique is introduced. The most general result is Theorem 4.1.