Is every abstract simplicial complex the independence complex of a simple graph?

124 Views Asked by At

Given a simple (no loops, no multi-edges) undirected graph $G$ on $n$-vertices, one can assign an abstract simplicial complex known as the independence complex (https://en.m.wikipedia.org/wiki/Independence_complex) on $n$-vertices whose faces are exactly the independent sets of the graph $G$.

My question is: Is every abstract simplicial complex the independence complex of a simple graph?

2

There are 2 best solutions below

0
On BEST ANSWER

If $X$ is a subset of the vertex set of a graph and if every $2$-element subset of $X$ is independent, then $X$ itself is independent. So the simplicial complex consisting of all the $\leq2$-element subsets of $\{1,2,3\}$ is not the independence complex of any graph.

3
On

As @AndreasBlass said, this is not true because whenever all the 2-faces of a simplex are present in the complex, the the simplex itself is present. This is a characterization of the clique complexes. And actually, the independence complex of a graph $G$ is the clique complex of the complement of $G$, so this makes sense.