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:

Status badges

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 jmantysalo

  • Branch set to u/jmantysalo/antidoubling-part-2

comment:2 Changed 5 years ago by jmantysalo

  • Commit set to 79faf902d860d1a19091d9906a7da01a18440a41
  • Status changed from new to needs_review

New commits:

79faf90Another "antidoubling" function.

comment:3 Changed 5 years ago by jmantysalo

  • 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 git

  • Commit changed from 79faf902d860d1a19091d9906a7da01a18440a41 to a80e877f130d8fcfd18213d2d9bac2de1447942c

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

a80e877Correct example.

comment:5 Changed 5 years ago by jmantysalo

  • 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 git

  • Commit changed from a80e877f130d8fcfd18213d2d9bac2de1447942c to ee37ec56626c5a48efdbb26e4658bede69a30db9

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

ee37ec5Merge branch 'develop' into t/22693/antidoubling-part-2

comment:7 Changed 5 years ago by jmantysalo

Is there something I can do to make reviewing easier?

comment:8 Changed 5 years ago by jmantysalo

  • Cc tscrim added

Travis? The code is quite direct implementation from the paper.

comment:9 follow-up: Changed 5 years ago by tscrim

  • 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 git

  • Commit changed from ee37ec56626c5a48efdbb26e4658bede69a30db9 to 8597c98fcf5866ad8c1759cfee296cab19b2328c

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

cf697ddMerge branch 'develop' into t/22693/antidoubling-part-2
8597c98for-loop to any-clause.

comment:11 in reply to: ↑ 9 Changed 5 years ago by jmantysalo

Replying to tscrim:

One little thing:

Done. (And tested, just to be sure...)

comment:12 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

Thanks.

comment:13 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/antidoubling-part-2 to 8597c98fcf5866ad8c1759cfee296cab19b2328c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.