Concepts in topology successfully transferred to graph theory and combinatorics with non-trivial applications?

Question

What are some of the difficult concepts in topology that have been transferred to graph theory and combinatorics where a certain new application has been found.

A good example is Lovász's proof of Kneser's conjecture.

Answer 1

The question asks for concepts, not applications, so in a sense the example given in the OP isn't one.

Here are five quick examples:

(0) One could argue that girth is a transferral of the concept systole from metric-topology, though this is an ahistorical argumentation: the two concepts arose independently in their respective fields.

(1) The concept of associated abstract polyhedral/simplicial complexes. This is the central concept in both Lovász's proof of Kneser's conjecture, and in the proof in [Babson--Kozlov, Proof of the Lovász conjecture, Annals of Mathematics (20 165 (2007) 965-1007]

(2) The concept of topological connectivity (i.e. (1+) smallest dimension such that there exists a non-nullhomotopic continuous map from a correspondingly-dimensional sphere to the geometric realization of the complex (this is strongly related to what the opening poster already mentioned, yet it was not explicitly mentioned yet.

(3) The similar concepts of Whitney complex and barycentric subdivision (see recent work of Oliver Knill).

(4) The concept of Freudenthal-compactification (see 'ends of graphs'), an important tool to enlarge the language with which to speak about infinite graphs.

Answer 2

Discrete Morse theory has been developed into a thriving subject by Robin Forman and others.

Answer 3

There has been very interesting work on defining curvature on a discrete graph. For example:

Knill, Oliver. "A graph theoretical Gauss-Bonnet-Chern theorem." arXiv:1111.5395 (2011). (Abstract.)

---

         

---

Another discrete curvature is the Ollivier-Ricci curvature:

Bauer, Frank, Jürgen Jost, and Shiping Liu. "Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator." arXiv:1105.3803 (2011). (Abstract.)

Answer 4

Riemann-Roch theorem for graphs is a good example of topological concepts in algebraic geometry transferred to graph theory. More references may be found here.

Answer 5

You maybe interested in my work with Terrence Bisson, we have studied closed models in various categories of graphs in particular in the category of directed graphs in which we have defined a closed model for which two finite graphs are homotopic equivalent if and only if they are isospectral.

We have defined another closed model in the category of directed graphs related to dynamic systems which characterizes the topology conjugacy class of some walkable finite graphs.

In a paper, I have defined a closed model structure which characterize strongly connected component. I have also studied closed models in the category of undirected graphs and shown that there does not exist a closed model which characterize the Ihara zeta function.

You maybe also interested in the work of Deborah Vicinsky who has constructed spectra for the model that I have defined with Bisson which characterizes isospectral graphs.

Symbolic dynamics and the category of graphs T Bisson, A Tsemo - Theory and Applications of Categories, 2011

Homotopy equivalence of isospectral graphs T Bisson, A Tsemo - New York J. Math, 2011

Closed models, strongly connected components and Euler graphs T Aristide - Proyecciones (Antofagasta), 2016

Tsemo Aristide

Applications of closed models defined by counting to graph theory and topology Algebra Letters, Vol 2017 (2017), Article ID 2

Vicinsky Deborah

The homotopy calculus of categories and graphs. https://scholarsbank.uoregon.edu/xmlui/bitstream/handle/1794/19283/Vicinsky_oregon_0171A_11298.pdf?sequence=1

Answer 6

Infinite graphs have been used as a "discrete version" of topological spaces, for instance infinite Cayley graphs as a discretisation of homogeneous spaces). Gromov constructed homogeneous spaces out of limits of infinite Caley graphs to prove his theorem on homogeneous spaces. Homogeneous spaces and Cayley graphs share the property that you can transfer any point (vertex) to any other by an auto-homeomorphism (isomorphism).

Answer 7

Last year I co-authored a paper whose title speaks for itself:

Comparative Genomics Meets Topology: a Novel View on Genome Median and Halving Problems

The introduced topological framework allowed to advance analysis of some hard combinatorial problems in comparative genomics, and further obtain a closed form answer for an open problem.

Answer 8

Here is a closed model defined in the category of undirected graphs, which maybe answer the question that you raised in your comment to my previous answer: I believe you want to define an homotopy theory which characterizes perfect matchings. The model here characterizes maximum matchings.

Homotopy theory in category theory have been defined by Quillen to generalize classical homotopy theory defined in the category of topological spaces to various settings.

In general, the notion of path does not exist in every category, but, it is possible to define a notion of weak equivalence, fibration, cofibration between two objects. It is on this purpose that Quillen has defined the notion of closed model:

${\it Definitions.}$

Let $C$ be a category, and $W$ a subclass of the class of morphisms of $C$, we say that $W$ verifies the $2$-$3$ property if and only if for every morphisms $f:X\rightarrow Y$ and $g:Y\rightarrow Z$, if two morphisms of the triple $(f,g,g\circ f)$ are in $W$, so is the third.

Let $C$ be a category complete and cocomplete; we say that $C$ is endowed with a closed model if and only if there exist three classes of morphisms $(Fib,Cof,W)$ such that:

• $W$ satisfies the $2$-$3$ property,

• Let $Fib'=W\cap Fib$, $(Cof,Fib')$ is a weak factorization system

• Let $Cof' = W\cap Cof$, $(Cof',Fib)$ is a weak factorization system.

See the reference for the definitions, the class $W$ is called the class of weak equivalences the class $Fib$ is called the class of fibrations, the class $Fib'$ the class of weak fibrations, the class $Cof$ the class of cofibrations, the class $Cof'$ the class of weak cofibration.

In th reference, I have described a method to generate closed models in a category: closed models defined by counting:

Let $C$ be a category complete and cocomplete whose initial object is denoted by $\phi$. For every objects $X$ and $Y$ of $C$, we denote by $X+Y$ the sum of $X$ and $Y$. Let $(X_i)_{i\in I}$ be a family of objects of $C$ and $l_i: \phi\rightarrow X_i$ the canonical morphism. There exist morphisms $j^i_1:X_i\rightarrow X_i+X_i$ and $j^i_2:X_i\rightarrow X_i+X_i$ such that for every morphisms $f:X_i\rightarrow Z$ and $g:X_i\rightarrow Z$, there exists a unique morphism $m(f,g):X_i+X_i\rightarrow Z$ such that $m(f,g)\circ j^i_1 = f$ and $m(f,g)\circ j^i_2 = g$. We set $m_i = m(Id_{X_i},Id_{X_i})$. Such a morphism is often called a folding morphism. We suppose that the class of morphisms $l_i,m_i\in I$ admits the small element argument. We denote by $W_I$ the class of morphisms which are right orthogonal to every morphisms $l_i$ and $m_i, i\in I$.

\medskip

{\it Proposition.}

There exists a closed model $(Hom(C),cell(I),W_I)$ defined on $C$ where $Hom(C)$ is the class of morphisms of $C$ and $cell(I)$ be the class of morphisms of $C$ which are retracts of transfinite compositions of pushouts of $l_i,m_i,i\in I$.

\medskip

Remark that a morphism $f:X\rightarrow Y $ of $C$ is an element of $W_I$ if and only if for every $i\in I$, the map $c^i_f:Hom_C(X_i,X)\rightarrow Hom_C(X_i,Y)$ defined by $c^i_f(h) = f\circ h$ is bijective.

\medskip

This model can be apply to the category of undirected graphs: Let $C_U$ be the category which has two objects that we denote by $0$ and $1$. We suppose that $Hom_{C_U}(0,1)$ contains two elements $s,t$, $Hom_{C_U}(0,0)$ contains one element, $Hom_{C_U}(1,1)$ contains the identity and an involution $i$ such that $i\circ s =t$, and $Hom_{C_U}(1,0)$ is empty. An undirected graph is a presheaf on $C_U$. We denote by $UGph$ the category of undirected graphs, its a complete and cocomplete category since it is a Grothendieck topos.

Particular examples of undirected graphs are the undirected arc graph $A_U$ is the graph defined by $A_U(0)=\{u_1,u_2\}$, $A_U(1)=\{a_1,a_2\}$ such that $A_U(i)(a_1)=a_2$, $A_U(s)(a_1)=u_1$ and $A_U(t)(a_1)=u_2$.

The graph $V_U$ is the graph defined by $V_U(0)=\{v_1,v_2,v_3\}$, $V_U(1)=\{b_1,b_2,c_1,c_2\}$ such that $V_U(s)(b_1)=V_U(s)(c_1)=v_1$, $V_U(t)(b_1) = v_2, V_U(t)(c_1)=v_3$, $V_U(i)(b_1)=b_2$ and $V_U(i)(c_1) = c_2$.

\medskip

We consider the closed model $(Fib,Cof,W)$ defined by counting the object $V_U$ of $UGph$.

\medskip

{\bf Theorem.}

{\it Let $X$ and $Y$ be finite graphs, a weak equivalence $f:X\rightarrow Y$ for the closed model defined by counting $V_U$ induces a bijection between the maximum matchings of $X$ and $Y$. Conversely, if the cardinal of the set of arcs of $X$ and $Y$ are equal, then a morphism $f:X\rightarrow Y$ which induces a bijection between the maximal matchings of $X$ and $Y$ is a weak equivalence.}

\medskip

{\bf Proof.}

A maximum matching of $X$ can be defined by $p_Y:\sum_JA_U^j\rightarrow Y$ where $A_U^j$ is a graph isomorphic to $A_U$ such that: $p$ is injective on arcs, $p_Y(A_U^{j_1})\cap p_Y(A_U^{j_2})$ is empty and every arc of $Y$ shares a vertex with an arc of $p_Y(\sum_J A_U^j)$.

Let $p_X:\sum_JA_U^j\rightarrow X$ be a maximum matching let's show that $p_Y=f\circ p_X$ is a maximum matching. Consider $b$ an arc of $Y$, there exists an unique arc $a$ of $X$ such that $f(a)=b$ since $f$ induces a bijection on arcs. If $a$ is not in the image of $p_X$, $a$ shares a vertex with $p_X(A_U^j)$ for an element $j\in I$, this implies that $b=f(a)$ shares a vertex with the image of $f\circ p_X$. Suppose that $f(p_X(A_U^{j_1}))$ shares a vertex with $f(p_X(A_U^{j_2}))$, you can define a morphism $m:V_U\rightarrow Y$ whose image is the subgraph of $Y$ whose arcs are $f(p_X(A_U^{j_1}))$ and $f(p_X(A_U^{j_2}))$. Since $f$ is defined by counting $A_U$ and $V_U$, there exists a unique morphism $n:V_U\rightarrow X$ such that $m=f\circ n$, but the arcs of $n$ are $p_X(A_U^{j_1})$ and $p_X(A_U^{j_2})$, contradiction, since they do not share a vertex.

Now we show that $f$ induces a surjection between the sets of maximum matchings of $X$ and $Y$. Let $p_Y:\sum_JA_U^j\rightarrow Y$ be a perfect matching. Since $f$ is defined by counting $V_U$, it induces a bijection between the sets $Ar(X)$ and $Arc(Y)$ of arcs of $X$ and $Y$. We can define the morphism $p_X:\sum_J A_U^j\rightarrow X$ such that the restriction $p_X^j$ of $p_X$ to $A_U^j$ is the unique morphism $p^j_X:A_U^j\rightarrow X$ such that $p_Y^j=f\circ p_X^j$, $p_X$ is a maximum matching:

Consider an arc $a$ of $X$ which is not in the image of $p_X$, $f(a)$ is not in the image of $p_Y$, this implies that there exists $j\in J$ such that $f(A_U^j)$ shares a vertex with $f(a)$, we can define a morphism $g:V_U\rightarrow Y$ whose image is the subgraph of $Y$ which arcs are $f(a)$ and $p_Y(A_U^j)$. Since $f$ is defined by counting $A_U$ and $V_U$, there exists a morphism $h:V_U\rightarrow X$ such that $g=h\circ f$, the image of $h$ is $a$ and $p_X(A_U^j)$. Remark that $p_X(A_U^{j_1})\cap p_X(A_U^{j_2})$ is empty since $p_Y(A_U^{j_1})\cap p_Y(A_U^{j_2})$ is empty. We deduce that $p_X$ is a maximum matching. We deduce that $f$ induces a surjective map on maximum matchings.

Suppose that $X$ and $Y$ are finite undirected graphs such that the set of arcs of $X$ and $Y$ have the same cardinal and $f$ is a weak equivalence: firstly we remark that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $b$ be an arc of $Y$, there exists a maximum matching $p\sum_JA_U^J\rightarrow Y$ whose image contains $b$, we can lift $p$ to $q:\sum_JA_U^j\rightarrow X$ such that $p=f\circ q$, this implies that there exists an arc $a$ of $X$ such that $f(a)=b$. Since $f$ is surjective on arcs and the cardinals of the set of arcs of $X$ and $Y$ are equal, we conclude that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $g:V_U\rightarrow Y$, there exists arcs $a,a'$ of $X$ such that the image of $(a,a')$ the subgraph of $X$ which is the union of $a$ and $a'$ by $f$ is $g(V_U)$, suppose that $a,a'$ do not have a common vertex, there exists a maximal matching $p\sum_JA_U^j\rightarrow X$ whose image contains $(a,a')$, but $f\circ p$ is not a matching: contradiction, since we have supposed that $f$ induces a map well defifined on maximal matchings. This implies that $g$ can be lifted to $X$ and $Hom(V_U,X)\rightarrow Hom(V_U,Y)$ induced by $f$ is surjective. This map is also injective since $f$ is induces a bijection on arcs.

\medskip

If one supposes that $X$ and $Y$ do not have isolated vertices, similar arguments show that a week equivalence between $X$ and $Y$ induces a bijection between their respective set of perfect matchings.

\medskip

This closed model is not trivial, consider the graph $X$ which is the undirected path of length $2$ (or $V_U$), it is obtained by identifying one vertex of two copies of $A_U$, and $Y$ which is the concatenation of $A_U$ and a circle. You can define $f:X\rightarrow Y$ obtained by identifying the middle vertex of $X$ with a vertex at its end. It is a weak equivalence.

Tsemo Aristide

Applications of closed models defined by counting to graph theory and topology Algebra Letters, Vol 2017 (2017), Article ID 2