LatticePoset: add maximal_sublattices()

[jm58660]

This adds a new function that computes maximal (proper) sublattices of the lattice.

It could be faster to reverse thinking: instead of computing sublattice try to get a minimal "remainder" of sublattice. For example the remainder must be a connected poset and it's every minimal element may not have more than one lower cover. However, this slow implementation at least works, and can be used as a checkpoint when making faster implementations.

CC: @nathanncohen @kevindilks

Component: combinatorics

Author: Jori Mäntysalo, Travis Scrimshaw

Branch/Commit: d85c873

Reviewer: Travis Scrimshaw, Jori Mäntysalo

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

[jm58660]

Branch: u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__

[jm58660]

Commit: 4b47df9

[jm58660]

comment:2

There is now some code that at least seems to work. This is quite interesting optimization problem. Can this be made to real maximal_sublattices_iterator() instead of maximal_sublattices() (that internally generates some non-maximal sublattices and then discards them).

I tried googling some time, but find no algorithm for this. This is somewhat ad hoc solution.

---

New commits:

4b47df9

Added a function.

[sagetrac-git]

Changed commit from 4b47df9 to 5ede78b

[sagetrac-git]

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

5ede78b

Some optimization.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ef073c1

New function for maximal_sublattices.

[sagetrac-git]

Changed commit from 5ede78b to ef073c1

[jm58660]

Author: Jori Mäntysalo

[jm58660]

comment:6

Ping... Anybody wants to look at the code? This is necessary part in the road to frattini_sublattice().

[tscrim]

comment:8

Two minor things:

• I think you could change the test sorted([sorted(list(x)) for x in ms]) to sorted(ms, key=sorted) (note that I didn't actually try this).

• Could you add a space around the < comparisons to help improve readability?

Kevin, if you want to do the full review, please go ahead. I'm not sure I will have enough time to throughly test this.

[sagetrac-git]

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

8dbb1d8

Two minor changes.

[sagetrac-git]

Changed commit from ef073c1 to 8dbb1d8

[jm58660]

comment:10

Here is one test lattice:

z={'d': [1,2,3], 1:['l', 4], 2:[4,'c'], 3:['r',4], 4:[5], 5:[6,13], 6:[7,11], 7:[8,14], 8:[9,12], 9:[10,15], 10:['u'], 'l':[11], 11:[12], 12:['u'], 'r':[13], 13:[14], 14:[15], 15:['u'], 'c':[10]}
M3min=LatticePoset(z)

(from http://www.math.hawaii.edu/~ralph/Preprints/combined.pdf you can find more). Do you want some test code? You can make a random lattice (for example random poset + completion_by_cuts()), and test by adding one random element to maximal sublattice - it should generate whole lattice. Or make a test like #18562 and see if a random maximal sublattice is found in the list of sublattices.

[fchapoton]

comment:12

needs rebase, does not apply

[sagetrac-git]

Changed commit from 8dbb1d8 to 24b10dd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

24b10dd

Add maximal_sublattices().

[jm58660]

comment:14

Replying to @fchapoton:

needs rebase, does not apply

Done that, should work now. I will change this to needs_review after checking myself that this compiles and works.

[tscrim]

Changed branch from u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__ to u/tscrim/maximal_sublattices_iterator-18567

[tscrim]

Changed commit from 24b10dd to none

[tscrim]

comment:16

I made some minor reviewer changes. If you're happy with them, then go ahead and set a positive review.

[tscrim]

Reviewer: Travis Scrimshaw

[jm58660]

comment:17

?? Branch-field is red, so I guess you made a typo.

[tscrim]

comment:18

I think it's because beta3 was just released and my branch is based off beta2.

[jm58660]

comment:19

Replying to @tscrim:

I think it's because beta3 was just released and my branch is based off beta2.

But I don't see the "commits"-link, like there is when the code needs rebasing.

[sagetrac-git]

Commit: d85c873

[sagetrac-git]

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

24b10dd	Add maximal_sublattices().
ffe4fb8	Merge branch 'u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__
d85c873	Some reviewer tweaks.

[tscrim]

comment:21

It seems like it didn't push it for some reason. Fixed.

[jm58660]

Changed author from Jori Mäntysalo to Jori Mäntysalo, Travis Scrimshaw

[jm58660]

comment:22

Replying to @tscrim:

I made some minor reviewer changes. If you're happy with them, then go ahead and set a positive review.

Thank you! Compiles & works.

(Now we just put this to production, and wait for someone to come up with better algorithm...)

[jm58660]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Jori Mäntysalo

[vbraun]

Changed branch from u/tscrim/maximal_sublattices_iterator-18567 to d85c873