Skip to main content
3 of 8
added 220 characters in body
Tsemo Aristide
  • 3.7k
  • 1
  • 13
  • 18

Here is a closed model defined in the category of undirected graphs, we 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 , 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 objects $A_U$ and $V_U$ of $UGph$.

\medskip

{\bf Theorem.}

{\it A morphism $f:X\rightarrow Y$ between finite undirected graphs is a weakly equivalence between $X$ and $Y$ for the closed model defined by counting $A_U$ and $V_U$ if and only if it induces a bijection between the maximum matchings of $X$ and $Y$.}

\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 $A_U$ and $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.

We have shown that a weak equivalence induces a bijection between maximal matching. The converse is also true, that is a morphism which induces a bijection between maximal matchings is a weak equivalence.

\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$, 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

Tsemo Aristide
  • 3.7k
  • 1
  • 13
  • 18