Maximal s-Wise t-Intersecting Families of Sets: Kernels, Generating Sets, and Enumeration

摘要

A family A of k-subsets of an n-set is said to be s-wise t-intersecting if |A_1 intersect ... intersect A_s| >= t, for any A_1, ..., A_s implied by A. For fixed s, n, k, and t, let I~s(n, k, t) denote the set of all such families. A family A implied by I~s(n, k, t) is said to be maximal if it is not properly contained in any other family in I~s(n, k, t). We show that for fixed s, k, t, there is an integer n_0 = n_0(k, s, t), for which the maximal families in I~s(n_0, k, t) completely determine the maximal families in I~s(n, k, t), for all n >= n_0. We give a construction for maximal families in I~s(n + 1, k + 1, t + 1) based on those in I~s(n, k, t). Finally, for s = 2, we classify the maximal families for k = t + 1, n >= t + 2, t >= 1, and for k = t + 2, n >= t + 6, t >= 1. The concepts of kernels and generating sets of a family of subsets play an important role in this work.