Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

By a graph I will understand an undirected graph without multiple edges or loops. By a morphism of graphs I will understand a map $f$ between the underlying sets of vertices, such that if $x$ and $y$ are adjacent, then $f(x)$ and $f(y)$ are either adjacent or equal.

Let $G$ be a finite graph. One can realise $G$ as a CW-complex $|G|$ and look at topological invariants, such as singular homology. But this captures only very little information about $G$, because except from $H_0(|G|)$ and $H_1(|G|)$ all homology groups are zero.

Consider the following alternative construction: Let us write $\Delta_n$ for the complete graph on $n$ vertices, and let us re-baptise this graph by the name "standard $n$-simplex". There are obvious codegeneracy and coface maps between standard simplices, so that we obtain a cosimplicial object $\Delta_\bullet$ in the category of graphs. Now, proceed as usual: Morphisms $\Delta_\bullet \to G$ form a simplicial set, applying the free group construction yields then simplicial group, and the associated chain complex is the one whose homology $H_i^{\mathrm{sing}}(G)$ I shall call "singular homology of $G$".

Obvious properties of $H_i^{\mathrm{sing}}(G)$ are: It is a finitely generated commutative group ($G$ is finite), covariantly functorial in $G$. In particular, if we work with coefficients in a field, we obtain representations of the automorphism group of $G$. The homology of the point is $\mathbb Z$ in degree $0$ and trivial in higher degrees. We can define singular cohomology accordingly, and get then a natural pairing between homology and cohomology.

The list of all natural questions one must ask after making such a definition is long, so I will not ask everything.

(a) Is there a comparison map $H_i(|G|) \to H_i^{\mathrm{sing}}(G)$, maybe even on the level of chain complexes? Is there some more elaborate CW-complex $||G||$ one can naturally associate with $G$ such that $H_i(||G||)$ gives back singular homology of $G$? In that case, one would ask for a natural map $|G| \to ||G||$.

(b) Given a graph $G$, is there a largest integer $i$ such that $H_i^{\mathrm{sing}}(G)$ is nonzero? Assuming yes, is this integer less or equal the size of the largest complete subgraph of $G$.

(c) Is there a Künneth morphism in singular cohomology? --is there a natural ring strucure on cohomology?

(d) What is a homotopy between morphisms of graphs? Given an answer to that, do homotopically equivalent morphisms induce the same maps in homology?

(z) Can you give an example of a graph with nontrivial $H_2^{\mathrm{sing}}(G)$?

share|improve this question
    
I had an erroneous answer here based on recognizing that the associated simplicial set is the coskeleton of its 1-skeleton, and that the chain complex computes the homology of the geometric realization of this simplicial set. This is still true, but the associated simplicial set is not fibrant and so one needs to do more work to determine the homotopy type. –  Tyler Lawson May 15 '10 at 12:54
    
This would have contradicted Robin's answer and Torsten's comment to it, which suggest that, say for the icosahedron-graph, (or also for any cycle of size $\geq 4$) we have nontrivial $H_2$ (respectively $H_1$). –  Xandi Tuni May 15 '10 at 12:59

2 Answers 2

up vote 2 down vote accepted

You talk about morphisms from $\Delta_\bullet$ to a graph $G$. I presume a morphism from $\Delta_n$ to $G$ is just an embedding of $\Delta_n$ in $G$, that is an $(n+1)$-clique in $G$ with a labelling of its vertices from $0$ to $n$. It seems to me that defining (co)homology in this way will be the same as the standard simplicial/singular (co)homology of the space $\widehat G$ obtained from $G$ by "filling in" each $(n+1)$-clique with an $(n+1)$-simplex.

As a example consider the graph $G$ consisting of the vertices and edges of a regular icosahedron. Then its $3$-cliques correspond to the faces of the icosahedron and it has no $4$-cliques. Therefore $\widehat G$ will consist of the boundary of the solid icosahedron in $\mathbb{R}^3$ and so your second homology group will be nonzero.

I hasten to add that I have not checked any details, and admit in advance that my thoughts here may be msiguided or just complete nonsense.

share|improve this answer
    
My maps of graphs are not just embeddings (1st paragraph) - the map that sends all of $\Delta_n$ to a single point is a valid morphism. Still: The space $\widehat G$ you suggest is the right candidate for $||G||$ in (a), the inclusion of $|G|$ in $\widehat G$ would yield the sought comparison map. –  Xandi Tuni May 15 '10 at 11:24
6  
Indeed this is just the simplicial set associated to the clique simplicial complex of a graph. Any flag complex is (by definition) the clique complex of its 1-skeleton considered as graph. In particular the barycentric subdivision of any simplicial complex is a flag complex and consequently any simplicial complex is homeomorphic to a clique complex. –  Torsten Ekedahl May 15 '10 at 11:32
    
After a first careless check, it appears that Robin and Torsten are right. Summing up that means "yes" for (a) and both parts of (b) and we also have many examples for (z). The answer to (c) is "no way": This kind of singular cohomology behaves very bad for products of graphs. –  Xandi Tuni May 16 '10 at 11:18

In response to (d), you may find some of the papers by Anton Dochtermann interesting. In particular, the paper Hom complexes and homotopy theory in the category of graphs might contain something you are looking for. I've seen two different notions of graph morphism: one where you allow $f(x) = f(y)$ if $x$ and $y$ are adjacent as you have, and one where you don't. Not allowing equality is what Dochtermann does, but your definition can be recovered if you put a loop at each vertex, for example.

If you use this definition (so the complete graphs form a simplicial object given by the different ways of embedding), then homology is not a homotopy invariant if my old notes are correct: the line graph on 3 vertices and the line graph on 2 vertices are homotopic but $H_1$ for the first is rank 2 while for the second it is rank 1. This should probably be double-checked (sorry that I am not doing this).

Maybe I should also mention that homology defined this way has been studied in the literature. It usually goes by the name of the "clique complex".

Hope that's of some help. I wrote some notes exploring some of these ideas which you can have if you like (but looking back, it looks like I was confused and I don't remember what I was trying to do), just send me an email.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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