The Erds–Ko–Rado Theorem for Integer Sequences.pdf

The Erd˝os–Ko–Rado Theorem for Integer Sequences Peter Frankl CNRS, ER 175 Combinatoire, 54 Bd Raspail, 75006 Paris, France Norihide Tokushige College of Education, Ryukyu University, Nishihara, Okinawa, 903-0213, Japan hide@edu.u-ryukyu.ac.jp Abstract For positive integers n, q, t we determine the maximum number of integer sequences (a , . . . , a ) which satisfy 1 ≤ a ≤ q for 1 ≤ i ≤ n, and any two 1 n i sequences agree in at least t positions. The result gives an affirmative answer to a conjecture of Frankl and F¨uredi. 1 Introduction Let n, q, t be positive integers with q ≥ 2, n ≥ t, and let [q] := {1, 2, . . . , q}. Then H ⊂ [q]n is a set of integer sequences (a , . . . , a ), 1 ≤ a ≤ q . We say that H is 1 n i t-intersecting if any two sequences intersects in at least t positions, more precisely, |{i : a = a }| ≥ t holds for all (a , . . . , a ), (a , . . . , a ) ∈ H. In this paper, we i i 1 n 1 n determine the exact value of the following function. f (n, q, t) := max{|H| : H ⊂ [q]n , H is t-intersecting}. [n] A family A ⊂ 2 is called t-intersecting if |A∩A | ≥ t holds for all A, A ∈ A. Define a weighted size of A by w (A) := A∈A (q − 1)n−|A |. Using a shifting technique, it is not difficult to check the following: Lemma 1 (Proposition