Homotopy $n$-types of graphs in discrete homotopy theory

Discrete homotopy theory, introduced around 20 years ago by H. Barcelo and collaborators [1] building on the work of Atkin from the mid-seventies, is a homotopy theory of (simple) graphs. The theory reimagines the foundations of algebraic topology in the category of graphs, and the resulting homotopy invariants encode more combinatorial information within a graph. These invariants have found applications in matroid theory, hyperplane arrangements, time series analysis, and most recently in topological data analysis, where it provides a more noise-resistant alternative to the usual Vietoris-Rips construction.

Recently, tools from category theory and abstract homotopy theory have been successfully used to prove new results in the field, including a resolution [2] of the Babson–Barcelo–de Longueville–Laubenbacher conjecture [3] on realizing discrete homotopy groups of graphs. That is, the discrete homotopy groups functor ${\pi }_n^{\mathrm{Graph}}:{\mathrm{𝖦𝗋𝖺𝗉𝗁}}_{\ast }\to \mathrm{𝖦𝗋𝗈𝗎𝗉}$ factors through the topological homotopy groups functor as in the diagram:

The functor $\mathrm{𝖦𝗋𝖺𝗉𝗁}\to \mathrm{𝖳𝗈𝗉}$ itself factors through the category $\mathrm{𝖼𝖲𝖾𝗍}$ of cubical sets. Similar to simplicial sets, cubical sets are a model for the homotopy theory of spaces, and are defined as the category of presheaves over the box category. The resulting functor $\mathrm{𝖦𝗋𝖺𝗉𝗁}\to \mathrm{𝖼𝖲𝖾𝗍}$ is known as the nerve functor. The conjecture was resolved by using the model structure on the category of cubical sets together with the closed symmetric monoidal product given by the geometric product of cubical sets; thus the discrete homotopy groups of a graph can be recovered as the topological homotopy groups of the geometric realization of its nerve.

A major problem in the field is to determine whether the nerve functor is an equivalence of $\mathrm{\infty }$-categories between the category of graphs, localized at ${\pi }_{\ast }^{\mathrm{𝖦𝗋𝖺𝗉𝗁}}$-isomorphisms, and the $\mathrm{\infty }$-category of spaces. A positive resoluton to this conjecture would establish a “dictionary” by which results in algebraic topology can be translated to results in the homotopy theory of graphs. This would resolve numerous other open problems, including discrete analogues of the Blakers–Massey theorem, the Mayer–Vietoris long exact sequence, and Brown representability.

In this talk, I will report on joint work with Mark Behrens and Chris Kapulkin making progress towards the conjecture by showing the nerve functor is essentially surjective after localizing at $n$-equivalences. That is, for a fixed $n$, the homotopy groups up to dimension $n$ of any topological space can be recovered as the discrete homotopy groups of some graph. Thus, our construction yields a potential inverse to the nerve functor up to homotopy. Our proof combines cubical homotopy theory, Reedy theory, and explicit combinatorics on graphs. As an added benefit, our methods allow us to compute previously-unknown discrete homotopy groups.