Multiply-intersecting families
Multiply-intersecting families
复制标题
多重相交族
DOI：
10.1016/0095-8956(91)90075-u
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
P. Frankl
中科院分区：
文献类型：
--
作者：
P. Frankl
交问题在有限集合论中占有重要地位。其中一个中心概念是r-方向t-相交族，即n元集合X的不同子集的集合F1，...，Fm，使得|F i l... F i r| ≥ t对1≤ i l<...< i r≤ m的所有选择成立。什么是最大的大小m= m（n，r，t）的r-明智的t-相交的家庭？取所有包含固定t元集的子集，表明m（n，r，t）≥ 2 n− t对所有n≥ t≥ 0成立。本文的主要结果之一是m（n，r，t）= 2 n− t成立当且仅当n< r+t或t≤ 2 r− r− 1，可能（但不太可能）的例外情况是（r，t）=（3，4）。获得了更多可能的最佳结果。另一个是下面的。假设G l，.，G r是交叉t-相交的（参见论文中的定义），且t≤ 2 r− r− 2，则|G 1|| G 2|·...·|G r| ≤ 2 r（n− t）。
Intersection problems occupy an important place in the theory of finite sets. One of the central notions is that of a r-wise t-intersecting family, that is, a collection F 1,…, F m of distinct subsets of the n-element set X such that| F i l ψ… ψF i r|≥ t holds for all choices of 1≤ i l<…< i r≤ m. What is the maximal size m= m (n, r, t) of a r-wise t-intersecting family? Taking all subsets containing a fixed t-element set shows that m (n, r, t)≥ 2 n− t holds for all n≥ t≥ 0. One of the main results of the paper is that m (n, r, t)= 2 n− t holds if and only if n< r+t or t≤ 2 r− r− 1 with the possible (but unlikely) exception of the case (r, t)=(3, 4). Many more best possible results are obtained. Another one is the following. Suppose that G l,…, G r are cross t-intersecting (see definition in the paper) and t≤ 2 r− r− 2, then| G 1|| G 2|·…·| G r|≤ 2 r (n− t).