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\). If \(P\) is a poset on \(N\) then the incomparability number of \(P\), denoted by \(\mbox{inc}(P)\), is the number of two-element subsets \(\{u,v\}\) of \(N\) such that \(u\) and \(v\) are incomparable in \(P\), that is, both \((u,v)\not\in P\) and \((v,u)\not\in P\). A total order on \(N\) is a poset \(T\) on \(N\) with zero incomparability number, that is, for every \(u,v\in N\) either \((u,v)\in T\) or \((v,u)\in T\).
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 \({\cal 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 \}\) of integers 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.
For a poset \(P\), let \({\cal L}(P)\) denote the set of linear extensions of \(P\), that is, enumerations \(\varepsilon\) of \(N\) such that \((u,v)\in P\) implies that \(u\) precedes \(v\) in \(\varepsilon\) (which includes the case \(u=v\)). For \(\varepsilon,\eta\in {\cal L}(P)\), the distance \(\mbox{dist}(\varepsilon,\eta)\) is the (shared) length of the geodesics between \(\varepsilon\) and \(\eta\) in the permutohedral graph. A theoretical result (see section 5.1 of the paper) says that the distance coincides with the number of inversions between \(\varepsilon\) and \(\eta\), that is, with the number of ordered pairs \((u,v)\) of distinct elements of \(N\) such that \(u\) precedes \(v\) in \(\varepsilon\), while \(v\) precedes \(u\) in \(\eta\).
An enumeration \(\varepsilon\in {\cal L}(P)\) is called boundary (in \({\cal L}(P)\)) if there exists an enumeration \(\eta\) of \(N\) which is outside \({\cal L}(P)\) but adjacent to \(\varepsilon\) in the permutohedral graph. If all adjacent enumerations of \(\varepsilon\in {\cal L}(P)\) also belong to \({\cal L}(P)\) then \(\varepsilon\) is named an inner enumeration (in \({\cal L}(P)\)).
The eccentricity of a node \(\varepsilon\in {\cal L}(P)\) is \(\mbox{ecc}(\varepsilon):=\max \{ \mbox{dist}(\varepsilon,\eta) \,:\, \eta\in {\cal L}(P)\,\}\), its degree, denoted by \(\mbox{deg}(\varepsilon)\), is the number of \(\eta\in {\cal L}(P)\) that are adjacent to \(\varepsilon\). The diameter of \({\cal L}(P)\) is \(\mbox{diam}({\cal L}(P)):=\max \{ \mbox{dist}(\varepsilon,\eta) \,:\, \varepsilon,\eta\in {\cal L}(P)\,\}\). The diametral pair is a pair \(\varepsilon,\eta\in {\cal L}(P)\) such that \(\mbox{dist}(\varepsilon,\eta)=\mbox{diam}({\cal L}(P))\). A poset \(P\) is called uni-diametral if it only has one diametral pair.
Every enumeration \(\varepsilon\) of \(N\) encodes a total order \(T_{\varepsilon}\) on \(N\), which consists of the pairs \((u,v)\in N\times N\) such that \(u\) precedes \(v\) in \(\varepsilon\) (which includes the case \(u=v\)). A set \({\cal R}\subseteq {\cal L}(P)\) is a realizer of a poset \(P\) on \(N\) if \(P\) is the intersection of total orders \(T_{\varepsilon}\) for \(\varepsilon\in {\cal R}\). A theoretical result in the paper (see sections 2.3 and 5.2) implies that \({\cal R}\) is a realizer of a poset \(P\) if and only if \({\cal L}(P)\) is the least geodetically convex set containing \({\cal R}\).
The dimension of \(P\), denoted by \(\mbox{dim}(P)\), is the minimal cardinality of a realizer of \(P\). A poset \(P\) is called uni-realized if it has a unique cardinality-minimal realizer.
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 (see section 2.3 of the paper) 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. If \(T\) is a poset, the diagram is the respective transitive directed acyclic graph with covering relations in bold (see section 3.3 of the paper). If \(T\) is only a preposet, its diagram may contain bidirected arrows and no arrows are interpreted as covering pairs. 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 the 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 the respective folders.
In the folder entitled by Set of enumerations, one other button, namely Graphical characteristics, is available. This button is applicable only when (a non-empty) geodetically closed set \({\cal L}(P)\) of enumerations was previously computed (for a poset \(P\) on \(N\)). After clicking on the button Graphical characteristics the respective matrix of distances of enumerations within \({\cal L}(P)\) is internally computed. On the basis of this matrix, the following graphical characteristics are computed by the program: eccentricities and degrees of included enumerations, diameter and the number of diametral pairs (of enumerations). The incomparability number is also shown within this list of graphical statistics.
As a continuation of these computations, the program computes the dimension of the represented poset \(P\) and the number of its cardinality-minimal realizers, giving the information on whether the poset is uni-realized or not. We also provide the number of edges of the linear extension graph of \(P\), which is the induced subgraph of the permutohedral graph on the set of nodes \({\cal L}(P)\). The computation of these characteristics is based on further theoretical observations (which are not included in the paper):
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 input. Light gray: diagonal pairs that were not part of the input. Pairs outside the closure remain white.
The pictorial diagrams represent the closure. If the closure is a poset, the diagrams are transitive directed acyclic graphs and bold arrows correspond to covering pairs. If the closure is only a preposet, bidirected arrows may occur and all arrows are shown with normal strength.
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.
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\). If the closure is antisymmetric, 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. For a non-antisymmetric preposet, covering pairs are not marked.
Click on a node (of the picture showing the power set of \(N\)) to select a set. Dark green nodes denote the input sets selected by the user. Dark blue nodes denote the sets in the generated topology which were not in the input. Light gray nodes do not belong to the current system.
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.
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.
Click on an enumeration to select it as a part of the input. The green colour will denote the input enumerations, which will additionally be highlighted in bold. The summary below reports the number of boundary and inner enumerations in the resulting closure, together with their total count.
After clicking on the above button, the geodetic closure of the input set is displayed. In this closure view, enumerations 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.
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.
After clicking on Graphical characteristics, the above described colours to distinguish input/boundary/inner enumerations will be replaced by tinted colours whose aim is to show the eccentricities and degrees of involved enumerations. The bold font of an enumeration continues to identify whether it was a part of the input.