A discrete homotopy theory for binary reflexive structures (Q1763635)

A (binary reflexive) structure is a set \(X\) equipped with a relation \(\sigma\) containing the diagonal of \(X^2\). Writing \(x\to y\) for \((x,y)\in\sigma\) we obtain an associated digraph (with loops \(x\to x\) at all vertices). \(F\) has base set \(X= \{0,1,2,\dots\}\) and \(n\to m\) provided \(n= m\) or \(n\) is even and \(|n-m|= 1\). A (weak) path in \(X\) from \(x\) to \(y\) exists iff a homomorphism \(f:F\to X\) (\(x\to y\) implies \(f(x)\to f(y)\)) has \(f(0)= x\) and \(f(n)= y\) for all \(n\geq N\). \(F^k(X,x_0)\) is the set of all homomorphisms \(f: F^k\to X\) such that for some \(N\geq 0\), \(f(\tau_1,\dots,\tau_k)= x_0\) implies there is a \(\tau_i\) such that \(\tau_i= 0\) or \(\tau_i\geq N\). \(F^k(X, x_0)\) has the relation inherited from Hom\((F^k,X)\) (\(f\to g\) iff \((f(\tau)\to g(\tau))\) for \(\tau\in F^k\)) and base point \(\overline x_0\) the constant map \(f(\tau)= x_0\). Let \(\sigma_k(X, x_0)\) denote the set of path components of \(F^k(X, x_0)\) with \(|f|\) denoting the path component of \(f\). For \(f\in F^k(X, x_0)\) and \(1\leq i\leq k\) let \(N_1(f)\) denote the least nonnegative even integer \(N\) such that\(f(\tau_1,\dots, \tau_k)= x_0\) if \(\tau_i\geq N\) and \(N(f)= \max N_i(f)\). Let \(f,g\in F^k(X, x_0)\) and \(N\geq N(f)\) an even integer. Then \((f,g)_N= f(\tau_1,\dots, \tau_k)\) if \(\leq N\), \((f,g)_N= g((\tau_1)- N\), \(\tau_2,\dots, \tau_k)\) otherwise. Finally let \(|f|*|g|= |(f, g)_{N_1(f)}|\). Then it is shown that \(\sigma_k(X, x_0)= (\sigma_k(X, x_0),*,|\overline x_0|)\) is a group with identity \(|\overline x_0|\). With \(\sigma_k(X, x_0)\) as defined above one has a precise recipe even if somewhat complicated. Via a reductive process passing through posets and their standard realization as a simplicial complex with facets the maximal chains, it is shown that \(\sigma_{k_0}(X, x_0)\) is naturally isomorphic to the \(k\)th homotopy group of the simplicial complex of \(X\) whose simplexes are those subsets of \(X\) which are homomorphic images of finite chains. In a nice tour de force the authors provide a different way to look at these homotopy groups. As explained in the introduction, this fact can be employed to determine when the \(\sigma_k(X, x_0)\) are all trivial, and this determination plays an important role in sorting certain computational problems as being NP-complete or not.