Implement more properties of lattices

[james-d-mitchell]

It would be helpful to have methods for IsDistributiveLatticeDigraph and IsModularLatticeDigraph and perhaps some more.

[AshleyClayton]

I am doing this.

[wilfwilson]

Do you still intend to work on Digraphs, @AshleyClayton? 🙂

[wilfwilson]

@AshleyClayton informed me that he is no longer working on this.

[james-d-mitchell]

Yup, he deleted his computer. But on the plus side I think @reiniscirpons is now working on it.

[jukkakohonen]

It seems the current functionality (e.g. IsLatticeDigraph) assumes that the digraph has an edge (x,y) for each comparable pair x<=y. In other words the digraph directly represents the partial order relation.

This is mathematically simple, but in terms of algorithms and compact representation, using the covering relation ("Hasse graph") might be better.

For example, a simple n-element chain has approx (n^2)/2 edges in the current "full" representation, but only n-1 edges in the covering relation.

[james-d-mitchell]

@jukkakohonen what you suggest is an option, I agree, but not the option we chose (for reasons that I now don't recall). The Hasse graph is also available via DigraphReflexiveTransitiveReduction, if this helps.

[wilfwilson]

I understand the concern here @jukkakohonen, thank you for your remarks. It can require many fewer edges, and therefore much less memory, to define the reflexive transitive reduction of a partial order rather than the whole thing. However, we went with our decision for mathematical reasons. We wanted a partial order digraph to be:

• a digraph whose set of edges, considered as a binary relation, is a partial order on the vertices.
• a digraph that satisfies IsReflexiveDigraph, IsAntisymmetricDigraph, IsTransitiveDigraph. I think that makes most sense.

Since you can imagine pretty much any acyclic digraph as a partial order, you might want to apply methods that currently only apply to objects satisfying IsPartialOrderDigraph, such as those to do with lattices. Perhaps we should consider adding new versions of these functions: these could take any acyclic digraph (when the loops are ignored), but consider mathematically it as the partial order digraph defined by its reflexive transitive closure. We would have to think carefully about how, and whether, to do this.

[jukkakohonen]

I agree that viewing a poset in terms of its order relation makes much sense mathematically.

I like the idea in wilfwilson's last paragraph: the internal representation could be different from the external interface. But surely that is not a trivial thing and I certainly do not know enough of GAP mechanics to be able to say anything intelligent on how it should or could be done.

What I might have is some mathematical algorithms for actually implementing lattice properties, either with the covering relation or the order relation representation. (e.g. modular, semimodular, distributive)

[james-d-mitchell]

See #375

[james-d-mitchell]

Just to mention that as of today, IsDistributiveLatticeDigraph is implemented in a release version of Digraphs (I'd have to check which). IsModularLatticeDigraph appears not to be implemented. Also implemented are IsUpperSemimodularDigraph and IsLowerSemimodularDigraph and some related funcitonality.

[reiniscirpons]

The wikipedia page for lattices is a good introduction to the topic, having dedicated pages for modular and distributive lattices. The approach to testing IsModularLatticeDigraph should be rather similar to IsDistributiveLatticeDigraph.

Roughly speaking distributivity (modularity) can be checked by looping through all triples of elements $x, y, z$ and checking if the distributive (modular) law holds, i.e. if $x \wedge (y\vee z) = (x\wedge y) \vee (x\wedge z)$ (or the equivalent condition for modular lattices) holds. The other way of checking for distributivity (modularity) is to use the "forbidden sublattice" criterion. Here we use the fact that a lattice is distributive (modular) if it does not contain embedded copies of the pentagon or diamond lattice (modular if it does not contain copies of just the pentagon). This is described in some more detail on the wikipedia pages.

The current Digraph implementation of IsDistributiveLatticeDigraph uses the forbidden sublattice criterion (see below for the link to the code snippet).

https://github.com/digraphs/Digraphs/blob/a9597ff872fbf82b65f81b4e38a3cb22e0e2b406/gap/prop.gi#L662-L679

It would be interesting to compare both approaches to testing distributivity/modularity to see which is faster/find examples where one method is better than the other.

It would also be nice to have implementation of some of the packages from the SAGE compute algebra package. In particular, checking if a lattice is atomic or complemented would be good properties to have.