tailieunhanh - Báo cáo toán học: "Independence Complexes of Stable Kneser Graphs"

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: Independence Complexes of Stable Kneser Graphs. | Independence Complexes of Stable Kneser Graphs Benjamin Braun Department of Mathematics University of Kentucky Lexington KY 40506 benj Submitted Nov 1 2010 Accepted May 10 2011 Published May 23 2011 Mathematics Subject Classification Primary 05C69 Secondary 57M15 Abstract For integers n 1 k 0 the stable Kneser graph SGn k also called the Schrijver graph has as vertex set the stable n-subsets of 2n k and as edges disjoint pairs of n-subsets where a stable n-subset is one that does not contain any 2-subset of the form i i 1 or 1 2n k . The stable Kneser graphs have been an interesting object of study since the late 1970 s when A. Schrijver determined that they are a vertex critical class of graphs with chromatic number k 2. This article contains a study of the independence complexes of SGn k for small values of n and k. Our contributions are two-fold first we prove that the homotopy type of the independence complex of SG2 k is a wedge of spheres of dimension two. Second we determine the homotopy types of the independence complexes of certain graphs related to SGn 2. 1 Introduction Let n 1 2 3 . n and consider the following family of graphs. Definition For each pair of integers n 1 k 0 the Kneser graph KGn k has as vertices the n-subsets of 2n k with edges defined by disjoint pairs of n-subsets. For the same parameters the stable Kneser graph SGntk also called the Schrijver graph is the subgraph of KGn k induced by the stable n-subsets of 2n k . those n-subsets that do not contain any 2-subset of the form i i 1 or 1 2n k . The author was partially supported by the NSF through award DMS-0758321. Thanks to the referees for their careful reading of the document. The author is particularly grateful to the anonymous referee who pointed out that Theorem can be proved using the contractible subcomplex approach given in the first proof. Thanks also to John Shareshian for thoughtful discussions at the beginning of this project. THE ELECTRONIC .

• 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