turkmath.org

A generalized Kneser graph with parameters n, k, d is a graph whose vertices are all k-subsets of a set with n elements and there is an edge between two vertices if their corresponding subsets' intersection has less than d elements. The case d=1 is the classical Kneser graph whose chromatic number was computed via topological methods by Lovasz. For d>1 very little is known about the chromatic number. In this talk we present methods that provide lower and upper bounds for the chromatic number of generalized Kneser graphs. In the process, we find surprising connections to the block designs and the Hadamard matrices. This is a report on a joint work with Alipour and Moghaddam.