Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#26099 closed enhancement (fixed)

trim lattices

Reported by: Frédéric Chapoton Owned by:
Priority: minor Milestone: sage-8.5
Component: combinatorics Keywords:
Cc: Jori Mäntysalo Merged in:
Authors: Frédéric Chapoton Reviewers: Jori Mäntysalo
Report Upstream: N/A Work issues:
Branch: 97ad922 (Commits, GitHub, GitLab) Commit: 97ad92209130b6328a9042f96e40897af0e583db
Dependencies: Stopgaps:

Status badges

Description (last modified by Jori Mäntysalo)

This patch adds is_trim() to finite lattices.

Change History (23)

comment:1 Changed 4 years ago by Frédéric Chapoton

Branch: u/chapoton/26099
Status: newneeds_review

comment:2 Changed 4 years ago by git

Commit: 72846f5d843babe368c4862684d106dc3343230a

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

72846f5adding a method to test if a lattice is trim

comment:3 Changed 4 years ago by Jori Mäntysalo

Status: needs_reviewneeds_work

All other functions always returns a pair when certificate=True, i.e.

x.foo() == x.foo(certificate=True)[0]

Change to this convention is possible, but should be discussed in sage-devel.

I suppose this also conflicts with #26095 because of a cross-link.

comment:4 Changed 4 years ago by git

Commit: 72846f5d843babe368c4862684d106dc3343230a0490414339d1dcc004cb6a51e80e8f5e4d76d8fe

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

0490414details

comment:5 Changed 4 years ago by Frédéric Chapoton

done. For the conflict, I will just rebase the branch here when needed.

comment:6 Changed 4 years ago by Frédéric Chapoton

Status: needs_workneeds_review

comment:7 Changed 4 years ago by git

Commit: 0490414339d1dcc004cb6a51e80e8f5e4d76d8fe5ae834d5976231e024e5f2e82767f551cf3436f3

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

5ae834dfix doctest in 26099

comment:8 Changed 4 years ago by Jori Mäntysalo

Reviewers: Jori Mäntysalo

comment:9 Changed 4 years ago by Jori Mäntysalo

Status: needs_reviewpositive_review

OK.

(References should go to the master bibliography file, but that can be corrected later.)

comment:10 Changed 4 years ago by Jori Mäntysalo

A question still: The paper you refers says that a trim lattice must have a chain of maximum length having only left modular elements. The code seems to search a maximal chain having only left modular elements. So is the code sufficient?

comment:11 in reply to:  10 ; Changed 4 years ago by Frédéric Chapoton

Replying to jmantysalo:

A question still: The paper you refers says that a trim lattice must have a chain of maximum length having only left modular elements. The code seems to search a maximal chain having only left modular elements. So is the code sufficient?

Right. I am also using a result of https://arxiv.org/abs/1712.10123, saying that in a trim lattice, left modular elements are exactly the elements that belong to the spine (union of all chains of maximum length).

comment:12 in reply to:  11 Changed 4 years ago by Jori Mäntysalo

Replying to chapoton:

Replying to jmantysalo:

A question still: The paper you refers says that a trim lattice must have a chain of maximum length having only left modular elements. The code seems to search a maximal chain having only left modular elements. So is the code sufficient?

Right. I am also using a result of https://arxiv.org/abs/1712.10123, saying that in a trim lattice, left modular elements are exactly the elements that belong to the spine (union of all chains of maximum length).

But just this is what I am saying. You only need to check one chain of a maximum cardinality, not all of them. But your code does not do that, it tries to found some maximal chain, not necessarily of the max cardinality.

comment:13 Changed 4 years ago by Frédéric Chapoton

Status: positive_reviewneeds_work

Ha. Indeed. So this needs work. Let us keep this aside for some time, I have more urgent business right now.

comment:14 in reply to:  13 Changed 4 years ago by Jori Mäntysalo

Replying to chapoton:

Ha. Indeed. So this needs work. Let us keep this aside for some time, I have more urgent business right now.

OK. Could this be just

self.is_extremal() and all(self.is_left_modular_element(e) for e in self.height(certificate=True)[1])

?

comment:15 Changed 4 years ago by git

Commit: 5ae834d5976231e024e5f2e82767f551cf3436f3fb3ed7370e1afbc5f5173440e2c6431482f4dc6b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

fb3ed73adding a method to test if a lattice is trim

comment:16 Changed 4 years ago by Frédéric Chapoton

Here is a new tentative, along the lines of your proposal. I did compare the timings with the corrected version of my code, and they were very similar. So I kept the simplest.

comment:17 Changed 4 years ago by Frédéric Chapoton

Status: needs_workneeds_review

comment:18 Changed 4 years ago by Jori Mäntysalo

Description: modified (diff)
Status: needs_reviewpositive_review

OK.

comment:19 Changed 4 years ago by Volker Braun

Status: positive_reviewneeds_work

Merge conflict

comment:20 Changed 4 years ago by git

Commit: fb3ed7370e1afbc5f5173440e2c6431482f4dc6b97ad92209130b6328a9042f96e40897af0e583db

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

97ad922Merge branch 'u/chapoton/26099' in 8.4.rc0

comment:21 Changed 4 years ago by Frédéric Chapoton

Status: needs_workpositive_review

trivial rebase, I am setting back to positive

comment:22 Changed 4 years ago by Volker Braun

Branch: u/chapoton/2609997ad92209130b6328a9042f96e40897af0e583db
Resolution: fixed
Status: positive_reviewclosed

comment:23 Changed 4 years ago by Erik Bray

Milestone: sage-8.4sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.