Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Stability analysis for k-wise intersecting families. | Stability analysis for k-wise intersecting families Vikram Kamat School of Mathematical and Statistical Sciences Arizona State University Tempe Arizona 85287-1804 Submitted Oct 1 2010 Accepted May 3 2011 Published May 16 2011 Mathematics Subject Classification 05D05 Abstract We consider the following generalization of the seminal Erdos-Ko-Rado theorem due to Frankl 5 . For some k 2 let F be a k-wise intersecting family of r-subsets of an n element set X . for any F1 . Fk G F nk 1Fi 0. If r l n k then F n Ỉ . We prove a stability version of this theorem analogous to similar results of Dinur-Friedgut Keevash-Mubayi and others for the EKR theorem. The technique we use is a generalization of Katona s circle method initially employed by Keevash which uses expansion properties of a particular Cayley graph of the symmetric group. Key words. intersection theorems stability. 1 Introduction For a positive integer n let n 1 2 . n . For positive integers i and j with i j let i j i i 1 . j i j 0 if i j . Similarly let i j i 1 . j which is empty if i 1 j. The notations i j and i j are similarly defined. Let n be the family of all r-subsets of n . For F c n and v G n let F v F G F v G F called a star in F centered at v. A family F c n is called intersecting if for any A B G F A n B 0. Similarly call F c n k-wise intersecting if for any F1 . Fk G F nL Fi 0. Frankl 5 proved the following theorem for k-wise intersecting families. 7 n k 1 n Theorem Frankl . Let F c n be k-wise intersecting. If r ------------k---- then F n-i . I I r 1 It is trivial to note that the k 2 case of Theorem is the seminal Erdos-Ko-Rado theorem 4 . THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P115 1 Theorem Erdos-Ko-Rado . Let F c n be intersecting. If r n 2 then F n-i . kr-17 Stability The classical extremal problem is to determine the maximum size and structure of a family on a given ground set of size n which avoids a given forbidden configuration F. For example
