Sharp results concerning disjoint cross-intersecting families. (May 2020)

• Record Type: Journal Article
• Authors: Frankl, Peter; Kupavskii, Andrey
• Is Part Of: European journal of combinatorics. Volume 86(2020)
• Publication Date: 2020-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103089
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For an n -element set X let X k be the collection of all its k -subsets. Two families of sets A and B are called cross-intersecting if A ∩ B ≠ 0̸ holds for all A ∈ A, B ∈ B . Let f ( n, k ) denote the maximum of min { | A |, | B | } where the maximum is taken over all pairs of disjoint, cross-intersecting families A, B ⊂ [ n ] k . Let c = log 2 e . We prove that f ( n, k ) = 1 2 n − 1 k − 1 essentially iff n > c k 2 (cf. Theorem 1.4 for the exact statement). Let f ∗ ( n, k ) denote the same maximum under the additional restriction that the intersection of all members of both A and B are empty. For k ≥ 6 and n ≥ k 3 − k 2 we show that f ∗ ( n, k ) = 1 2 n − 1 k − 1 − n − 2 k k − 1 + 1 and the restriction on n is essentially sharp (cf. Theorem 1.5).