Opened 3 years ago
Closed 3 years ago
#21419 closed enhancement (fixed)
LatticePoset: "kappa function" and relations AD
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  combinatorics  Keywords:  
Cc:  tscrim, chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  7c192cd (Commits)  Commit:  7c192cd06f1a5f88dcee9b6662863956d470bb8e 
Dependencies:  Stopgaps: 
Description
I would like to implement relations AD from http://www.math.hawaii.edu/~jb/unbound.ps
It seems natural to first start from the function that is marked as greek letter kappa at the paper. Here I gave it just a name kappa()
.
Change History (25)
comment:1 Changed 3 years ago by
 Branch set to u/jmantysalo/kappa
comment:2 Changed 3 years ago by
 Commit set to bc21b06d68c34dbad5c0039bd99883501485d157
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 Cc tscrim added
Travis: What you think about the name of the function? Is there (at least) educational value of having a kappafunction also "visible", i.e. at lattices.py
and not only indirectly available at hasse_diagram.py
?
comment:4 followup: ↓ 5 Changed 3 years ago by
From your description, this seems like it is not a standard notation/function (I don't actually know). So I feel it doesn't make sense to call it kappa
and instead give it a slightly more descriptive name. Perhaps maximal_incomparable_element
?
comment:5 in reply to: ↑ 4 Changed 3 years ago by
Replying to tscrim:
From your description, this seems like it is not a standard notation/function (I don't actually know). So I feel it doesn't make sense to call it
kappa
and instead give it a slightly more descriptive name. Perhapsmaximal_incomparable_element
?
That's good name!
By googling I found that Lattices and Ordered Sets by Steven Roman p. 225 uses the name "kappa function", but I can not see the page itself. The symbol itself seems to be coherently used for this, see Algebras and Orders by Ivo G. Rosenberg and Gert Sabidussi, or http://journals.cambridge.org/download.php?file=%2FJAZ%2FJAZ1_63_01%2FS1446788700000355a.pdf&code=9cc17eeb007fe5d050aadfcbedad50cd, but I did not found other mentions of "kappa function" spelled out.
Should I ask from J. B. Nation himself?
comment:6 Changed 3 years ago by
It's okay; some textbooks is good enough reference for me. I leave it up to you if you want to change the name.
comment:7 Changed 3 years ago by
 Status changed from needs_review to needs_info
Hmm.. Hard to say. I left this open and think.
Name maximal_incomparable_element
would suggest that function works for all elements in every poset, and it really could be defined so. But I have seen it only used for joinirreducibles.
comment:8 Changed 3 years ago by
 Status changed from needs_info to needs_review
Back to needs_review. This can not be "maximal incomparable element", as that is not the case in special case where an element covers a doubly irreducible element; then \kappa(a)=a
. Hence I can see no easy name for the function at all, except "kappa".
Now the question is should we have this available at "interface level", i.e. in lattices.py
at all, or just hidden in hasse_diagram.py
. Also, is it more clear to explicitly say in the documentation that this is the greatest incomparable elemenet excluding the special case?
comment:9 followup: ↓ 13 Changed 3 years ago by
 Cc chapoton added
CC'd Frédéric. What you think about the name, and should this be available at lattices.py
?
I found a book that uses a section title "The $\kappa$ function". But to make this more complicated: there are also dual functions, i.e. "kappa'" defined for meetirreducibles.
comment:10 Changed 3 years ago by
 Status changed from needs_review to needs_work
Arghs, a braindead bug in special case handling.
comment:11 Changed 3 years ago by
 Commit changed from bc21b06d68c34dbad5c0039bd99883501485d157 to 3359c29fdc997a58ee0054918218f8502c8d8877
Branch pushed to git repo; I updated commit sha1. New commits:
3359c29  A correction, modify docstring.

comment:12 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:13 in reply to: ↑ 9 Changed 3 years ago by
Replying to jmantysalo:
I found a book that uses a section title "The $\kappa$ function". But to make this more complicated: there are also dual functions, i.e. "kappa'" defined for meetirreducibles.
That tells me we need to change either the function title or arguments, and I'd rather change the title. I go back to maximal_incomparable_element
, and as long as we document that it is only for joinirreducible elements (which includes an appropriate error message), it is okay.
comment:14 Changed 3 years ago by
If you take L = Poset({0:[1,2,3], 1:[4, 5], 2:[5], 3:[6], 4:[7], 5:[7], 6:[7]})
then kappa(4)
is 5
, but both 5
and 6
are maximal incomparables. Hence maximal_incomparable_element
does not work.
Hard question... To compare: both meet and joinsemidistributive are used, and semidistributive means that a lattice is both. (Then there are joindistributive and meetdistributive...) OTOH semimodular usually means upper semimodular. And pseudocomplement is almost never said to be meetpseudocomplement, but of course there is a possible dual notion of joinpseudocomplement.
comment:15 Changed 3 years ago by
J.B. Nation answered: "It seems that the 'kappa' notation is fairly widely used, but perhaps not enough to be called standard. It is useful though."
It is useful at least to check if a lattice is semidistributive or to compute canonical joinands. But to publish it on lattices.py
or not to publish  that is the question.
comment:16 Changed 3 years ago by
 Commit changed from 3359c29fdc997a58ee0054918218f8502c8d8877 to 4893b877b57cf93df457cbaeb8f5e553fe9435da
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
4893b87  Add kappa() to Hasse diagram.

comment:17 Changed 3 years ago by
No common view about adding this to uservisible namespace at lattices.py
. Hence I suggest a modified version where this is only added to hasse_diagram.py
.
(This will make is_[meetjoin]_semidistributive()
much faster.
comment:18 followup: ↓ 20 Changed 3 years ago by
You need to change the *.next()
to next(*)
for Python3 compliance.
comment:19 Changed 3 years ago by
 Commit changed from 4893b877b57cf93df457cbaeb8f5e553fe9435da to 46c64ccf32bd4fc7d421239ccf41d3bb63576dad
Branch pushed to git repo; I updated commit sha1. New commits:
46c64cc  next() to py3 style.

comment:20 in reply to: ↑ 18 Changed 3 years ago by
Replying to kdilks:
You need to change the
*.next()
tonext(*)
for Python3 compliance.
True. Done that.
comment:21 followup: ↓ 22 Changed 3 years ago by
 Milestone changed from sage7.4 to sage7.5
OK? If not, OK if name changed to _kappa
?
comment:22 in reply to: ↑ 21 Changed 3 years ago by
comment:23 followup: ↓ 24 Changed 3 years ago by
 Branch changed from u/jmantysalo/kappa to u/tscrim/kappa21419
 Commit changed from 46c64ccf32bd4fc7d421239ccf41d3bb63576dad to 7c192cd06f1a5f88dcee9b6662863956d470bb8e
 Reviewers set to Travis Scrimshaw
I think kappa
is fine. I reworked things slightly and improved the documentation. If my changes look good, then you can set a positive review. (From Sage's definition of joinirreducible, the 1 element lattice does not have any joinirreducible elements, and subsequently this case is not handled by your code, which is okay.)
New commits:
3846724  Merge branch 'u/jmantysalo/kappa' of git://trac.sagemath.org/sage into u/tscrim/kappa21419

7c192cd  Some reviewer changes.

comment:24 in reply to: ↑ 23 Changed 3 years ago by
 Status changed from needs_review to positive_review
Replying to tscrim:
I think
kappa
is fine. I reworked things slightly and improved the documentation. If my changes look good, then you can set a positive review. (From Sage's definition of joinirreducible, the 1 element lattice does not have any joinirreducible elements, and subsequently this case is not handled by your code, which is okay.)
Thanks (once again). This is good.
I must remember that oneelement case when making code for semidistributivity.
comment:25 Changed 3 years ago by
 Branch changed from u/tscrim/kappa21419 to 7c192cd06f1a5f88dcee9b6662863956d470bb8e
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Add kappa function.