Two problems on matchings in set families - In the footsteps of Erdős and Kleitman
Two problems on matchings in set families - In the footsteps of Erdős and Kleitman
复制标题
DOI：
10.1016/j.jctb.2019.02.004
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
P. Frankl;A. Kupavskii
中科院分区：
文献类型：
--
作者：
P. Frankl;A. Kupavskii
如果不存在对不相交的F∈F 1，…，F s∈F s满足| F 1∪…∪F s|≤q，则称族F 1，…，F s∧2 [n]为q相关族。对于所有值n≥q， s≥2，我们求出max∈| F 1|+…+| F s|。该结果对Kleitman的一个重要经典结果进行了深远的推广。著名的Erdős匹配猜想（Matching Conjecture）提出了没有s对不相交集合的族F （[n] k）的最大大小。50多年后，它的全面解决方案仍然遥遥无期。本文给出了Erdős匹配猜想在较宽范围内的一个hilton - milner型稳定性定理，特别是当n≥(2+ o (1)) k且o(1)仅依赖于s时。由于Bollobás， Daykin和Erdős，这是对经典结果的相当大的改进。我们将我们的结果应用于Özkahya和Young提出的以下反拉姆齐型问题。设r （n, k, s）为颜色的最小数目x，使得在[n]的k元素子集的任何着色中，具有x（非空）颜色，存在大小为s的彩虹匹配，即s个不同颜色的集合成对不相交。我们证明了该问题的一个稳定性结果，该结果允许对所有k≥3和n≥s k+(s - 1)（k - 1）确定r （n, k, s）。本文还提出了我们研究结果的其他一些结果。
Abstract The families F 1,…, F s⊂ 2 [n] are called q-dependent if there are no pairwise disjoint F 1∈ F 1,…, F s∈ F s satisfying| F 1∪…∪ F s|≤ q. We determine max| F 1|+…+| F s| for all values n≥ q, s≥ 2. The result provides a far-reaching generalization of an important classical result of Kleitman. The well-known Erdős Matching Conjecture suggests the largest size of a family F⊂([n] k) with no s pairwise disjoint sets. After more than 50 years its full solution is still not in sight. In the present paper we provide a Hilton–Milner-type stability theorem for the Erdős Matching Conjecture in a relatively wide range, in particular, for n≥(2+ o (1)) s k with o (1) depending on s only. This is a considerable improvement of a classical result due to Bollobás, Daykin and Erdős. We apply our results to advance in the following anti-Ramsey-type problem, proposed by Özkahya and Young. Let a r (n, k, s) be the minimum number x of colors such that in any coloring of the k-element subsets of [n] with x (non-empty) colors there is a rainbow matching of size s, that is, s sets of different colors that are pairwise disjoint. We prove a stability result for the problem, which allows to determine a r (n, k, s) for all k≥ 3 and n≥ s k+(s− 1)(k− 1). Some other consequences of our results are presented as well.