Intersecting families in $$\left( {\begin{array}{c}{[m]}\\ \ell \end{array}}\right) \cup \left( {\begin{array}{c}{[n]}\\
- PDF / 260,707 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 165 Views
Intersecting families in
[m]
∪
[n] k
Jun Wang1 · Huajun Zhang2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let m, n, and k be positive integers with = k, n > m < 2 and 2k, [n] ∪ , then n = max{m, n} ≥ + k. If F is an intersecting family in [m] k |F| ≤ max
m−1 n−1 m , + . −1 k−1
n−1 Unless n = + k ≥ m, equality holds if and only if m−1 ≥ k−1 and F = [m] n−1 [m] [n] or m−1 ≤ and F consists of all members of ∪ that contain a fixed k−1 k element of [m] ∩ [n]. Keywords Family of sets · Intersecting family · Erd˝os–Ko–Rado theorem
1 Introduction A family A of sets is intersecting if A ∩ B = ∅ for every pair A, B ∈ A. Given a finite set X , let Xk denote the set of all k-subsets of X . For a positive integer n, let [n] denote the set {1, . . . , n}. We are interested in the intersecting families F’s in [n] k . [n] [n] Here, “F in k ” means that F is a subfamily of k . A maximum intersecting family is an intersecting family of the largest size. Note that [n] k is intersecting if n 2k, this problem is nontrivial and was solved by os et al. (1961). Their n−1 pioneering result states if F is an intersecting family in Erd˝ [n] , then |F| ≤ k k−1 subject to n ≥ 2k, and except for n = 2k, equality implies that all members of F contain a fixed element. Such an intersecting family is said to be a star, or a t-star if the fixed element t needs to be indicated. This theorem was reproved many times, and initiated a new field of combinatorial set theory. The reader is referred to Deza and Frankl (1983), Frankl (1987), and Borg (2011) for surveys on relevant results. As a generalization of the Erd˝os–Ko–Rado theorem, Frankl (1996) determined the maximum intersecting families in the direct product
Xm X1 × ··· × , k1 km
where X 1 , . . . , X m are pairwise disjoint sets with |X i | ≥ 2ki . Recently, we generalized the result in Frankl (1996) to X 1 Xm × ··· × , kσ (1) kσ (m)
σ ∈Sm
which was called the symmetric union of direct products of set families in Wang and Zhang (2018). Motivated [n] by the above results, in this paper, we investigate the intersecting families in [m] positive integers with = k. Let F be a maximum ∪ k , where m,n, andk are [n] intersecting family in [m] ∪ , and write F1 = F ∩ [m] and F2 = F ∩ [n] k k . [m] [n] Suppose n < 2k and m < 2. Clearly, ∪ k is an intersecting family if m, n < k + , so we may assume max{n, m} ≥ k + . In this case, k > n = and m < k + ≤ n. Then m < n ≤ nk , and F1 and F2 can be regarded as [n] cross-intersecting families in [n] ∪ k , that is, each A ∈ F1 intersects each B ∈ F2 . By Theorem 1 in Frankl and Tohushige (1992) or Wang and Zhang (2013), we have that |F| < nk if F1 = ∅ and F2 = ∅. Therefore, |F| ≤ nk , and equality implies F = [n] k . Therefore, we always assume that n ≥ 2k or m ≥ 2. Of course, if both inequalities hold, the question has been answered by th
Data Loading...
