Lattices of Paths and Flat Dihomotopy Types
Cameron Calk and Luigi Santocanale
As described for example in [2, 5], the set of discrete paths in a given grid form a distributive lattice, abinomial lattice, whose underlying ordering is also known as the dominance ordering.
The congruences of this lattice present analogies with notions of homotopy coming from directed topology.
In this talk, we formalise this connection by introducing cubical complexes [4], combinatorial directed spaces,
whose subspaces’ dihomtopy types correspond exactly to lattice quotients. This establishes interesting links
between finite lattice theory, combinatorics, and concurrency theory.
This strong connection in the discrete case has led us to extend our investigation to lattices of continuous
paths [6]. In this setting, the dominance order is no longer canonically characterised as a point-wise path ordering. We show that such a characterisation can be achieved, similarly as in the discrete case, by constructing
simultaneous parametrisations and exhibiting directed homotopies that witness the ordering.
Finally, we shall end this talk by sketching ongoing work relating congruences to (directed) topologicalproperties of the unit square.

1. The discrete case. First, we describe the explicit link between the lattice congruences of the binomial lattice L(n, m) and the dihomotopy types of subspaces of a certain two-dimensional cubical complex
C(n, m). Fix non-zero natural numbers n, m ∈ N \ {0}.
1.1. Binomial lattice quotients. The binomial lattice, denoted by L(n, m) or simply L when the context
is clear, admits several equivalent descriptions. Firstly, it is the set of words on the alphabet {E, N } having
exactly n (resp. m) occurrences of E (resp. N ), equipped with the order generated by the relation below on
the first line. Secondly, writing [k] := (0 < · · · < k), L may be described as the set of monotone (discrete)paths f : [n + m] → [n] × [m] on the n by m grid sending 0 to (0, 0) and n + m to (n, m), equipped with thepoint-wise order defined below on the second line,w → w0⇐⇒

∃w1 , w2 s.t. w = w1 EN w2 and w0 = w1 N Ew2f ≤g⇐⇒

f (k) ≤2 g(k) for all k ∈ [n + m]

where ≤2 is the product order [n]op × [m]. These equivalent orderings are known as the dominance order. Itis well known, see e.g. [2] that L is distributive, and so, being finite, its congruences are given (exactly) by
subsets of join-prime elements. Here, these are words of the form E k N l E k N l , where (k, l) = (n, m) − (k, l)
and 0 ≤ x < n and 0 < y ≤ m. As paths, these are those having exactly one “north-east” turn, see the figurebelow.
The join-prime elements of L, the set of which is denoted by J, are thereN
fore characterised by a “point” (k, l) in [n] × [m] describing the upper-lefthand corner of a square in the n by m grid. The congruence ≡S associatedNEEEto a subset S ⊆ J(L(n, m)) identifies f, g ∈ L when j ≤ f ⇐⇒ j ≤ g forN
all j ∈ S. This means that ≡S identifies all paths which are not separatedby the squares associated to the elements of S. This geometric intuition
NEEled us to introduce a cubical complex whose subcomplexes’ dihomotopical
properties correspond to these congruences.
1.2. Binomial cubical complexes. Consider the two-dimensional cubical complex C(n, m) whose set C0of vertices is given by elements of [n] × [m], its set of edges C1 connect pairs of adjacent vertices, and the setof squares C2 is given by filling each of the holes in the grid. The latter is thus in bijection with J, since eachjoin-prime uniquely corresponds to a square in the grid. We call C(n, m) the full (n, m)-binomial complex.

1Its geometric realization ||C(n, m)|| is isomorphic to [0, n] × [0, m] ⊂ R2 . In what follows, we will denote
this complex simply by C. Given a subset S ⊆ C2 , we denote by C S the cubical complex (C0 , C1 , C2 \ S).
Geometrically, ||C S || corresponds to removing the squares in S from the space ||C||.
The maximal combinatorial directed traces of C S , see [3], i.e. images of continuous maps γ : I → ||C S || suchthat γ(0) = (0, 0) and γ(1) = (n, m), increasing in each coordinate and which are contained in the 1-skeletonof C S (the n by m grid), correspond exactly to the elements of L for any S ⊆ C2 . The set of these paths,→−
denoted by T (C S ), is equipped with the elementary dihomotopy relation [3], denoted γ1 S γ2 , which holds
when there exist combinatorial dipaths µ and η and a square F ∈ C2 \ S such thatγ1 = µ ? d11 (F ) ? d02 (F ) ? η and γ2 = µ ? d01 (F ) ? d12 (F ) ? η,i.e. γ1 and γ2 coincide up to going above or below F . We denote the symmetric, reflexive, transitive closure∗of S by !S . Note that the transitive, reflexive closure of ∅ corresponds exactly to the ordering ≤ on L,→−
thereby naturally equipping T (C) with an isomorphic ordering .
Finally, we remark that removing the squares in S from C does not remove any combinatorial dipaths,→−→−
so we have T (C S ) = T (C) for all S. We can thus (artificially) equip these sets with the ordering  so→−∗that ( T (C S ), ) ∼= (L(n, m), ≤).
 The quotients by the dihomotopy relations !S are compatible with this→− S ∗
, S for every S.
ordering, so we obtain lattices T (C ) !
S
1.3. Dihomotopy quotients and congruences. Let j ∈ J be a join-prime element of L and denote by
Fj the corresponding square in C. We establish a technical lemma stating that, given f ∈ L, we have j ≤ f
if, and only if, there exists tf such that the combinatorial trace γf : I → ||C S || corresponding to f satisfies
γ(tf ) ≥2 (x, y) for all (x, y) ∈ Fj . Extending this result to a set of join-primes S ⊆ J, we see that f ≡S g is∗equivalent to γf and γg passing above or below the same set of removed squares in ||C S ||, i.e. having γf ! γg .
This leads to our first main result:→− S 
∗Proposition 1. For any S ⊆ J, we have L(n, m) ≡S ∼.
= T (C ) !
S0We can also include the maps induced by inclusions S ⊆ S 0 . Indeed, in this case, C S is a subcomplexof C S and we have the inclusion of congruences ≡S ⊆≡S 0 . By functoriality, we respectively obtain qS,S 0 :→− S0 →− S ∗∗T (C ) !
T (C ) !
L(n, m) /S 0 → L(n, m) /S . Denoting the associated diagrams by0→0S
S and pS,S :→−Π(C(n, m)) and Cong(L(n, m)), we have the following:→−Theorem 1. Π(C(n, m)) ∼= Cong(L(n, m)).
This means that the congruence lattice Cong(L(n, m)) of the binomial lattice is exactly the diagram ofdihomotopy types of subspaces of the binomial complex. Moreover, each of these is isomorphic to the orderdual of the power-set P(J).

2. Ordering continuous paths. A third description of the binomial lattice L is as join-preserving
lattice morphisms f : [n] → [m]. A natural continuous extension of these lattices is thus given by studying
the lattice of suprema-preserving lattice morphisms of the unit interval f : I → I. These may also be seen as
traces, i.e. images of continuous maps I → I2 which are increasing in each coordinate sending 0 to (0, 0) and 1to (1, 1). A more complete description of this lattice may be found in [6]. In the discrete case, the ordering onelements of L are given by the point-wise order induced by ≤2 , the product order [n]op ×[m]. In the continuouscase, the natural ordering on suprema-preserving functions is given by the point-wise order induced by thatof I, that is, for such f, g : I → I, we setf ≤g⇐⇒f (t) ≤ g(t) for all t ∈ I.

Here we briefly describe how this ordering, again called the dominance order, is captured the point-wiseorder over increasing paths I → I2 induced by that of Iop × I.

2

2.1. Sup-continuous endomorphisms, traces, and paths. We consider the quantale of sup-continuous
endomorphisms of I, denoted by Q∨ (I), i.e. the set of suprema-preserving increasing maps f : I → I equippedwith the dominance ordering ≤ and a multiplication operation given by composition of functions.
Each function f ∈ Q∨ (I) corresponds uniquely to a trace, that is a maximal chain Cf ⊆ I2 . These, in turn,correspond to images of increasing paths p : I → I2 such that p(0) = (0, 0) and p(1) = (1, 1). However, incontrast to the discrete case, in which we essentially parametrize paths by arc-length, many paths correspondto each trace.
For example, the identity endomorphism on I, which corresponds to the diagonal trace ∆, may beparametrized both by p1 : t 7→ (t, t) and p2 : t 7→ (t2 , t2 ). Denoting the product order Iop × I by ≤2 , clearly wehave p1 6≤2 p2 and p2 6≤ p1 . Parametrization is thus a major obstruction to describing the dominance ordervia ≤2 .
2.2. Simultaneous parametrization. The previous example illustrates that, for f, g ∈ Q∨ (I), we cannot
expect f ≤ g to imply pf ≤2 pg for any chosen parametrizations pf and pg of f and g, respectively. However,note that if f and g are topologically continuous, suitable parametrisations are given by t 7→ (t, f (t)) , (t, g(t)).
In the general case, denoting by D the set of discontinuity of points of f and g, we set([{x} when x ∈ I \ D,Lx
where Lx =L=I when x ∈ D,x∈I
This set is equipped with and ordering known as the order sum [1] of the family {Lx }. We show that L isisomorphic to the unit interval I, thereby constructing, for any pair (f, g) of elements of Q∨ (I), parametrizations
πf and πg satisfying πf ≤2 πg ⇐⇒ f ≤ g. We call these simultaneous parametrizations because their xcoordinates coincide throughout the progression of each path.
Simultaneous parametrisation also relates the ordering on Q∨ (I) to the notion of directed homotopy. Indeed,consider f, g ∈ Q∨ (I) such that f ≤ g. Then the map ψf,g : I → [I, I2 ] defined by ψf,g (s, t) = (πf1 (t), (1 −s)πf2 (t) + sπg2 (t)) is an increasing homotopy from πf to πg , in the sense that ψ(s, t) ≤2 ψ(s0 , t) for all s ≤ s0 .
Moreover, any two parametrizations pf and p0f of the same element f are related by a homotopy ϕp,p0 withconstant image, called a reparametrization homotopy. Summing this up, we have
Theorem 2. Let f, g ∈ Q∨ (I) be such that f ≤ g. Then there exist parametrisations πf , πg : I −−→ I2 and a
directed homotopy ψf,g : πf −−→ πg . Moreover, given any parametrisations qf and qg of f and g, there exist
reparametrising homotopies φf , φg so that φf ? ψf,g ? φg is a homotopy from qf to qg .

3. Ongoing work. To end this talk, we discuss partial results and ongoing work relating congruences ofthe lattice Q∨ (I) to topological properties of I2 and its increasing paths. These include studying the topologyof the Priestley dual space X of Q∨ (I) and the subspace XJ correpsonding to its join-primes, as well as its
relation to a topology on I2 . We have also observed certain obstructions to generalising Theorem 1 to thecontinuous case which we will briefly discuss.
References.
[1] Raymond Balbes and Alfred Horn. Order sums of distributive lattices. Pacific Journal of Mathematics,
21(3):421–435, 1967.
[2] M. K. Bennett and G. Birkhoff. Two families of newman lattices. Algebra Universalis, 32(1):115–144, 1994.
[3] Lisbeth Fajstrup. Dipaths and dihomotopies in a cubical complex. Advances in Applied Mathematics,35(2):188–206, 2005.
[4] Vaughn Pratt. Modeling concurrency with geometry. In Proceedings of the 18th ACM SIGPLAN-SIGACTSymposium on Principles of Programming Languages, POPL ’91, pages 311–322. ACM, 1991.
[5] Luigi Santocanale. On the join dependency relation in multinomial lattices. Order, 24(3):155–179, August
2007.
[6] Luigi Santocanale and Maria João Gouveia. The continuous weak order. Journal of Pure and AppliedAlgebra, 225:106472, 2021.
3