Tomasz Luczak: On the chromatic number of generalized shift graphs

For natural numbers k and n, by G(n,delta_k) we denote the graph whose vertex set consists of all k-element subsets of {1,2,dots,n}, and two subsets A={a_1,a_2,...,a_k} and B={b_1,b_2,..., b_k} are adjacent if a_1 < a_2 < b_1 < a_3 < b_2 < a_4 < b_3 < ... < a_k < b_{k-1} < b_k,.

In the talk we try to estimate the chromatic number of G(n,delta_k).

This is a joint work with Christian Avart and Vojta Rödl.