论文标题
在erdős-ko-rado型定理的逆问题上
On an inverse problem of the Erdős-Ko-Rado type theorems
论文作者
论文摘要
子集$ \ Mathcal {f} \ subseteq {[n] \选择k} $的家族称为相交，如果其两个成员共享一个共同的元素。考虑一个相交的家族，直接问题是确定其最大尺寸，而反问题是表征其极端结构和相应的稳定性。著名的Erdős-Ko-Rado定理回答了直接问题和反面问题，并带领研究有限集的交叉路口问题的时代。 在本文中，我们考虑以下定量交叉问题，可以将其视为eRdős-ko-rado type定理的一个反问题：对于$ \ mathcal {f} \ subseteq {[n] \ subseteq {[n] \ select k} $ $ \ MATHCAL {i}（\ MATHCAL {F}）= \ sum_ {f_1，f_2 \ in \ Mathcal {f}} | f_1 \ cap f_2 | $。那么，当$ {[n] \选择K k} $具有相同家庭规模的所有家庭之间具有最大的总交点时，$ \ Mathcal {f} $的结构是什么？ 使用纯组合方法，我们提供了两个具有给定尺寸的最佳家族的结构特征，从而最大化了总交叉点。结果，对于$ n $足够大，$ \ mathcal {f} $适当的尺寸，这些特征表明，最佳家族$ \ mathcal {f} $的确确实是$ t $ - intersecting（$ t \ t \ geq 1 $）。在一定程度上，这揭示了相交的特性与最大化总相交之间的关系。另外，我们在$ \ Mathcal {i}（\ Mathcal {f}）$上提供了一个上限，用于$ | \ Mathcal {f} | $的几个范围，并确定具有某些值大小的家庭的独特最佳结构。
A family of subsets $\mathcal{F}\subseteq {[n]\choose k}$ is called intersecting if any two of its members share a common element. Consider an intersecting family, a direct problem is to determine its maximal size and the inverse problem is to characterize its extremal structure and its corresponding stability. The famous Erdős-Ko-Rado theorem answered both direct and inverse problems and led the era of studying intersection problems for finite sets. In this paper, we consider the following quantitative intersection problem which can be viewed an inverse problem for Erdős-Ko-Rado type theorems: For $\mathcal{F}\subseteq {[n]\choose k}$, define its \emph{total intersection} as $\mathcal{I}(\mathcal{F})=\sum_{F_1,F_2\in \mathcal{F}}|F_1\cap F_2|$. Then, what is the structure of $\mathcal{F}$ when it has the maximal total intersection among all families in ${[n]\choose k}$ with the same family size? Using a pure combinatorial approach, we provide two structural characterizations of the optimal family of given size that maximizes the total intersection. As a consequence, for $n$ large enough and $\mathcal{F}$ of proper size, these characterizations show that the optimal family $\mathcal{F}$ is indeed $t$-intersecting ($t\geq 1$). To a certain extent, this reveals the relationship between properties of being intersecting and maximizing the total intersection. Also, we provide an upper bound on $\mathcal{I}(\mathcal{F})$ for several ranges of $|\mathcal{F}|$ and determine the unique optimal structure for families with sizes of certain values.
