Opened 6 years ago

Closed 6 years ago

#19884 closed enhancement (fixed)

LatticePosets: Add is_relatively_complemented()

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.2
Component: combinatorics Keywords: latticeposet
Cc: chapoton Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 3170b43 (Commits, GitHub, GitLab) Commit: 3170b43a8966c7cb8be789cc52465dab375d71df
Dependencies: #19878 Stopgaps:

Status badges

Description

This patch adds a function to check if a lattice is relatively complemented or not.

Change History (16)

comment:1 Changed 6 years ago by jmantysalo

  • Branch set to u/jmantysalo/relatively_complemented

comment:2 Changed 6 years ago by jmantysalo

  • Commit set to e93c8699d9a6ae4378164f152891985aceb74e99
  • Status changed from new to needs_review

New commits:

e93c869Add is_relatively_complemented().

comment:3 Changed 6 years ago by git

  • Commit changed from e93c8699d9a6ae4378164f152891985aceb74e99 to 26725ab54e1c090b2a2d64d711f19c6e6dece105

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

26725abIterator instead of list.

comment:4 Changed 6 years ago by jmantysalo

  • Cc chapoton added

Frédéric, maybe you are not yet bored of reviewing...?

comment:5 Changed 6 years ago by dimpase

test, please ignore

comment:6 Changed 6 years ago by jmantysalo

  • Milestone changed from sage-7.0 to sage-7.1

comment:7 follow-up: Changed 6 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

For the reverse implication counterexample, could you also have it display that L is (co)atomic.

Also, could you make the following changes:

             sage: [Posets.ChainPoset(i).is_relatively_complemented() for
-            ....: i in range(5)]
+            ....:  i in range(5)]
             [True, True, True, False, False]
         Usually a lattice that is not relatively complemented contains elements
-        `l`, `m`, and `u` such that rank(`l`)+1 == rank(`m`) == rank(`u`)-1
-        and `m` is the only element in the interval `[l, u]`. We make an
+        `l`, `m`, and `u` such that `r(l) + 1 = r(m) = r(u) - 1`, where `r` is
+        the rank function and `m` is the only element in the interval `[l, u]`.
+        We construct an example where this does not hold::
         C = Counter(flatten([H.neighbors_out(e2) for e2 in H.neighbors_out(e1)]))
-            for e3, c in C.iteritems():
-                if c == 1:
-                    if len(H.closed_interval(e1, e3)) == 3:
-                        return False
+            if any(c == 1 and len(H.closed_interval(e1, e3)) == 3 for e3, c in C.iteritems()):
+                return False
         return True

Otherwise it is a positive review.

comment:8 in reply to: ↑ 7 Changed 6 years ago by jmantysalo

Replying to tscrim:

For the reverse implication counterexample, could you also have it display that L is (co)atomic.

I can do that, but is_coatomic() is not yet closed, see #19878.

Your suggestions to code and documentation seems good.

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

Then we should merge it in and set it as a dependency. It's already positively reviewed, so there shouldn't be any issues.

comment:10 Changed 6 years ago by git

  • Commit changed from 26725ab54e1c090b2a2d64d711f19c6e6dece105 to a08fac06be39a07de8f1c82ba0d0f2a3733579be

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

a08fac0Changes suggested by tscrim.

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

  • Status changed from needs_review to needs_work

Replying to tscrim:

Then we should merge it in and set it as a dependency. It's already positively reviewed, so there shouldn't be any issues.

But if we just wait for the next beta, shouldn't this then work without any extra job to do?

I made changes you suggested, but I'm compiling and testing - so this is in needs_work.

comment:12 Changed 6 years ago by jmantysalo

  • Milestone changed from sage-7.1 to sage-7.2

I got error from docbuilding, but it seems not to relate lattices.py. Strange.

comment:13 Changed 6 years ago by tscrim

  • Branch changed from u/jmantysalo/relatively_complemented to public/posets/add_is_relatively_complemented-19884
  • Commit changed from a08fac06be39a07de8f1c82ba0d0f2a3733579be to 3170b43a8966c7cb8be789cc52465dab375d71df
  • Dependencies set to #19878
  • Status changed from needs_work to positive_review

Chances are that it this will get merged, along with #19878, in beta1. So I have merged in #19878 because that is 0 additional work in reviewing. I did not get any docbuilding, no doctesting errors with #19878, and your changes look good. So I'm setting a positive review.


New commits:

e2e53d3Merge branch 'u/jmantysalo/relatively_complemented' of trac.sagemath.org:sage into public/posets/add_is_relatively_complemented-19884
9b0b30bAdd coatomic, simpler code.
533d660Spaces removed.
3170b43Merge branch 'u/jmantysalo/simpler_atomic' of trac.sagemath.org:sage into public/posets/add_is_relatively_complemented-19884

comment:14 Changed 6 years ago by jmantysalo

Thanks!

comment:15 Changed 6 years ago by tscrim

Thank you for all your work on posets.

comment:16 Changed 6 years ago by vbraun

  • Branch changed from public/posets/add_is_relatively_complemented-19884 to 3170b43a8966c7cb8be789cc52465dab375d71df
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.