Cross-intersecting subfamilies of levels of hereditary families

Abstract

A set A t-intersects a set B if A and B have at least t common elements. Families A1,A2, . . . ,Ak of sets are cross-t-intersecting if, for every i and j in {1, 2, . . . , k} with i ̸= j, each set in Ai t-intersects each set in Aj. An active problem in extremal set theory is to determine, for a given finite family F, the structure of k cross-t-intersecting subfamilies whose sum of sizes is largest. For a family H, the rth level H(r) of H is the family of sets in H of size r, and, for s ≤ r, H(s) is called a (≤ r)-level of H. We solve the problem for any union F of (≤ r)-levels of any union H of power sets of sets whose sizes are at least a certain integer n0, where n0 is independent of H and k but depends on r and t (dependence on r is inevitable, but dependence on t can be avoided). We show that there are only two possible optimal configurations. We also prove generalizations, whereby A1,A2, . . . ,Ak are not necessarily contained in the same union of levels. Erdős–Ko–Rado-type results follow, particularly the author’s analogous result for t-intersecting subfamilies of F. The problem for a level of a power set was solved for t = 1 by Hilton in 1977, and for any t by Wang and Zhang in 2011. This work draws inspiration from the Chvátal Conjecture and the Holroyd–Talbot Conjecture.