Simplicial Complexes

From CanisiusmathWiki

Table of contents

1 Introduction

2 Definitions

3 The Kneser Conjecture

4 The Neighborhood Complex

5 The Hom-complex

6 Hom-complex construction using the poset

[edit]

Introduction

In 1978, Laszlo Lovasz used and developed certain types of simplicial complexes to prove Kneser's conjecture. He applied the conjecture to colorings and the chromatic number of graphs and consequently, his method led to the development of a new branch of mathematics: topological combinatorics. In this section, I will provide some background of the Kneser conjecture and give an overview of the Neighborhood and Hom complexes as used by Lovasz.

[edit]

Definitions

Coloring: For a graph $G$ , a proper coloring is a map from $V (G)$ into some finite set of colors such that no two adjacent vertices are assigned the same color.

Chromatic number: The smallest number of color classes in a graph coloring, denoted $χ(G)$

The illustrations below show show examples of graph colors. The image on the left is the complete bipartite graph $K 3,3$ whose chromatic number is 2, as is the chromatic number of all bipartite graphs. On the right is the Petersen graph which can be properly colored with three color classes.

Graph homomorphism: For two graphs $T$ and $G$ , a graph homomorphism from $T \to G$ is a map $\varphi : V(T) \to V(G)$ , such that if $x, y$ in $V (T)$ are connected by an edge, then $\varphi(x)$ and $\varphi(y)$ are also connected by an edge.

Graph homomorphisms from G to H are also often referred to as morphisms or mappings from G to H.

The chromatic number of a graph $G$ can also be understood as the smallest number $n$ such that there exists a graph homomorphism $f: G \to K_n$ where a complete graph $K n$ is defined as a graph with $n$ vertices, each of which is connected to every other vertex.

The figure below shows a graph morphism from $K 5,2$ to the complete graph $K 3$ which is the largest graph K_n for which the mapping is valid, thus proving the chromatic number to be 3.

Kneser graph: Let $n, k$ be positive integers, $n \geq 2k$ . A Kneser graph, $K n, k$ , is a graph whose vertices are the $k$ -subsets of ${1,..., n}$ and the edges are given by pairs of disjoint $k$ -sets. Any graph $K n, k$ has ${n \choose k}$ vertices each with regular degree ${n-k \choose k}.$ The graph $K 5,2$ shown below has 10 vertices, each represented by subsets of size 2 made of all the different possible combinations of the numbers {1,...,n}. Therefore, the graph $K 5,2$ illustrated below is a regular graph with 10 vertices, each of degree 3.

[Can show example of Kneser graphs: The Petersen graph and $K 7:3$ ]

[edit]

The Kneser Conjecture

Martin Kneser conjectured in 1955 whether the partitioning of the $n$ -element subsets of a $(2 n + k)$ -element set in such a way that the subsets contained in any fixed class are pairwise intersecting. He observed that it is easy to partition this family into $n - 2 k + 2$ classes $C_1 \cup C_2 \cup \cdots \cup C_{(n-2k+2)}$ such that no pair of $k$ -sets within one class is disjoint. Kneser conjectured that k+2 is the least possible number of classes that allow for a valid partition. This conjecture can be translated into graph theory in regards to graph colorings, as described below.

Kneser's conjecture: It is impossible to properly color a graph $K n, k$ graph with fewer than $n - 2 k + 2$ color classes.

Lovasz was able to prove Kneser's conjecture and showed that $n - 2 k + 2$ is not only a lower bound for the chromatic number of a Kneser graph, but it was shown that $χ(K n, k)$ actually does equal $n - 2 k + 2$ .

For example, it was shown above that the Petersen graph, $K 5,2$ , can be colored with three color classes. We can verify this is the lowest possible amount of coloring classes, $χ(G) = n - 2 k + 2 = 5 - 2(2) + 2 = 3.$

[edit]

The Neighborhood Complex

Traditionally, many proofs with applications in graph theory are generally done by considering their adjacency matrices. However, Lovasz's proof of the Kneser conjecture referred to other forms of graphs to prove the hypothesis-. Laszlo Lovasz invented the neighborhood complex, a type of simplicial complex, to be used in his proof of the conjecture. The neighborhood complex is defined as follows.

Neighborhood complex, $\mathcal{N}(G):$ A simplicial complex associated with a graph $G$ whose simplices are defined by sets of vertices that have a common neighbor in the graph.

The formation of the neighborhood complex can best be understood through an example.

Example:

$\mathcal{N}(G) = \{ \{{\emptyset}\},\{1\},\{2\},\{3\},\{4\},\{5\},\{1,2\},\{1,3\}, \{1,4\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{1,2,5\},\{1,3,4\}\}$

Inclusion maximal simplices: ${1,2,5},{1,3,4},{2,3}$

[edit]

The Hom-complex

Following his application of the neighborhood complex, Lovasz sought to develop a simplicial complex which would have more useful properties and applications. This led him to create the Hom-complex, defined as follows.

Hom-complex: A polyhedra complex whose cells are indexed by all functions $\eta: V(T) \to 2^{V(G)}\backslash{\{\emptyset}\},$ such that if $(x,y) \in E(T)$ , then $\eta(x) \times \eta(y) \subseteq E(G).$ The closure of a cell $η$ consists of all cells indexed by $\tilde{\eta} : V(T) \rightarrow 2^{V(G)}\backslash{\{\emptyset}\}$ , which satisfy $\tilde{\eta}(v) \subseteq \eta(v)$ .

More simply, the Hom-complex of graphs G and H, Hom $(G, H)$ , can be thought of as the simplicial complex whose vertices are all the homomorphisms from G to H. Although the construction of the Hom-complex is different from that of the Neighborhood complex, particularly because the former depends on two parameters, the polyhedral complex Hom $(K 2, G)$ turned out to be homotopy equivalent to the simplicial complex $N (G)$ The vertices of a simplicial complex are also called the 0-skeleton, the faces are referred to as the 1-skeleton, triangular faces as the 2-skeleton, and so forth. An example of the construction of the Hom-complex for the graphs $K 2$ and $K 3$ is shown below.

[edit]

Hom-complex construction using the poset

While creating the Hom-complex of small graphs is quite simple, constructing the Hom-complex of more elaborate graphs quickly becomes much more complicated. Thus it is often very helpful to use an intermediary step as opposed to going from the initial graphs immediately to their Hom-complex. This method helps to breakdown the process of creating the Hom-complex into first finding the vertices, which are simply all of the homomorphisms from the first graph to the second and then outlining the 1-skeleton by connecting the appropriate vertices. The 2-skeleton is then represented by connecting the relevant elements of the 1-skeleton and so forth. This method breaks down all of the faces of the simplicial complex determined by the poset.

The face poset, $P (K)$ , of a simplicial complex $K$ is the poset $P (K)$ , which is the set of all nonempty simplicies of K ordered by inclusion. An example of $H o m (L 3, K 3)$ illustrating this method follows.