Opened 3 years ago

Closed 3 years ago

#21002 closed enhancement (fixed)

LatticePoset: certificates for non-semimodularity

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.4
Component: combinatorics Keywords:
Cc: kdilks, tscrim Merged in:
Authors: Jori Mäntysalo Reviewers: Kevin Dilks
Report Upstream: N/A Work issues:
Branch: c059d46 (Commits) Commit: c059d46ef3a9f7150f988fc7889dc39ef7defd95
Dependencies: Stopgaps:

Description (last modified by jmantysalo)

Add a certificate-option to the functions checking if a lattice is semimodular.

Change History (11)

comment:1 Changed 3 years ago by jmantysalo

  • Cc kdilks added
  • Status changed from new to needs_info

Kevin: First part is #20980, but a question about interface part:

What should be the certificate? I.e. a sublattice, a list of five elements of the sublattice, or list of three elements violating the defining property? Or a choise between those?

comment:2 Changed 3 years ago by jmantysalo

  • Branch set to u/jmantysalo/latticeposet__certificates_for_non__semi_modularity_and_non_distributivity

comment:3 Changed 3 years ago by jmantysalo

  • Cc tscrim added
  • Commit set to 10cb3ca6bcfb3d79793200b9f1def5be584a8e46
  • Description modified (diff)
  • Milestone changed from sage-feature to sage-7.3
  • Status changed from needs_info to needs_review
  • Summary changed from LatticePoset: certificates for non-[semi]modularity and non-distributivity to LatticePoset: certificates for non-semimodularity

I thinked about this, and here is first part.

First, this is faster for almost all cases. But for small lattices with already computed meet, join and rank function this is slower. However, the speedup for, say, BooleanLattice(10) is big. With current code the time to check semimodularity is 4,9 seconds for first time and 0,6 seconds for second time. With this patch it drops to 0,1 seconds.

Second, this adds a certificate-option.

I thinked this, and I guess we should use this by-definition -certificate, and later implement isomoprhic_sublattices().

I will put this to needs_review and later try to do something similar to is_modular() and is_distributive().


New commits:

10cb3caModifications to semimodularity tests.

comment:4 Changed 3 years ago by jmantysalo

  • Milestone changed from sage-7.3 to sage-7.4

rc0 is out.

comment:5 Changed 3 years ago by jmantysalo

Just pinging... Nothing very complicated here.

comment:6 follow-up: Changed 3 years ago by kdilks

Even though it's a "hidden" function, I don't think the method in hasse_diagram.py should be called is_semimodular() if it's not in some way return a boolean (either directly, or as part of a tuple along with certificate).

comment:7 Changed 3 years ago by git

  • Commit changed from 10cb3ca6bcfb3d79793200b9f1def5be584a8e46 to c9a365cb5bd5fd0e4d8916650e219c35cebc64d2

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

c9a365cChange internal function name.

comment:8 Changed 3 years ago by git

  • Commit changed from c9a365cb5bd5fd0e4d8916650e219c35cebc64d2 to c059d46ef3a9f7150f988fc7889dc39ef7defd95

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

c059d46Forgot *lower* semimodular.

comment:9 in reply to: ↑ 6 Changed 3 years ago by jmantysalo

Replying to kdilks:

Even though it's a "hidden" function, I don't think the method in hasse_diagram.py should be called is_semimodular() if it's not in some way return a boolean (either directly, or as part of a tuple along with certificate).

True. Changed that.

comment:10 Changed 3 years ago by kdilks

  • Reviewers set to Kevin Dilks
  • Status changed from needs_review to positive_review

comment:11 Changed 3 years ago by vbraun

  • Branch changed from u/jmantysalo/latticeposet__certificates_for_non__semi_modularity_and_non_distributivity to c059d46ef3a9f7150f988fc7889dc39ef7defd95
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.