8
$\begingroup$

Let $G$ be a finite simple graph and let $C(G)$ be the flag complex associated to $G$ (the set of vertices of $C(G)$ is the vertex set of $G$ and the set of all cliques of $G$ are its simplexes).

Are there characterizations of contractibility of $C(G)$ ONLY in terms of the graph theoretical properties of $G$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Suppose you have a graph G and we know that the flag complex C(G) is contractible. Pick a clique K inside G and define H to be the graph given by 'taking the cone' over K, so adding an extra vertex v and adding edges (v,k) for each k in K. Then C(H) is still contractible. My guess is that any G with C(G) contractible can always be built by repeatedly taking cones over subcliques. I think this counts as a graph theoretic condition. Can anyone verify my guess? $\endgroup$
    – James Griffin
    Commented Jan 27, 2012 at 12:21
  • $\begingroup$ Also, if $G$ is any tree, then $C(G) = G$ and is contractible. I'm having trouble thinking of a good class of graphs that contains trees and is closed under coning. $\endgroup$
    – David E Speyer
    Commented Jan 27, 2012 at 12:26
  • $\begingroup$ Actually, James comment undersells the situation. Let $G$ be any graph, whether or not $C(G)$ is contractible, and let $H$ be the cone on $G$. Then $C(H)$ is the cone on $C(G)$, and hence contractible. $\endgroup$
    – David E Speyer
    Commented Jan 27, 2012 at 12:28

2 Answers 2

Reset to default
6
$\begingroup$

It is known that every induced subcomplex of the flag complex of a graph is contractible iff the graph is chordal (no induced cycles of length 4 or more). I doubt a necessary and sufficient condition that is purely graph theoretic for contractibility of just the flag complex is possible because the barycentric subdivision of any simplicial complex is a flag complex.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Chordal graphs are exactly those obtained by coning over cliques as James says. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 27, 2012 at 12:59
  • $\begingroup$ And chordal graphs also have several other characterizations... See e.g. en.wikipedia.org/wiki/Chordal_graph $\endgroup$
    – Russ Woodroofe
    Commented Jan 27, 2012 at 14:09
  • $\begingroup$ Do you have a reference of that result? $\endgroup$
    – María
    Commented Feb 27, 2019 at 15:06
  • 1
    $\begingroup$ @María, we give a proof in Proposition 4.8 of arxiv.org/pdf/1205.1159.pdf, it is essentially folklore and you can find it some form or the other in the references of our paper. $\endgroup$
    – Benjamin Steinberg
    Commented Feb 27, 2019 at 16:52
5
$\begingroup$

A nice graph theory lemma for showing homotopy equivalence that builds on the "clique starring" already discussed is stated as Lemma 3.2 of Alexander Engström's paper arXiv:math/0508148. I'll rephrase in terms of the language the question was asked in (clique complexes rather than independence complexes).

Lemma: If $v$ and $w$ are vertices of a graph $G$ with $N[v] \subseteq N[w]$, then $C(G)$ is homotopy equivalent to $C(G \setminus v)$.
(Here $N[v]$ is the closed neighborhood of $v$, i.e., $v$ and all its neighbors.)

The proof technique is that of elementary collapses. See http://en.wikipedia.org/wiki/Collapse_(topology).
Even if the lemma of Engström doesn't give you what you need, the broader technique of collapsing can be quite useful. Collapses are the "engine" of discrete Morse theory, for example.
It's not too hard to write a computer program (or some are available) that does automatic collapsing, and you could generate a large number of examples this way. If you can collapse a complex to a point, then the complex is contractible. The converse is not true, but the program might at least give you a smaller complex to examine by hand.

On the other hand, as Benjamin Steinberg points out, the barycentric subdivision of any simplicial complex is flag, so classifying contractible flag complexes should be as hard as classifying contractible simplicial (and more generally CW) complexes.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .