posets.RandomLattice() cannot generate some lattices

[obtext]

For example, the lattice

L = LatticePoset((range(9), [(0,1),(1,2),(1,3),(1,4),(2,5),(2,6),(3,5),(3,7),(4,6),(4,7),(5,8),(6,8),(7,8)]))

(a 3-cube with an extra point added at the bottom) will never be generated by posets.RandomLattice().

The algorithm used to generate random lattices is to construct a join-semilattice, successively adding new minimum elements by choosing an admissible upper cover for them at random; and finally making a lattice by adding a bottom element. (Note that the code looks like it is doing the dual of this, but the thing gets turned upside-down when passed to the Poset constructor.) The problem is in the method used to search for an admissible upper cover for the new element: it adds random elements to the antichain one by one, checking at each stage whether the antichain is admissible (i.e. whether adding the new element will preserve unique joins). But not all admissible antichains can be obtained in this way, as the example above demonstrates: in order to construct it, the point 1 has to be added below the antichain {2,3,4}; but no 2-element subset of {2,3,4} is admissible. Furthermore, the lattice cannot be constructed in any way that avoids this step.

A possible fix would be at each step to select the antichain at random from the set of all antichains (repeatedly until an admissible antichain is selected), rather than build it up incrementally. It would, I think, be reasonably efficient to maintain the set of antichains as the random lattice is constructed, since after adding a new element the new antichains are just the old ones with the new element possibly added provided they don't contain any elements below the upper cover just selected. On the other hand, the set of antichains probably grows quite fast as the lattice grows. A method that avoids this cost while still being able to generate all possible lattices would be interesting, but I can't think of one.

(This method would remove the need for the parameter p; alternatively p could be used to bias the selection of antichains in favour of larger or smaller ones.)

CC: @kevindilks @jm58660

Component: combinatorics

Author: Alec Edgington

Branch/Commit: 64d3954

Reviewer: Jori Mäntysalo

Issue created by migration from https://trac.sagemath.org/ticket/27130

[obtext]

Attachment: impossible-random-lattice.png

Diagram of lattice that cannot be generated by posets.RandomLattice()

[kevindilks]

comment:1

How does what Sage currently does compare with the algorithm given here ( https://www.emis.de/journals/MB/125.2/mb125_2_1.pdf ) ?

[obtext]

comment:2

I'm afraid I don't understand the algorithm described there. The description in section 2 sounds as if you build a meet semilattice by successively adding new elements whose lower covers consist only of maximal elements. But that can't generate anything except a chain. I'm trying to understand the code...

Edit: I have compiled and run the code from section 2 of that paper, with a few small modifications:

• Initialize u to 0 in Work() (otherwise it's used uninitialized).
• Change if(!rnd(q)) to if(i && !rnd(q)) (otherwise we may call rnd() with a zero argument in FindMax(), which makes no sense).
• Finally add a bottom element. (The code only generates a join semilattice.)

It does then generate non-trivial lattices. But not all of them. It only generates 2 out of the 5 possible 5-point lattices.

[obtext]

comment:4

I was overthinking the problem. we don't need to maintain a list of antichains. We can just generate random antichains on the fly at each step, repeating until we find an admissible one.

Working on a patch...

[obtext]

Branch: u/alec.edgington/posets_randomlattice___cannot_generate_some_lattices

[obtext]

New commits:

4480bf2

Modify algorithm to generate random lattices.

[obtext]

Commit: 4480bf2

[obtext]

Author: Alec Edgington

[obtext]

comment:7

Hi kdilks, would you be able to review this -- or suggest someone else? Thanks!

[kevindilks]

comment:8

I can look at this in a few days.

[jm58660]

comment:9

True, my fault. Also I did not enough random testing for random lattices: I tested that all 8-element lattices are generated, not for 9-element lattices.

Number of possible antichains is of course O(n!), just take an antichain with upper cover added.

As a quick fix at least one can create a random poset and run completion_by_cuts() to it, but that is also slow.

When doing this I remember thinking about speed and possible algorithms. One possibility could be making a random antichain, and if it not admissible, removing elements from it.

[jm58660]

comment:10

To get some numbers I counted all antichains in 9-, 10- and 11-element lattices. On average they have 27, 37 and 51 antichains. But the corner cases might still freeze computation in practise.

[obtext]

comment:11

Yes, I found by experiment that keeping track of all antichains was too expensive for sizes greater than about 25.

Actually I've submitted for review a simpler fix, which modifies your algorithm so that it generates a random antichain without checking for admissibility at each step, and then if it is inadmissible retries with a new antichain. Performance seems OK.

If this is accepted, I am not sure if the comment advising on the value of p should be modified. Did you have some heuristic to arrive at that recommendation?

[jm58660]

comment:12

The code seems to be OK. I am currently compiling it.

There is already random_order_ideal on posets, with docstring "Return a random order ideal with uniform probability." Might be useful. For values of p I have no suggestion. Might be hard to have a good heuristics.

One idea I had when thinking about more uniform distribution: Create all lattices of (say) three more elements using for example canonical augmentation. Now use the number of them as weight to randomly select one new element to add. Repeat. I haven't tested that.

(Btw, I also tested 12-element lattices. They have 71 antichains on average.)

[jm58660]

comment:13

I tested with

L = LatticePoset((range(9), [(0,1),(1,2),(1,3),(1,4),(2,5),(2,6),(3,5),(3,7),(4,6),(4,7),(5,8),(6,8),(7,8)]))
for i in xrange(100000):
    if i%1000 == 0:
        print(i/1000)
    set_random_seed(i)
    L1 = posets.RandomLattice(9, 0.995)
    if L.is_isomorphic(L1):
        print("Found", i)
        break
else:
    print("Not found")

and it found nothing. However with p=0.9 it was fast and the lattice was found.

[obtext]

comment:14

Yes, it seems that values of p very close to 1 do inhibit some configurations. Perhaps the advice for p should be modified, but I don't have a clear sense of how.

[obtext]

comment:15

I wrote some quick (well, not that quick) test code to get a sense of how varying p changed the 'spread' of isomorphism classes of lattices produced:

def iso_invariant(L):
    """ Quick and dirty isomorphism-invariant, hopefully enough to distinguish
        most non-isomorphic pairs.
    """
    return (L.height(), L.width(), L.relations_number(), len(L.coatoms()), len(L.atoms()), len(L.meet_irreducibles()), len(L.join_irreducibles()))
def variation(n, p, k):
    S = set(iso_invariant(posets.RandomLattice(n, p)) for _ in xrange(k))
    return len(S)
def variations(n, k):
    ps = [0.4, 0.6, 0.8, 0.85, 0.9, 0.95, 0.99, 0.995]
    return [(p, variation(n,p,k)) for p in ps]

I ran it with n=9 and n=20, each time with k=1000. This leads me to think that p=0.9 may be a good choice:

sage: a = variations(9, 1000); a
[(0.400000000000000, 153),
 (0.600000000000000, 190),
 (0.800000000000000, 206),
 (0.850000000000000, 215),
 (0.900000000000000, 218),
 (0.950000000000000, 197),
 (0.990000000000000, 143),
 (0.995000000000000, 128)]
sage: a = variations(20, 1000); a
[(0.400000000000000, 939),
 (0.600000000000000, 970),
 (0.800000000000000, 982),
 (0.850000000000000, 989),
 (0.900000000000000, 988),
 (0.950000000000000, 981),
 (0.990000000000000, 891),
 (0.995000000000000, 796)]

[obtext]

comment:16

For comparison, this is what I get running with the unpatched RandomLattice code:

sage: a = variations(9, 1000); a
[(0.400000000000000, 145),
 (0.600000000000000, 184),
 (0.800000000000000, 229),
 (0.850000000000000, 219),
 (0.900000000000000, 214),
 (0.950000000000000, 224),
 (0.990000000000000, 202),
 (0.995000000000000, 211)]
sage: a = variations(20, 1000); a
[(0.400000000000000, 953),
 (0.600000000000000, 966),
 (0.800000000000000, 974),
 (0.850000000000000, 970),
 (0.900000000000000, 985),
 (0.950000000000000, 988),
 (0.990000000000000, 992),
 (0.995000000000000, 986)]

[sagetrac-git]

Changed commit from 4480bf2 to 64d3954

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

64d3954

Tweak advice about p. (See discussion on https://github.com/sagemath/sage/issues/27130.)

[obtext]

comment:18

Ping ... is this OK to be merged?

[jm58660]

Reviewer: Jori Mäntysalo

[jm58660]

comment:19

Yes, I think this is ready to go.

[vbraun]

Changed branch from u/alec.edgington/posets_randomlattice___cannot_generate_some_lattices to 64d3954