Give posets polynomials (order, characteristic, zeta, etc.) #13240

sagetrac-csar · 2012-07-12T17:02:42Z

Adding some of the polynomials from Stembridge's Posets package for Maple (see http://www.math.lsa.umich.edu/~jrs/software/posetshelp.html), namely:

characteristic polynomial (done)
zeta polynomial (done)
flag f-polynomial (done)
flag h-polynomial (done)
f-polynomial (done)
h-polynomial (done)
order polynomial (done)
chain polynomial (done)
W-polynomial
antichain polynomial

apply:

CC: @kevindilks

Component: combinatorics

Keywords: sd40, days45

Author: Alex Csar, Kevin Dilks, Frédéric Chapoton

Reviewer: Darij Grinberg, Nathann Cohen

Merged: sage-5.13.beta2

Issue created by migration from https://trac.sagemath.org/ticket/13240

sagetrac-csar · 2013-02-14T16:22:12Z

Changed keywords from sd40 to sd40, days45

fchapoton · 2013-05-05T19:39:49Z

comment:3

A first patch, with three of the simplest polynomials

fchapoton · 2013-05-14T19:32:01Z

comment:4

I have added the flag f-vector

fchapoton · 2013-05-15T18:38:54Z

comment:5

I have added the flag h-polynomial

fchapoton · 2013-05-24T16:53:04Z

comment:6

I have added the characteristic polynomial

sagetrac-csar · 2013-05-24T17:20:21Z

comment:8

I think we have code from Sage Days 45 for the order polynomial (which is one line once you have zeta), the antichain polynomial and the chain polynomial.

fchapoton · 2013-05-24T19:02:19Z

comment:9

great ! could you post it here as a patch on top of mine ?

sagetrac-csar · 2013-05-24T20:03:18Z

comment:10

Will do. I'm compiling sage at the moment, but I should be able to do it sometime this evening (GMT -6).

Note several hours later: compiling took way longer than expected. Will add to the patch tomorrow.

sagetrac-csar · 2013-05-26T03:00:29Z

comment:11

The patch didn't apply. I'm pretty sure it's a problem on my end and my installation is still messed up. I'll add things when I get it fixed.

sagetrac-csar · 2013-05-27T21:43:08Z

Attachment: trac_12340_poset_polynomials-csar.patch.gz

add chain polynomial and order polynomial

sagetrac-csar · 2013-05-27T21:50:19Z

comment:12

Okay, I've added the chain polynomial and the order polynomial. We had something written for the antichain polynomial, but I didn't include it as I wanted to check with Kevin if he knew a better way of doing it like he worked out for the chain polynomial.

The chain polynomial is written so you can ask for it in terms of something other than q. So, for example, P.chain_polynomial(1) would give you the chain polynomial evaluated at one. Obviously, things should be consistent as to whether you get to choose the variable, but it's a minor change to go either direction.

I made a second patch on top of yours because I wasn't sure if I should be making a separate one or just adding to the patch, and combining them shouldn't be hard.

fchapoton · 2013-05-28T08:25:22Z

comment:13

Yes, it is better to upload a patch that applies on top of mine.

I will have a closer look at your code soon.

fchapoton · 2013-05-28T18:40:47Z

comment:14

ok, here is a short review patch of your code.

I have removed trailing whitespaces that you had introduced, and made small changes to the code. I have also made sure that each method starts with a brief (one-line) description of what it does. Details are then given on other lines.

I would prefer not to propose the use of another variable in the code, but rather give no option. The user will get a polynomial, that he can then evaluate on whatever he wants. I think this keeps the code cleaner and shorter.

Combining patches is indeed easy, and can be done just once when everything is ready.

fchapoton · 2013-06-22T20:43:14Z

comment:16

maybe we could stop here adding other polynomials, and try to let this set of polynomials enter sage ?

fchapoton · 2013-06-30T07:55:45Z

comment:17

apply trac_1324O_first_step-fc.patch, trac_12340_poset_polynomials-csar.patch, trac_13240-review1-fc.patch

nathanncohen · 2013-07-04T09:34:37Z

comment:19

Hello !

Would it be possible to add definitions of what these polynomials are, possibly as links toward wikipedia pages ?

I also think that you should cache minimal and maximal elements in the code of remove_top_and_bottom, otherwise you compute the maximal and minimal elements for each vertex :

sage: def a():                                 
....:     print "Hey"
....:     return [1]
....: 
sage: [x for x in range(5) if x in a()]
Hey
Hey
Hey
Hey
Hey
[1]

Hence if you want to write this function, this really should not be computed so many times.

Besides : you only implement this method for bounded posets, which means that there is one max and one min elements. Hence this complicated line only checks that each vertex is different from two given vertices.

I personally do not think that this remove_top_and_bottom method is useful, especially when it build a copy of the whole poset, which can be very costly. You would probably save yourself a lot of time if you worked on self in each of your methods, and just ignored the top and bottom elements. No copies of the poset, no call to remove_to_and_bottom either.

Oh, and Florent thinks that it would be nice to add "seealso" sections toward "is_bounded", or toward polynomials that are related with each other.

See youuuuuuuuuuuuuuuuUU !!

Nathann

sagetrac-csar · 2013-07-04T13:26:48Z

comment:20

I'm not actually sure there are definitions on Wikipedia for any/some/most of these (I took a quick look and didn't find any). But one could include references to EC1.

fchapoton · 2013-07-05T19:11:44Z

comment:21

Here is a new patch

I have tried to adress some of the points raised by Nathan:

I have got rid of remove_top_and_bottom, but introduced chains_with_bounds

There remains to explain the definition of every polynomial, and give the references to EC1

fchapoton · 2013-09-13T18:17:08Z

comment:23

Attachment: trac_1324O_first_step-fc.patch.gz

apply trac_1324O_first_step-fc.patch,trac_12340_poset_polynomials-csar.patch,trac_13240-review1-fc.patch

fchapoton · 2013-09-13T18:37:14Z

comment:24

I have added a few more reference to Enum. Comb. 1

fchapoton · 2013-09-22T14:00:48Z

comment:25

Maybe this ticket can be considered good enough ?

One patchbot has turned green, so there is an opportunity right now.

nathanncohen · 2013-09-22T16:31:46Z

comment:27

Helooooooo !

There still isn't any definition of what f_polynomial and h_polynomial return. Also, I personally do not think that a function named "chains with bounds" should exist (and so I will let somebody else give a positive review to this ticket), but in any case if you want to implement such a thing I'd think better to do it the following way :

create a copy of the poset without the top/bottom element
list its chains
return each of them after adding the top and bottom element at each end of the chain.

Nathann

fchapoton · 2013-09-22T16:58:23Z

comment:28

Hello Nathann,

well, chains_with_bounds has been written to try to cope with your previous comments, that suggested to avoid copying the poset. And now you suggest to copy the poset..

Would it be better to make chains_with_bounds a hidden method ?

nathanncohen · 2013-09-22T17:13:58Z

comment:29

well, chains_with_bounds has been written to try to cope with your previous comments, that suggested to avoid copying the poset. And now you suggest to copy the poset..

Well, yes. The best way out is to not copy the poset, to not call the .chains() method, and to rewrite what chains() does directly on this poset, ignoring the top/bottom elements on the fly. There's no need to copy.

Though if you want to call this chains() method you will enumerate 4 times too many things chains, and you need each time to check if the two vertices belong to the list (by the way, you already know WHERE in the list they will appear if they do, so you can save time there too).

Would it be better to make chains_with_bounds a hidden method

What about making it an option of "chains" ?

Nathann

fchapoton · 2013-09-23T19:19:31Z

comment:30

Attachment: trac_13240-review1-fc.patch.gz

Hello Nathann,

thanks for spending time on this ticket.

I have removed chains_with_bounds, instead adding a parameter exclude to the method chains.

I have also added more documentation.

nathanncohen · 2013-09-25T09:19:20Z

comment:31

Wow ! It sure looks cleaner this way :-)

I don't see anything wrong in this patch right now... Though I'm a bit embarassed because I don't understand the maths at all, and it would be nice if somebody could just check that the polynomials are indeed what they should be ^^;

Nathann

darijgr · 2013-10-20T20:09:22Z

comment:32

The csar patch applied with fuzz for me (5.13beta0):

applying trac_12340_poset_polynomials-csar.patch
patching file sage/combinat/posets/posets.py
Hunk #1 succeeded at 28 with fuzz 1 (offset 0 lines).
Hunk #2 succeeded at 84 with fuzz 2 (offset 5 lines).

The file I'm uploading in a few seconds is just a qfold so that I get a better view of the changes myself.

darijgr · 2013-10-20T20:09:51Z

qfold

darijgr · 2013-10-21T02:48:35Z

Attachment: trac_13240-qfold.patch.gz

UPDATED! everything reviewed, except for the two flag_* functions which I don't really understand nor can find a reference for.

darijgr · 2013-10-21T02:49:57Z

comment:33

Attachment: trac_13240-almost-review-dg.patch.gz

Thanks, Nathan, for alerting me to this patch!

The file I just attached gives a review of everything but the two flag polynomials (f and h) which I couldn't find in literature. Please give a reference or a full definition (how exactly are those monomials built from the ranks etc.).

#13223 notwithstanding, I've replaced the hyperpolynomial-time is_graded method by a polynomial-time (and memory) one. Speed comparisons:

before:

sage: B2 = Posets.BooleanLattice(2)
sage: %timeit B2.is_graded()
10000 loops, best of 3: 84.9 us per loop
sage: B3 = Posets.BooleanLattice(3)
sage: %timeit B3.is_graded()
10000 loops, best of 3: 195 us per loop
sage: B4 = Posets.BooleanLattice(4)
sage: %timeit B4.is_graded()
1000 loops, best of 3: 663 us per loop
sage: B5 = Posets.BooleanLattice(5)
sage: %timeit B5.is_graded()
100 loops, best of 3: 2.86 ms per loop
sage: B6 = Posets.BooleanLattice(6)
sage: %timeit B6.is_graded()
100 loops, best of 3: 16 ms per loop
sage: B7 = Posets.BooleanLattice(7)
sage: %timeit B7.is_graded()
10 loops, best of 3: 109 ms per loop
sage: P = Poset({1: [2, 3], 3: [4, 5], 2: [6]})
sage: %timeit P.is_graded()
10000 loops, best of 3: 103 us per loop
sage: C = Poset([list(B7) + [1337], B7.cover_relations() + [[127, 1337]]])
sage: %timeit C.is_graded()
10 loops, best of 3: 146 ms per loop

after:

sage: B2 = Posets.BooleanLattice(2)
sage: %timeit B2.is_graded()
10000 loops, best of 3: 82.3 us per loop
sage: B3 = Posets.BooleanLattice(3)
sage: %timeit B3.is_graded()
10000 loops, best of 3: 149 us per loop
sage: B4 = Posets.BooleanLattice(4)
sage: %timeit B4.is_graded()
1000 loops, best of 3: 290 us per loop
sage: B5 = Posets.BooleanLattice(5)
sage: %timeit B5.is_graded()
1000 loops, best of 3: 525 us per loop
sage: B6 = Posets.BooleanLattice(6)
sage: %timeit B6.is_graded()
1000 loops, best of 3: 1.02 ms per loop
sage: B7 = Posets.BooleanLattice(7)
sage: %timeit B7.is_graded()
100 loops, best of 3: 2.07 ms per loop
sage: P = Poset({1: [2, 3], 3: [4, 5], 2: [6]})
sage: %timeit P.is_graded()
10000 loops, best of 3: 108 us per loop
sage: C = Poset([list(B7) + [1337], B7.cover_relations() + [[127, 1337]]])
sage: %timeit C.is_graded()
100 loops, best of 3: 2.14 ms per loop

Also I have optimized the polynomial-computing methods (apart from the ones I don't understand) by letting them work with the _hasse_diagram of the poset rather than the poset itself, because all methods that are used (minimal elements, top, Moebius etc.) currently work by calling the corresponding methods on the Hasse diagram and then relabelling vertices back. This also fixes the issue of chain_polynomial throwing errors if the poset wasn't labelled 0,1,...,n (one of the doctests I made checks for this now).

Probably someone will have to review my review...

for the patchbots:

apply trac_13240-qfold.patch trac_13240-almost-review-dg.patch

nathanncohen · 2013-10-21T13:23:39Z

comment:34

Yooooooooooooooo !!

Well, all I can understand makes sense ! It was nice to merge these calls to is_bounded and getting the top/bottom elements in particular. It could even become an optional argument eventually : p.is_bounded(if_it_is_bounded_return_top_and_bottom_not_true=True) :-)

Thaaaaaaaanks Darij !

Nathann

fchapoton · 2013-10-21T19:47:08Z

comment:35

Thanks Darij, for your review patch.

Your review looks good to me.

concerning flag f-vector and flag h-vector, there is something here : http://en.wikipedia.org/wiki/H-vector#Flag_h-vector_and_cd-index

It can also probably go through the hasse diagram.

darijgr · 2013-10-22T03:09:59Z

Attachment: trac_13240-review2-dg.patch.gz

completed review patch. ignore the almost-review one.

darijgr · 2013-10-22T03:13:05Z

comment:36

Hi Frederic,

I've completed my review, editing again all four f/h-polynomials (flag and usual). Please check that:

the definitions I've added to the docstring are correct (I have deduced them from the implementation, except for the size-1 poset case which I just found had to give 1 for reasons of consistency);
all four methods return what they should in the case of a poset with 1 vertex (this is doctested, but I don't know if it's what you want);
you really want the flag h-polynomial to be returned as a polynomial over QQ, even if it has integer coefficients.

If these are fine, feel free to set this to positive review!

for the patchbot:

apply trac_13240-qfold.patch trac_13240-review2-dg.patch

darijgr · 2013-10-22T03:14:32Z

Reviewer: Darij Grinberg, Nathann Cohen

fchapoton · 2013-10-22T07:49:00Z

comment:39

Thanks Darij,

I will have a serious look later today.

for the patchbots (beware of invisible characters when copy pasting!)

apply trac_13240-qfold.patch trac_13240-review2-dg.patch

fchapoton · 2013-10-22T18:29:25Z

comment:40

ok, I am happy enough with the current patch. Positive review !

:)

fchapoton · 2013-10-22T18:29:25Z

Changed author from Alex Csar, Kevin Dilks to Alex Csar, Kevin Dilks, Frédéric Chapoton

jdemeyer · 2013-10-31T19:16:05Z

Merged: sage-5.13.beta2

sagetrac-csar mannequin added this to the sage-5.11 milestone Jul 12, 2012

sagetrac-csar mannequin added c: combinatorics labels Jul 12, 2012

sagetrac-csar mannequin assigned sagetrac-sage-combinat Jul 12, 2012

sagetrac-csar mannequin changed the title ~~Give posets polynomails (order, characteristic, zeta, etc.)~~ Give posets polynomials (order, characteristic, zeta, etc.) Jul 12, 2012

This comment has been minimized.

Sign in to view

fchapoton added the s: needs review label Jun 30, 2013

nathanncohen mannequin added s: needs work and removed s: needs review labels Jul 4, 2013

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

fchapoton added s: needs review and removed s: needs work labels Sep 22, 2013

This comment has been minimized.

Sign in to view

fchapoton added s: positive review and removed s: needs review labels Oct 22, 2013

jdemeyer removed the s: positive review label Oct 31, 2013

jdemeyer closed this as completed Oct 31, 2013

Give posets polynomials (order, characteristic, zeta, etc.) #13240

Give posets polynomials (order, characteristic, zeta, etc.) #13240

Comments

sagetrac-csar mannequin commented Jul 12, 2012

sagetrac-csar mannequin commented Feb 14, 2013

fchapoton commented May 5, 2013

fchapoton commented May 14, 2013

fchapoton commented May 15, 2013

fchapoton commented May 24, 2013

This comment has been minimized.

sagetrac-csar mannequin commented May 24, 2013

fchapoton commented May 24, 2013

sagetrac-csar mannequin commented May 24, 2013

sagetrac-csar mannequin commented May 26, 2013

sagetrac-csar mannequin commented May 27, 2013

sagetrac-csar mannequin commented May 27, 2013

fchapoton commented May 28, 2013

This comment has been minimized.

fchapoton commented May 28, 2013

This comment has been minimized.

fchapoton commented Jun 22, 2013

fchapoton commented Jun 30, 2013

nathanncohen mannequin commented Jul 4, 2013

sagetrac-csar mannequin commented Jul 4, 2013

fchapoton commented Jul 5, 2013

fchapoton commented Sep 13, 2013

fchapoton commented Sep 13, 2013

fchapoton commented Sep 22, 2013

nathanncohen mannequin commented Sep 22, 2013

fchapoton commented Sep 22, 2013

nathanncohen mannequin commented Sep 22, 2013

fchapoton commented Sep 23, 2013

nathanncohen mannequin commented Sep 25, 2013

darijgr commented Oct 20, 2013

darijgr commented Oct 20, 2013

darijgr commented Oct 21, 2013

darijgr commented Oct 21, 2013

nathanncohen mannequin commented Oct 21, 2013

fchapoton commented Oct 21, 2013

darijgr commented Oct 22, 2013

darijgr commented Oct 22, 2013

This comment has been minimized.

darijgr commented Oct 22, 2013

fchapoton commented Oct 22, 2013

fchapoton commented Oct 22, 2013

fchapoton commented Oct 22, 2013

jdemeyer commented Oct 31, 2013