Chennai Mathematical Institute


11:50 am, Seminar Hall
Exact homotopy type of certain graph complexes

Anurag Singh
IIT Kanpur.


One of the classical problems in graph theory is the computation of the chromatic number, which finds applications in several areas. In 1955, Martin Kneser posed a conjecture regarding the partitioning of $n$- subsets of $(2n+k)$ element set. In 1978, Lov{\'a}sz proved the graph theoretic version of this conjecture by defining the Kneser graphs, $KG_{n,k}$. In this proof, he introduced a simplicial complex, called the neighborhood complex of graph.

In the same year, A. Schrijver identified a family of vertex critical subgraphs of the kneser graphs, called the stable Kneser graph $SG_{n,k}$. In 2003, Bj{\"o}rner and Longueville proved that the neighborhood complex of stable Kneser graph, $SG_{n,k}$ is homotopy equivalent to the $k$-dimensional sphere. In this talk, I will discuss the exact homotopy type of neighborhood complexes of Kneser graphs, $KG_{n,k}$ for $n=2$ and $3$ using some tools from discrete Morse theory.

Lov{\'a}sz further generalised the notion of neighborhood complex by defining a polyhedral complex called the Hom complex for any pair of graphs $G$ and $H$. For a fixed graph $T$ and a simplicial complex $X$, Dochtermann constructed a graph $G_{k,X}$ such that $diam(T) \leq 2^{k-1}-1$ and proved that $Hom(T,G_{k,X})\simeq X.$ He further conjectured that if $diam(T)=1$ then $Hom(T,G_{1,X})\simeq X$. I will present a combinatorial proof of this conjecture.

Another important complex associated to a graph is the independence complex, which has many applications in netework analysis and statictical mechanics. We will see the exact homotopy type of independence complex of Kneser graphs, $KG_{2,k}$ and $KG_{3,\ell}$ for $\ell <5$.