The chromatic number of finite type-graphs

详细信息    查看全文

• 作者：Christian Avart^a ; ^{christian.avart@otosense.com} ; Bill Kay^b ; ¹ ; ^{bill.w.kay@gmail.com} ; Christian Reiher^c ; ^{Christian.Reiher@uni-hamburg.de} ; Vojtěch Rö ; dl^b ; ² ; ^{rodl@mathcs.emory.edu}
• 关键词：Shift graphs ; Type-graphs ; Chromatic number ; Order types of pairs
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：877-896
• 全文大小：408 K
• 卷排序：122

文摘

By a finite type-graph we mean a graph whose set of vertices is the set of all k  -subsets of [n]={1,2,…,n}[n]={1,2,…,n} for some integers n≥k≥1n≥k≥1, and in which two such sets are adjacent if and only if they realise a certain order type specified in advance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz Łuczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.