TAILIEUCHUNG - Báo cáo toán học: "tability analysis for k-wise intersecting families"

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

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học