The Lusternik-Schnirelmann theorem for graphs

Abstract

We prove the discrete Lusternik-Schnirelmann theorem telling that tcat(G) less or equal to crit(G) for a general simple graph G=(V,E). It relates the minimal number tcat(G) of in G contractible graphs covering G, with crit(G), the minimal number of critical points which an injective function f on the vertex set V can have. We also prove that the cup length cup(G) is less or equal to tcat(G) which is valid also for any finite simple graph. If cat(G) is the minimal tcat(H) among all graphs H homotopic to G and cri(G) is the minimal crit(H) among all graphs H homotopic to G, we get a relation between three homotopy invariants: an algebraic quantity (cup), a topological quantity (cat) and an analytic quantity (cri).

29 pages, 7 figures. Main results unchanged but cat(G) had not yet been homotopy invariant. 3 more references, smaller typos and a figure correction

References in corpus (3)

• A graph theoretical Poincare-Hopf Theorem
• On index expectation and curvature for networks
• A Brouwer fixed point theorem for graph endomorphisms

Cited by in corpus (17)

• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• The McKean-Singer Formula in Graph Theory
• The Dirac operator of a graph
• Gauss-Bonnet for multi-linear valuations
• Coloring graphs using topology
• A notion of graph homeomorphism
• Graphs with Eulerian unit spheres
• Classical mathematical structures within topological graph theory
• The Jordan-Brouwer theorem for graphs
• Deformed Laplacians and spectral ranking in directed networks
• The graph spectrum of barycentric refinements
• A Reeb sphere theorem in graph theory
• A simple sphere theorem for graphs
• Constant index expectation curvature for graphs or Riemannian manifolds
• Graph complements of circular graphs
• Complexes, Graphs, Homotopy, Products and Shannon Capacity
• Coloring Discrete Manifolds