Combinatorics Seminar

When: Sunday, December 15, 10am Where: Schreiber 309 Speaker: Tomasz Luczak, Adam Mickiewicz University at Poznan Title: On the chromatic number of generalized shift graphs

Abstract:

We study the chromatic number of graphs whose vertices are k-subsets of {1,2,..., n}, and two vertices a_1< a_2< ...< a_k and b_1 < b_2 < ... < b_k are adjacent if they interlace with each other according to some given pattern, such as a_1 < a_2 < b_1 < a_3 < b_4 < ... < a_{k-1} < b_{k-2} < a_k < b_{k-1} < b_k. It is shown that the chromatic number of such graph grows roughly as the iterated logarithm log_{(r)}n, where r=r(k) is a linear function of k.

This is a joint work with Christian Avart and Vojtech Rodl.