(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)

Are there examples of results in "classical" [*] graph theory that have been achieved by using simplicial complex methods?

Another terse way of putting that question is perhaps:

Can methods from 05E45 be used to resolve problems raised in 05C?

[*] As a rough working definition of "classical" I take anything that appears or could have reasonably appeared in the standard books by (for example) Diestel, Bollobas, Chartrand & Lesniak, Bondy & Murty.

  • $\begingroup$ What about containing graphs? $\endgroup$ – Fernando Muro Mar 27 '14 at 12:56
  • 1
    $\begingroup$ @FernandoMuro What are they? $\endgroup$ – Felix Goldberg Mar 27 '14 at 13:00
  • 8
    $\begingroup$ Your second way of putting the question is not so much "terse" as "incomprehensible". $\endgroup$ – Lee Mosher Mar 27 '14 at 13:33
  • 3
    $\begingroup$ @LeeMosher I meant the AMS classification numbers: 05E45="Combinatorial aspects of simplicial complexes" and 05C="Graph theory". I hope it's clearer now... $\endgroup$ – Felix Goldberg Mar 27 '14 at 13:34
  • $\begingroup$ @FelixGoldberg sorry it was a stupid comment, I meant that the class of simplicial complexes contains graphs. $\endgroup$ – Fernando Muro Mar 27 '14 at 15:10

There are quite a few examples where simplicial complexes, more general complexes, and algebraic topology in general had important impact on graph theory. (Usually, the applications are indirect and by looking at the graph as a 1-dimensional simplicial complex.) Some such applications are even mentioned in the book you referred to. Examples include: Lovasz solution to the Kneser problem and related later studies of homomorphisms of graphs, the study of simplicial complexes based on edge-sets of graphs with certain properties, the solution of the evasiveness conjecture for graph properties.

I will try to gradually find online papers surveying some of these areas.

1) Here is a survey on Kneser's conjecture by Mark de Longueville

2) Lovasz and Young Lecture Notes on Evasiveness of Graph Properties

3) Jakob Jonsson thesis on simplicial complexes of graphs with introduction and many references.

4) Another line of research started with Aharoni and Haxell's "Hall's theorem for hypergraphs‏." For example Meshulam studied in this context the independence complex of a graph, and found connections between homological properties of the complex and combinatorial properties of the graphs.

5) Another brunch of such applications is coming from Lovasz' 1977 proof of a conjecture by Frank on finding k connected subgraphs with presecibed numbers of vertices in a k-connected graph. (Gyori gave a purely combinatorial proof).

A chapter entitled Topological methods about applications of algebraic topology in combinatorics by Bjorner is a very good general reference and it contains also material about applications to graph theory.

Let me try now to say gradually a few things on each of the five directions mentioned above.

1) Development related to Kneser's conjecture. The chromatic number of a graph is one of the most important parameters associated to graphs. Lovasz' idea was to establish a lower bound on the chromatic number of a graph $G$ in terms of the (homological connectivity) of a simplicial complex - the neighborhood complex, ${\cal N}(G)$ asspciated with $G$. The faces of the neighborhood complex are sets of vertices that have a common neighbors. Lovasz proved that if ${\cal N}(G)$ is $k$-connected (namely has a vanishing reduced homology groups of index $i < k$ then the chromatic number of $G$ is at least $k+2$. (For example if $G$ is bipartite then ${\cal N}(G)$ is disconnected.) These topological methods were extended and applied to various questions related to homomorphisms of graphs.

2) Evasiveness. Consider monotone (decreasing) properties of graphs (say, on a fixed set of $n$ vertices). Here by "monotone" I mean that if a graph $G$ has the property then also every subgraph $H$ of $G$ has the property. (We consider here subgraphs with the full set of vertices.) Every such property describes a simplicial complex whose vertices are the edges of the complete graph on $n$ vertices and whose simplices correspond to subsets of edges so that the subgraph described by them has the property. This simple construction is important also for item 3). We can ask for monotone (and non-monotone) properties of graphs what is the decision-tree complexity of the property. Namely, given an unknown graph $G$ we can ask questions of the type "is an edge $e$ belongs to $G$". We can choose questions according to earlier answers. The evasiveness conjecture of Aanderaa, Karp, and Rosenberg asserts that every non-trivial monotone property of graphs is evasive: namely, you need to ask in the worst case all ${{n} \choose {2}}$ edges before being able to tell if the property is satisfied. Kahn, Saks & Sturtevant proved in 1983 that the conjecture holds when the number of vertices is a prime power. The general case remains open. The basic idea is this: the simplicial complex that corresponds to a non-evasive property must be contractible. (In fact, it is even collapsible in a very strong sense.) On the other hand if the property is non-trivial it admit a free action of the symmetric group on the vertices (acting on the edges). And know you need some basic observations on the symmetric group for prime power number of elements plus a fixed point theorem (by Oliver) for groups of certain types to show that in the prime power case this is impossible.

  • $\begingroup$ Matoušek's nice book "Using the Borsuk-Ulam theorem" should be mentioned here. It is a grad-student accessible, book-length treatment of the Lovász solution to the Kneser problem and more recent improvements (and all the background you need to understand them). $\endgroup$ – Russ Woodroofe Mar 28 '14 at 1:57
  • $\begingroup$ In the same vein of 4) in Gil Kalai's answer, the main result of "R. Aharoni and E. Berger, The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc., 358 (2006), pp. 4895–4917" has interesting applications in graph theory. For instance in this paper : epubs.siam.org/doi/abs/10.1137/100818340 $\endgroup$ – Louis Esperet Mar 28 '14 at 9:10

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.