Implement `IsBetweenCoverAndX` for partial orders and lattices

[reiniscirpons]

Computing all the edges of a partial order or lattice via DigraphReflexiveTransitiveClosure can be very time and memory intensive, especially for larger graphs. At the same time, many algorithms for lattices can be run quite efficiently even if some transitive edges are missing.

We should implement the functions

• IsBetweenCoverAndPreorder - to check if a given digraph contains the cover relation of some preorder digraph, and is in turn contained in a preorder digraph.
• IsBetweenCoverAndPartialOrder - the equivalent functionality for partial order
• IsBetweenCoverAndLattice - for lattices.

One naive way to implement this would be to compute the reflexive transitive closure and then apply the appropriate filter, i.e. IsLatticeDigraph(DigraphReflexiveTransitiveClosure(D)); would compute IsBetweenCoverAndLattice. However as mentioned above, doing so is memory intensive on large graphs, see also #636 . So the idea would be to implement IsBetweenCoverAndLattice ideally without adding any extra edges to the given digraph.

See also #664 and #632 for related, but not quite same problems.

[reiniscirpons]

@zljlzljlz this is a writeup of what we spoke about earlier. I think the name I initially suggested for the function wasn't all that good and we should instead call the functions IsBetweenCoverAndX for each of the classes X.

As you mentioned, IsBetweenCoverAndPreorder should just always return true since this will always be the case. For IsBetweenCoverAndPartialOrder(D) I spoke to @james-d-mitchell briefly and we thought that maybe this would just involve checking if D is acyclic. For lattices we weren't really sure how to proceed but we can have a brainstorm next week!

[mtorpey]

This is what @zljlzljlz is working on, right?

[zljlzljlz]

Indeed.

[Joseph-Edwards]

For the IsBetweenCoverAndLattice function, we need to know whether the input digraph can be extended (by the addition of transitive edges) to both a meet-semilattice and a join-semilattice. The code implemented in DIGRAPHS_MeetJoinTable might provide a good template for this.

A function that takes a digraphs D, that may not have of all transitive edges, and checks if it can be extended to a meet-semilattice might take the following steps:

1. Topologically sort the nodes in D.
2. Iterate through pairs of nodes of D in topological order and construct a table of their meets.
3. If there is more than one maximal lower bound for any pair of vertices, return false; we know the the reflexive-transitive closure of D is not a meet-semilattice. Otherwise, return true.

Care needs to be taken when checking for the existence of lower bounds, since we might not have the transitive edges, but it should be possible to take advantage of the partial table of meets to do this.

An example of a digraph that cannot be extended to a meet-semilattice is given by D := Digraph([[3, 4], [3, 4], [5], [5], []]);. Vertices $1$ and $2$ and are both minimal lower bounds for the vertices $5$ and $6$.

@ThatOtherAndrew, this might be something you would be interested in.

[ThatOtherAndrew]

Currently on a restricted network, will investigate later today!

[ThatOtherAndrew]

I believe I understand how to implement the IsBetweenCoverAndLattice algorithm outlined in the 3 steps, although I do not understand the underlying maths of what this is for / how it works. Would that be sufficient?

[reiniscirpons]

I believe I understand how to implement the IsBetweenCoverAndLattice algorithm outlined in the 3 steps, although I do not understand the underlying maths of what this is for / how it works. Would that be sufficient?

@ThatOtherAndrew Yes that should be absolutely fine. Also don't hesitate to ask if you have any questions about the underlying mathematics.

For a quick introduction on lattices, the Lattice wikipedia page is quite well written. In Digraphs, a lattice digraph represents a lattice partial order on the vertices of the digraph, where the relation
$a \leq b$ holds if and only if there is an edge from $a$ to $b$ in the digraph, see the manual entry for IsLatticeDigraph for more info. The meets and joins offer an alternate view of a lattice as an algebra, and is what the DIGRAPHS_MeetJoinTable function computes.

As for the what this is for: many of the relations in a lattice can be inferred from other edges. For example, if we know that $a\leq b$ and $b \leq c$, then we can deduce that $a \leq c$, this is because of the transitivity property of partial orders. However, in order for IsLatticeDigraph to hold, the digraph must have all three edges $(a, b), (b, c)$ and $(a, c)$, even if the final edge $(a, c)$ is a consequence of transitivity.

There are many graphs that arise in practice in semigroup and group theory (e.g. the lattice of congruences or lattice of subgroups ) that are lattices, but when we compute them we may not compute all of the edges for efficiency reasons (i.e. we might compute some smaller set of edges which imply other edges because of transitivity). However, if we then want to perform computations with this digraph to determine its lattice properties (such as height, width etc), we can't use the appropriate functions in the Digraph package because they expect the graph to satisfy IsLatticeDigraph, which needs all of the transitive edges to be present. This means that to use these, we often need to call DigraphReflexiveTransitiveClosure which computes all these missing edges. But this is very wasteful in practice, since it requires us to copy the whole graph and then add a lot of edges. If the original graph had $n$ vertices, we may need to add up to $n^2$ additional edges! This is just not practical for really big graphs that represent lattices.

At the same time, many of the algorithms we have for lattices should work, possibly with some modifications, if we have a digraph representing lattices that is missing some (but not neccesarily all) of the transitive edges. In order for us to apply such algorithms in the Digraphs package, we need a way of checking if a digraph is a lattice that is missing some edges. This is precisely what the IsBetweenCoverAndLattice functions should do. So, given a digraph D, we would want IsBetweenCoverAndLattice(D) to return true whenever IsLatticeDigraph(DigraphReflexiveTransitiveClosure(D)) returns true, but we would ideally want IsBetweenCoverAndLattice to perform this computation without copying D or adding any extra edges to D. If we had such a function then we would be able to compute many interesting properties of lattices arising from semigroup and group theory that were previously out of reach because of their large size.

Hope this helps!