Two problems on matchings in set families - In the footsteps of Erdos and Kleitman

摘要

The families, F-1,..., F-s subset of 2([n]) are called q-dependent if there are no pairwise disjoint F-1 is an element of F-1,..., F-s is an element of F-s satisfying vertical bar F-1 boolean OR...boolean OR F-s vertical bar <= q. We determine max vertical bar F-1 vertical bar+... +vertical bar F-s vertical bar for all values n >= q, s >= 2. The result provides a far-reaching generalization of an important classical result of Kleitman. The well-known Erdds Matching Conjecture suggests the largest size of a family. F subset of (([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 Erdos Matching Conjecture in a relatively wide range, in particular, for n >= (2+o(1))sk with o(1) depending on s only. This is a considerable improvement of a classical result due to Bollobas, Daykin and Erdds. We apply our results to advance in the following anti Ramsey -type problem, proposed by Ozkahya and Young. Let ar(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 ar(n, k, s) for all k >= 3 and n >= sk + (s - 1)(k - 1). Some other consequences of our results are presented as well. (C) 2019 Elsevier Inc. All rights reserved.