Updates

  1. On November 6, Nick Scoville informed us about his work with Seth Aaronson on Lusternik-Schnirelman theory in the context of Forman theory. Here is a link to their research page. Since our paper is purely graph theoretical (we especially do not look at geometric realizations as CW complexes) there seems not to be overlap of results however. It seems like a parallel approach to discretising Lusternik-Schnirelmann. Here is a link to their paper [PDF] dated August 19, 2012. Aaronson-Scottville take the elementary collapses of Whitehead. One of our main difficulties with doing LS theory on graphs G is that contractible in G is not a good enough notion for a LS cover. Small examples like the cyclic graph G with 4 elements which does not allow any homotopy contraction would imply that the LS category is 4 because even a two point graph K2 is not collapsible in G. But crit(G)=2. This is why we had to allow contracibility in itself in the definition of category. While this is obvious once seen, it had been a major stumbling block in developing the theory. An other difficulty (also obvious once seen) is the definition of the multiplication in the cohomology ring in order to define cup length. We need an exterior product which works for general finite simple graphs without referring to Euclidean implementations.
  2. Nov 13, 2012 correction: cat(G) as defined in the November 4 paper is not a homotopy invariant. The dunce hat G satisfies cat(G)=2 but it is homotopic to a point. This is also the case for the continuum dunce hat M which satisfies cat(M)=2 but is homotopic to a point. (In the continuum, the homotopy invariance Theorem 1.30 in CLOT deals with paracompact C2 manifolds and the dunce hat is not a manifold). In the graph case, we renamed now the category topological category tcat(G) and define cat(G) as the minimum over all tcat(H), where H is homotopic to G. This is similar as with geometric category gcat(G) which is made homotopy invariant to become the strong category Cat(G). The original theorem reads now cup(G) ≤ tcat(G) ≤ crit(G) and remains true. Because cup is a homotopy invariant and cat(G) &le tcat(G) we have also cup(G) ≤ cat(G) ≤ crit(G) and because cat(G) is a homotopy invariant, we have the ultimate relation
    cup(G) ≤ cat(G) ≤ cri(G)
    between three homotopy invariants cup,cat,cri for graphs. The first one is algebraic, the second one is topological and the third one is analytic. This Lusternik-Schnirelmann theorem is true for any finite simple graph.