Minimum degree and diversity in intersecting antichains
- PDF / 286,517 Bytes
- 11 Pages / 476.22 x 680.315 pts Page_size
- 81 Downloads / 224 Views
DOI: 1 0
MINIMUM DEGREE AND DIVERSITY IN INTERSECTING ANTICHAINS P. FRANKL Alfr´ ed R´ enyi Institute of Mathematics, Re´ altanoda u. 13-15, H-1953 Budapest, Hungary e-mail: [email protected] (Received May 7, 2020; revised July 27, 2020; accepted July 30, 2020)
Abstract. Let n, be positive integers, n > 2 + 1. Let X be an n-element os conjectured that set and F an antichain, F ⊂ 2X . Kiselev, Kupavskii and Patk´ if |F ∪ G| ≤ 2 + 1 for all F, G ∈ F then the minimum degree of F is no more than [n] n−1 , the minimum degree of . We prove this conjecture for n ≥ 3 + 2 + 32 −1 and solve the analogous problem for the case |F ∩ G| ≥ t.
1. Introduction Let n > t > 0 be integers and let [n] = {1, 2, . . . , n} be the standard n element set. Let 2[n] be the power set and [n] k the collection of all k-element subsets of [n]. A family F ⊂ 2[n] is called t-intersecting if |F ∩ F | ≥ t holds for all F, F ∈ F . A family F of subsets is called an antichain if there are no distinct F, F ∈ F satisfying F ⊂ F . For a family F ⊂ 2[n] and i ∈ [n] define F (i) = F \ {i} : i ∈ F ∈ F , F (i) = F : i ∈ F ∈ F . Note that |F | = |F (i)| + |F (i)|. Definition 1.1. Let δ(F ) := min |F (i)| be the minimum degree of F i∈[n]
and γ(F ) := min |F (i)| be the diversity of F . Recently these two quantities have received quite some attention (cf. [9], [16], [13], [14], [8], [5], [6] or [7]). In particular, Kiselev, Kupavskii and Patk´ os [15] proved the following Research partially supported by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926. Key words and phrases: extremal problem, finite set, antichain, minimum degree. Mathematics Subject Classification: primary 05D05, secondary 05C35.
0236-5294/$20.00 © 2020 Akade ´miai Kiado ´, Budapest, Hungary
2
P. FRANKL
Theorem 1.2 [15]. Suppose that F ⊂ 2[n] is a t-intersecting antichain and n + t = 2k is even. Then n−1 [n] (1.1) γ(F ) ≤ with equality holding iff F = . k k They made the analogous conjecture for n + t odd. Conjecture 1.3 [15]. Suppose that n + t = 2k + 1 is odd. Let F ⊂ 2[n] be a t-intersecting antichain. Then n−1 . (1.2) γ(F ) ≤ k+1 [n] Note that M = k+1 shows that, if true, (1.2) is best possible. However, as it is pointed out by [15], there are other, more complex examples achieving equality in (1.2). The dual notion of t-intersecting is that of (n − t)-union. A family G ⊂ 2[n] is called s-union if |G ∪ G | ≤ s for all G, G ∈ G. For F ⊂ 2[n] define the dual family F c = {[n] \ F : F ∈ F }. ⊂ 2[n] . Then Observation Suppose that F 1.4. c c (i) |F (i)| = F (i) , F (i) = F (i) , γ(F ) = δ(F c ), δ(F ) = γ(F c ), (ii) F is t-intersecting iff F c is (n − t)-union, (iii) F is an antichain iff F c is an antichain. In view of Observation 1.4 one can reformulate Conjecture 1.3 in the following way. Conjecture 1.5. Suppose that 1 ≤ 2 + 1 < n, F ⊂ 2[n] is a (2 + 1)union antichain. Then n−1 [n] (1.3) δ(F ) ≤ =δ . −1 The aim of the present paper
Data Loading...
