12
$\begingroup$

Let $G$ be a simple graph on a finite vertex set. The clique complex $X(G)$ is the simplicial complex whose faces are complete subgraphs of $G$, and the independence complex $I(G)$ is the simplicial complex whose faces are independent subsets of $G$. Said another way, $I(G) = X( \bar{G} )$, where $\bar{G}$ denotes the complement of $G$.

My question is whether there is any relationship between the topology of these two complexes. Playing around with small examples made me optimistic that there would be some way to relate the homology of $X(G)$ with the cohomology of $I(G)$, perhaps via Alexander Duality. For example, consider $G = C_5$, the $5$-cycle. Then both $X(G)$ and $I(G)$ are homeomorphic to $S^1$. The boundary of the simplex on $5$ vertices is homeomorphic to $S^3$.

In particular, we have (for reduced homology and cohomology) that $H_q (X(G)) = H^{m-q-1} (I(G))$, where $m=3$.

But I don't see any proof for a general case.

Even worse: one can probabilistically construct examples on $n$ vertices, where both $X(G)$ and $I(G)$ both have dimension roughly $2 \log_2 n$ and all their nontrivial homology concentrated around dimension $\log_2 n$, which also does not seem to bode well for Alexander Duality. At least it does not bode well for the most simple-minded relationship, where one might hope that $I(G)$ is homotopy equivalent to the complement of $X(G)$ in the $n-2$-dimensional sphere.

(The probabilistic examples I have in mind are to let $G$ be the Erdős–Rényi random graph $G(n,p)$ with $p=1/2$. Then the clique complex $X(G)$ and independence complex $I(G)$ have the same distribution. Several papers have studied the topology of such random complexes, and we know that they have homology concentrated around middle dimension.)

$\endgroup$
  • $\begingroup$ What happens for triangle-free graphs? ($C_5$ is atypical because it is self-complementary.) $\endgroup$ – Chris Godsil Nov 18 '14 at 22:25
  • 2
    $\begingroup$ There is no connection in general between $X(G)$ and $S^n \setminus I(G)$ for a given graph $G$. Perhaps you're more interested in classifying those $G$ for which an Alexander type theorem might hold? $\endgroup$ – Vidit Nanda Nov 19 '14 at 2:22
13
$\begingroup$

Given any graph $G$, let $G'$ denote $G$ with a new vertex $v$ adjacent to every vertex of $G$. The clique complex of $G'$ is contractible, while the independence complex of $G$ and $G'$ are the same except for an isolated vertex. Similarly we can adjoin a new isolated vertex $w$ to $G$, obtaining a graph $G''$ with a contractible independence complex but with the same clique complex as $G$ except for an isolated vertex. Thus is general there is not much connection between the topologies of the clique and independence complexes.

$\endgroup$
7
$\begingroup$

This is not quite an answer to your question, but still.

There is a version of Alexander duality between homology groups of clique complex $X(G)$ and complex of complements of non-cliques $X^*(G)$, see, e.g. http://arxiv.org/pdf/0710.1172.pdf for precise statement in the case of arbitrary simplicial complexes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.