An Erdos-Ko-Rado theorem for cross t-intersecting families

作者：Frankl Peter^*; Lee Sang June; Siggers Mark; Tokushige Norihide

来源：Journal of Combinatorial Theory - Series A, 2014, 128: 207-249.

DOI：10.1016/j.jcta.2014.08.006

• Cross intersecting families
• Erdos Ko-Rado
• Shifting
• Random walks

Two families A and B, of k-subsets of an n-set, are cross t-intersecting if for every choice of subsets A is an element of A and B is an element of B we have |A boolean AND B| %26gt;= t. We address the following conjectured cross t-intersecting version of the Erdos-Ko-Rado theorem: For all n %26gt;= (t + 1)(k - t + 1) the maximum value of |A||B| for two cross t-intersecting families A, B subset of ([n] k) is (n-t k-t)(2). We verify this for all t %26gt;= 14 except finitely many n and k for each fixed t. Further, we prove uniqueness and stability results in these cases, showing, for instance, that the families reaching this bound are unique up to isomorphism. We also consider a p-weight version of the problem, which comes from the product measure on the power set of an n-set.

• 出版日期2014-11