This applet offers computational transition between three different combinatorial representatives of a poset \(P\) on a finite (unordered) set \(N\) of variables, involving at least 2 and at most 7 variables. Two of these representatives are more general and allow one to represent a preposet \(R\) on \(N\).
Deeper theoretical basis for these transitions is described in the paper 'Graphical view on linear extensions of finite posets' available at https://arxiv.org/abs/2511.11785 . Nonetheless, the applet user does not need to consult the paper because basic definitions are recalled below.
Given a non-empty finite variable set \(N\), a binary relation \(R\) on \(N\) is a subset of the Cartesian product \((N \times N)\), that is, of the set of ordered pairs \((u,v)\), where \(u,v \in N\).
A preposet on \(N\) (or quasi-order, pre-order) is a binary relation on \(N\), which is reflexive, \((u,u) \in R\) for any \(u \in N\), and transitive, \((u,v), (v,w) \in R \Rightarrow (u,w) \in R\). A preposet is called a poset (= partially ordered set) if it is, moreover, anti-symmetric, \((u,v), (v,u) \in R \Rightarrow u = v\).
A set system over \(N\) is a collection \({\cal D}\) of subsets of \(N\). A topology on (finite) \(N\) is a set system over \(N\) which contains the empty set, the whole variable set \(N\), and is closed under intersection and union of sets \((A,B \in {\cal D} \Rightarrow A \cap B, A \cup B \in {\cal D})\).
A topology \( D \) distinguishes points if, for every two distinct \(u,v \in N\), there exists \(D \in {\cal D}\) such that either \([ u \in D \, \& \, v \not\in D ]\) or \([ v \in D \, \& \, u \not\in D ]\).
An enumeration of \(N\) is an ordered list of all elements of \(N,\) without their repetition. Formally, it is described by a bijective mapping \(\varepsilon\) from the ordered set \(\{ 1,\ldots , n \}\) onto \(N\), where \(n\) is the number of elements of \(N\). We use the record \(|\varepsilon(1)|\ldots |\varepsilon(n)|\) to specify such an enumeration, where the straight lines separate the (distinct) elements of \(N\).
The set of enumerations of \(N\) can be interpreted as the set of nodes of an undirected graph, called the permutohedral graph. In this graph, two enumerations form an edge iff they differ by an adjacent transposition, which means that one of them is obtained from the other by interchanging two consecutive items.
A geodesic between two enumerations is a walk in this graph which has the shortest possible length among such walks. A set of enumerations is geodetically convex if, with every two enumerations, it also contains all (enumerations belonging to all) geodesics between them.
The three possible inputs (and ways of representing of a preposet \(R\) on \(N\)) are as follows:
To each of these inputs the respective abstract closure operation can be applied. It is
The applet allows one to compute these closures together with the other corresponding representatives. The idea behind the computations is the application of the respective Galois connections (see Section 2.3 of the paper). More specifically, the procedures are as follows.
If the input is a binary relation \(R\subseteq N\times N\) then after clicking on the button Transitive closure the program first computes the collection \({\cal D}\) of down-sets of \(R\), that is, of subsets \(D\subseteq N\) such that, for any \((u,v)\in R\), if \(v\in D\) then \(u\in D\). This is the respective topology on \(N\). The second step is to compute the collection \(T\) of pairs \((a,b)\in N\times N\) which respect \({\cal D}\), that is, those \((a,b)\) such that, for every \(D\in {\cal D}\), \(b\in D\) implies \(a\in D\). This collection \(T\) appears to be the transitive and reflexive closure of \(R\). Note that the topology \({\cal D}\) distinguishes points iff \(T\) is a poset. The closure \(T\) will be shown both in the \(N\times N\)-array but also in the form of a pictorial diagram. The diagram is the respective transitive directed acyclic graph with covering relations in bold (see Section 3.3 of the paper). The third step is to compute the set of linear extensions for \(R\), which is the set of enumerations \(\varepsilon\) of \(N\) such that, for any \((u,v)\in R\), \(u\) precedes \(v\) in \(\varepsilon\). It appears to coincide with the set of linear extensions for \(T\). If \(T\) is a poset (= anti-symmetric) then this set of extensions is non-empty, otherwise it is empty. The user can find the topology and these linear extensions in the respective folders.
If the input is a set system \({\cal D}\) over \(N\) then after clicking on the button Generated topology the program first computes the respective preposet \(R\subseteq N\times N\) as the set of \((a,b)\in N\times N\) respecting \({\cal D}\), that is, those pairs \((a,b)\) such that for every \(D\in {\cal D}\), \(b\in D\) implies \(a\in D\). The second step is to compute collection \({\cal T}\) of down-sets \(D\) of \(R\), which means, such sets \(D \subseteq N\) that for any \((u,v)\in R\), \(v\in D\) implies \(u\in D\). The collection \({\cal T}\) appears to be the topology generated by the input set system \({\cal D}\). The third step is to compute the set of linear extensions for \(R\), by the same procedure as in the previous case. Again, the user can find the preposet and its linear extensions in the respective folders.
If the input is a set \(S\) of enumerations of \(N\) then after clicking on the button Geodetic closure the program first computes the respective binary relation \(P\) on \(N\) as the set of \((a,b)\in N\times N\) respecting \(S\), which means that, for every \(\varepsilon\in S\), \(a\) precedes \(b\) in \(\varepsilon\). Note that in case of the empty input \(S=\emptyset\) one has \(P=N\times N\), but in case of non-empty \(S\) the relation \(P\) is always a poset on \(N\). The second step is to compute the geodetic closure \(G\) of \(S\) as the collection of those enumerations \(\eta\) of \(N\) that respect \(P\), that is, for every \((u,v)\in P\), \(u\) precedes \(v\) in \(\eta\). The third step is to compute the respective topology \({\cal T}\) as the collection of down-sets for \(P\) (as described in case of binary relation input). The user can find the corresponding poset and topology in respective folders.
Click on an entry of the array to select a pair. Dark green entries indicate selected input pairs. White entries denote pairs not belonging to the relation.
After clicking on the button, the transitive and reflexive closure is displayed. Each pair in the array is colour-coded as follows: Dark green: input pair that is a covering pair in the closure. Light green: input pair that is not a covering pair in the closure (this includes all diagonal input pairs). Light blue: non-input, non-diagonal pair implied by the closure. Light gray: diagonal pairs that were not part of the input. Pairs outside the closure remain white.
The pictorial diagrams show the transitive directed acyclic graph representing the closure. Bold arrows correspond to covering pairs.
Here we show pictorial representation of the transitive closure computed as described in the Introduction part.
In this straightforward approach, the binary relation is treated as a directed graph and its transitive closure is obtained by computing reachability: for every pair of vertices \((u,v)\), we check whether there exists any directed path from \(u\) to \(v\). This is implemented by computing all shortest paths in the graph and converting all finite path lengths to 1, which yields the reachability matrix of the graph. Based on this closure, all covering pairs \((u,v)\) are identified as those edges for which no intermediate element \(w\) satisfies \((u,w)\) and \((w,v)\) in the closure.
If the result displayed in this folder was computed from an input provided in a different folder, the green input colour is not used and all results are shown in blue. Clicking on the closure button in this folder starts a new computation and the current input becomes green.
Click on a node to select a set. Dark green nodes denote input sets selected by the user. Dark blue nodes denote sets implied by the generated topology. Light gray nodes do not belong to the current system.
After clicking on the button, the topology generated by the input sets is shown. Input sets remain dark green, while newly implied sets appear in dark blue.
If the result displayed in this folder was computed from an input provided in a different folder, the green input colour is not used and all results are shown in blue. Clicking on the closure button in this folder starts a new computation and the current input becomes green.
Click on an enumeration to select it as input. Green colour denotes input enumerations. The summary below reports the number of boundary and inner enumerations in the resulting closure, together with their total count.
After clicking on the button, the geodetic closure of the input set is displayed. Enumerations belonging to the closure are colour-coded as follows: Dark green: input enumeration that is a boundary enumeration of the result. Light green: input enumeration that is an inner enumeration of the result. Dark blue: implied (non-input) enumeration that is boundary in the result. Light blue: implied enumeration that is inner in the result. Enumerations outside the closure remain white.
Boundary enumerations are those having at least one neighbouring enumeration outside the closure. Inner enumerations have all neighbours within the closure. Input enumerations are additionally highlighted in bold.
If the result displayed in this folder was computed from an input provided in a different folder, the green input colour is not used and all results are shown in blue. Clicking on the closure button in this folder starts a new computation and the current input becomes green.