|
11:50 am, Seminar Hall Exact homotopy type of certain graph complexes Anurag Singh IIT Kanpur. 30-01-18 Abstract 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$.
|
