Opened 5 years ago
Closed 5 years ago
#22693 closed enhancement (fixed)
LatticePoset: Antidoubling, part 2
Reported by: | jmantysalo | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.0 |
Component: | combinatorics | Keywords: | |
Cc: | mantepse, tscrim | Merged in: | |
Authors: | Jori Mäntysalo | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 8597c98 (Commits, GitHub, GitLab) | Commit: | 8597c98fcf5866ad8c1759cfee296cab19b2328c |
Dependencies: | Stopgaps: |
Description
This patch adds a backend function to see if a lattice is constructible with Alan Day's doubling construction of convex subsets.
To be added to frontend #22648 later.
Change History (13)
comment:1 Changed 5 years ago by
- Branch set to u/jmantysalo/antidoubling-part-2
comment:2 Changed 5 years ago by
- Commit set to 79faf902d860d1a19091d9906a7da01a18440a41
- Status changed from new to needs_review
comment:3 Changed 5 years ago by
- Status changed from needs_review to needs_work
Arghs, the example is incorrect. Example from http://www.math.hawaii.edu/~jb/inflation.pdf page 8 shows how to construct a lattice by doubling a non-convex set ("Reppe's lattice"), but begins with a 9-element lattice that is not constructible by any doubling.
comment:4 Changed 5 years ago by
- Commit changed from 79faf902d860d1a19091d9906a7da01a18440a41 to a80e877f130d8fcfd18213d2d9bac2de1447942c
Branch pushed to git repo; I updated commit sha1. New commits:
a80e877 | Correct example.
|
comment:5 Changed 5 years ago by
- Status changed from needs_work to needs_review
Now a correct example. It is done with
L = Posets.BooleanLattice(3) L = L.day_doubling([1,3]) def double_no_check(self, S): S_ = [self._element_to_vertex(e) for e in S] g = self.hasse_diagram() g.relabel(lambda e: (e, 0)) for e in S: g.add_edge((e, 0), (e, 1)) for e_up in self.upper_covers(e): if e_up in S: g.add_edge((e, 1), (e_up, 1)) else: g.delete_edge((e, 0), (e_up, 0)) g.add_edge((e, 1), (e_up, 0)) return LatticePoset(g) L = double_no_check(L, [(3, 1), (6, 0), (2, 0), (5, 0), (1, 1), (4, 0)])
where (3, 0)
shows that the subset to double is not convex.
I may be that there is no smaller example of a lattice costructible by doublings of some subset but not constructible by doublings of convex subset.
comment:6 Changed 5 years ago by
- Commit changed from a80e877f130d8fcfd18213d2d9bac2de1447942c to ee37ec56626c5a48efdbb26e4658bede69a30db9
Branch pushed to git repo; I updated commit sha1. New commits:
ee37ec5 | Merge branch 'develop' into t/22693/antidoubling-part-2
|
comment:7 Changed 5 years ago by
Is there something I can do to make reviewing easier?
comment:8 Changed 5 years ago by
- Cc tscrim added
Travis? The code is quite direct implementation from the paper.
comment:9 follow-up: ↓ 11 Changed 5 years ago by
- Reviewers set to Travis Scrimshaw
One little thing:
- for ji in congs_ji[cong]: - if self.is_lequal(ji, mi): - return False + if any(self.is_lequal(ji, mi) for ji in congs_ji[cong]): + return False
IMO this is cleaner (and I think it might be marginally faster). Otherwise LGTM.
comment:10 Changed 5 years ago by
- Commit changed from ee37ec56626c5a48efdbb26e4658bede69a30db9 to 8597c98fcf5866ad8c1759cfee296cab19b2328c
comment:11 in reply to: ↑ 9 Changed 5 years ago by
comment:13 Changed 5 years ago by
- Branch changed from u/jmantysalo/antidoubling-part-2 to 8597c98fcf5866ad8c1759cfee296cab19b2328c
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
Another "antidoubling" function.