Opened 5 years ago
Closed 5 years ago
#22648 closed enhancement (fixed)
LatticePoset: test if lattice is constructible by doublings
Reported by: | jmantysalo | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.0 |
Component: | combinatorics | Keywords: | |
Cc: | chapoton, tscrim | Merged in: | |
Authors: | Jori Mäntysalo | Reviewers: | Martin Rubey |
Report Upstream: | N/A | Work issues: | |
Branch: | 9974715 (Commits, GitHub, GitLab) | Commit: | 9974715d4de393b776eaefdc8f33113224a888cd |
Dependencies: | Stopgaps: |
Description
Add functions to test if a lattice is constructible from the one-element lattice with Day doubling of 1) interval, 2) lower pseudo-interval, 3) upper pseudo-interval and 4) any convex subset.
Change History (30)
comment:1 Changed 5 years ago by
- Cc chapoton tscrim added
- Status changed from new to needs_info
comment:2 follow-up: ↓ 3 Changed 5 years ago by
How about is_interval_doubling()
?
comment:3 in reply to: ↑ 2 Changed 5 years ago by
Replying to tscrim:
How about
is_interval_doubling()
?
For case 1 only? Could be, got to think about this.
We now have is_orthocomplemented()
(by me) with optional parameter unique
. What you think about that, and having something like is_doubling_constructable()
with mandratory string parameter having possible values 'convex', 'intevar'
etc?
comment:4 follow-up: ↓ 6 Changed 5 years ago by
Some people (at least McConville? https://arxiv.org/abs/1504.05213) use congruence_uniform
instead of bounded, I think:
5.2 Congruence-normal and congruence-uniform lattices
A finite lattice L is congruence-normal if there exists a sequence of lattices L_1,..., L_l such that L_1 is the one-element lattice, L_l = L, and for all i, there exists an order convex subset C_i of L_i such that L_{i+1} = L_i[Ci].
A lattice is congruence-uniform if it is both congruence-normal and semidistributive.
comment:5 Changed 5 years ago by
- Reviewers set to Martin Rubey
comment:6 in reply to: ↑ 4 Changed 5 years ago by
Replying to mantepse:
Some people (at least McConville? https://arxiv.org/abs/1504.05213) use
congruence_uniform
instead of bounded, I think:
Duh. We already have is_uniform
after #21861.
A finite lattice L is congruence-normal if there exists a sequence of lattices L_1,..., L_l such that L_1 is the one-element lattice, L_l = L, and for all i, there exists an order convex subset C_i of L_i such that L_{i+1} = L_i[Ci].
A lattice is congruence-uniform if it is both congruence-normal and semidistributive.
Page 3 says this more directly "congruence-uniform lattice is any lattice constructable by a sequence of interval doubings."
comment:7 follow-up: ↓ 9 Changed 5 years ago by
In case it's possible, it would be great if the code could also produce a certificate.
For myself personally, what would be wonderful is a function that takes a lattice and produces all intervals that can be collapsed. (I assume that, no matter which intervall is collapsed, the result should again be congruence uniform, if the original was. But I admit that I do not know.)
comment:8 Changed 5 years ago by
- Milestone changed from sage-8.0 to sage-wishlist
Certificate should be possible.
First see a term 'inflation' in http://www.math.hawaii.edu/~jb/inflation.pdf and also figure 3 at page 8. Maybe doubling construction should be expanded to municipal subsets?
For decomposing see https://hal.archives-ouvertes.fr/hal-01282151/document.
But I can't be sure when I will look at this, and so I mark this as wishlist queue.
comment:9 in reply to: ↑ 7 Changed 5 years ago by
Replying to mantepse:
For myself personally, what would be wonderful is a function that takes a lattice and produces all intervals that can be collapsed.
I think it should be something like this:
def antidouble(self): ji = self.join_irreducibles() mi = self.meet_irreducibles() h = {} i = 0 for l in self.level_sets(): for e in l: h[e] = i i += 1 for a in ji: a_ = self.lower_covers(a)[0] for b in mi: if self.compare_elements(a, b) is not None: continue b_ = self.upper_covers(b)[0] if h[b]-h[a_] == h[b_]-h[a]: A = self.interval(a_, b) B = self.interval(a, b_) if len(A) == len(B): if self.subposet(A).is_isomorphic(self.subposet(B)): if LatticePoset(self.subposet([e for e in self if e not in B])).day_doubling(A).is_isomorphic(self): print((a_, b), (a, b_))
but of course is much faster to work directly with Hasse Diagram. Having temporary posets is bad, as they eat memory that is not released until you restart the whole worksheet.
comment:10 Changed 5 years ago by
Wow! Thank you!
There must be a small bug however, because
antidouble(posets.PentagonPoset())
should print a collapsible interval (the middle relation in the longer chain), but doesn't.
In case I find out, I'll let you know!
comment:11 Changed 5 years ago by
True, but I think they are just the double irreducible elements that are not seen by this code.
Anyway, I guess I should extend Posets.RandomLattice
to get some test material.
comment:12 Changed 5 years ago by
Random code could be like
def random_bounded(n, p): """ Return a random "bounded" lattice. I.e. a lattice that can be made from the one-element lattice by doubling an interval. """ if n < 4: return Posets.ChainPoset(n) g = digraphs.Path(2) g = Posets.PentagonPoset().hasse_diagram() n = n - 2 while n: a = g.random_vertex() a_up = list(g.depth_first_search(a)) b = a_up[randint(0, ceil(len(a_up)*p*random())-1)] b_down = list(g.depth_first_search(b, neighbors=g.neighbors_in)) S = [x for x in a_up if x in b_down] if n-len(S) < 0 or len(S) == 0: continue # New try... g_S = g.subgraph(S) g_S.relabel(lambda x: (1, x)) g = g.union(g_S) for e in g.neighbor_out_iterator(b): g.delete_edge(b, e) g.add_edge((1, b), e) for e in S: g.add_edge(e, (1, e)) g.relabel() n -= len(S) return LatticePoset(g)
to test try for example
set_random_seed(0) random_bounded(15, 1).show()
comment:13 Changed 5 years ago by
This needs more reading and thinking.
But a question: If we have a decomposition -- as certificate
or as a specific function -- what should be the output type? Some kind of tuple or list, I guess.
comment:14 Changed 5 years ago by
More about this. Free Lattices by Ralph S. Freese, Jaroslav Ježek and James Bryant Nation p. 76 says that a lattice L
is lower bounded iff |Ji(L)| = |Ji(Con L)|
, and of course dually for upper bounded. The congurence lattice of a lattice is always distributive. A distributive lattice L has |Ji(L)| = |Mi(L)|
. Hence a lattice L
can be (totally) bounded only if it has |Ji(L)| = |Mi(L)|
. That can be used as a fast check to reject lattices that clearly can't be (totallyt) bounded.
And of course Posets.DiamondPoset(5)
shows that the last "if" is not "iff".
But I must continue to think and code. For me they are almost the same thing.
comment:15 Changed 5 years ago by
New try, kind of proof-of-concept:
def antidouble(L): H = L._hasse_diagram at = H.atoms_of_congruence_lattice() for cong in at: if all(len(p) <= 2 for p in cong): tmp = [p for p in cong if len(p) == 2] tmp1 = [min(p) for p in tmp] tmp2 = [max(p) for p in tmp] LatticePoset(L.subposet([L._vertex_to_element(e) for e in H if e not in tmp2])).show() print([L._vertex_to_element(e) for e in tmp1]) break else: print("Nothing to double.")
comment:16 Changed 5 years ago by
- Branch set to u/jmantysalo/latticeposet__test_if_lattice_is_constructible_by_doublings
comment:17 Changed 5 years ago by
- Commit set to 94ad32ce12bbc0a39a9fab4af83a8f2127e936a4
- Milestone changed from sage-wishlist to sage-8.0
- Status changed from needs_info to needs_review
OK, I started working with this. I think it is easier to proceed with smaller parts, and so put this on needs_review. The code is trivial, so the main question is about the design.
New commits:
94ad32c | Add is_doubling_constructible().
|
comment:18 Changed 5 years ago by
Currently compiling...
In any case, I'd prefer is_constructible_by_doublings
over is_doubling_constructible
. I am somewhat surprised that the test is now so simple.
comment:19 follow-up: ↓ 22 Changed 5 years ago by
Another minor thing is that you should include something like the following in the docstring:
A lattice L is lower bounded if and only if |Ji(L)| = |Ji(Con L)|, dually for upper bounded, see Free Lattices by Ralph S. Freese, Jaroslav Ježek and James Bryant Nation p. 76.
Note that a congruence lattice of a lattice is always distributive, and a distributive lattice L has |Ji(L)| = |Mi(L)|. Hence a lattice L can be totally)bounded only if it has |Ji(L)| = |Mi(L)|.
I'd like to ask you to also include a reference to the term congruence uniform (eg. McConville?).
comment:20 Changed 5 years ago by
- Commit changed from 94ad32ce12bbc0a39a9fab4af83a8f2127e936a4 to 2274d3765ec515b4e6efa021fe59870ab31d8219
Branch pushed to git repo; I updated commit sha1. New commits:
2274d37 | Change name etc.
|
comment:21 Changed 5 years ago by
- Commit changed from 2274d3765ec515b4e6efa021fe59870ab31d8219 to 9974715d4de393b776eaefdc8f33113224a888cd
Branch pushed to git repo; I updated commit sha1. New commits:
9974715 | LaTeX formatting.
|
comment:22 in reply to: ↑ 19 Changed 5 years ago by
Replying to mantepse:
I changed the name and add a reference. I think that
Another minor thing is that you should include something like the following in the docstring:
Note that a congruence lattice of a lattice is always distributive, and a distributive lattice L has |Ji(L)| = |Mi(L)|. Hence a lattice L can be totally)bounded only if it has |Ji(L)| = |Mi(L)|.
is not needed to say, as we don't rely on it. This only uses Python's short-circuit evaluation of a==b==c
as an optimization.
I'd like to ask you to also include a reference to the term congruence uniform (eg. McConville?).
I don't think it is necessary.
I am somewhat surprised that the test is now so simple.
I think it comes from "de-doubling" algorithm quite naturally. Every interval doubling adds exactly one meet- and one join-irreducible element, i.e. the upper cover of bottom of the set to double and the top of the set to double. On the other direction if |Ji(Con L)|
equals to |Ji(L)|
, then every principal congruence must correspond to one of those "de-doubling" congruence.
comment:23 follow-up: ↓ 25 Changed 5 years ago by
Looks good! The sequence
[len([1 for L in posets(r) if L.with_bounds().is_lattice() and LatticePoset(L.with_bounds()).is_constructible_by_doublings('interval')]) for r in range(1,8)] [1,2,4,9,22,60,174]
is not in the OEIS...
comment:24 Changed 5 years ago by
- Status changed from needs_review to positive_review
comment:25 in reply to: ↑ 23 Changed 5 years ago by
Replying to mantepse:
Looks good! The sequence
[len([1 for L in posets(r) if L.with_bounds().is_lattice() and LatticePoset(L.with_bounds()).is_constructible_by_doublings('interval')]) for r in range(1,8)] [1,2,4,9,22,60,174]is not in the OEIS...
Thanks for the review.
OEIS is missing most of series related to lattice enumeration. I have added some, see for example https://oeis.org/A261994. Here is code if you want to add more:
N = 8 LL = [] for i in range(N-2): x = [] for P in Posets(i): try: x.append(LatticePoset(P.with_bounds())) except ValueError: pass LL.append(x) functions = ['is_planar', 'is_upper_semimodular'] for f in functions: print(f) for i in range(2, N): print(i, len([L for L in LL[i-2] if attrcall(f)(L)]))
comment:26 follow-up: ↓ 27 Changed 5 years ago by
Side question: is it clear (or false) that the number of doublings of intervals to construct a lattice is independent of the particular doublings chosen?
comment:27 in reply to: ↑ 26 Changed 5 years ago by
Replying to mantepse:
Side question: is it clear (or false) that the number of doublings of intervals to construct a lattice is independent of the particular doublings chosen?
I think so, and even more has been said in some paper: If S
and T
are convex subsets so that their union is convex non-connected subset, then L[S][T]
and L[T][S]
are isomorphic.
comment:28 follow-up: ↓ 29 Changed 5 years ago by
*cough*authorname*cough*
comment:29 in reply to: ↑ 28 Changed 5 years ago by
Replying to tscrim:
*cough*authorname*cough*
Duh. Added.
Btw, this can be optimized much more. First, we don't need to count all Ji(Con L)
, as if we found a, b \in Ji(L)
such that Cong(a, a_) == Cong(b, b_)
, where e_
is the only element covered by e
, we can't have |Ji(Con L)|
as big as |Ji(L)|
.
Next, a congruence generated by "antidoubling" can only have blocks of one or two element. Hence we can stop when we found even one e
such that Cong(e, e_)
has at least one congruence block of three or more elements.
comment:30 Changed 5 years ago by
- Branch changed from u/jmantysalo/latticeposet__test_if_lattice_is_constructible_by_doublings to 9974715d4de393b776eaefdc8f33113224a888cd
- Resolution set to fixed
- Status changed from positive_review to closed
What should be the names for these functions?
4 is called congruence normal, 2 and 3 as lower bounded and upper bounded and 1 as bounded. But we can't add
is_bounded()
with different meaning to lattices that we already have for posets.(See for example http://www.math.hawaii.edu/~jb/inflation.pdf.)