Opened 5 years ago

Closed 4 years ago

#13240 closed enhancement (fixed)

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

Reported by: csar Owned by: sage-combinat
Priority: major Milestone: sage-5.13
Component: combinatorics Keywords: sd40, days45
Cc: kdilks Merged in: sage-5.13.beta2
Authors: Alex Csar, Kevin Dilks, Frédéric Chapoton Reviewers: Darij Grinberg, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by darij)

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:

Attachments (6)

trac_12340_poset_polynomials-csar.patch (3.7 KB) - added by csar 4 years ago.
add chain polynomial and order polynomial
trac_1324O_first_step-fc.patch (11.0 KB) - added by chapoton 4 years ago.
trac_13240-review1-fc.patch (16.2 KB) - added by chapoton 4 years ago.
trac_13240-qfold.patch (18.8 KB) - added by darij 4 years ago.
qfold
trac_13240-almost-review-dg.patch (27.6 KB) - added by darij 4 years ago.
UPDATED! everything reviewed, except for the two flag_* functions which I don't really understand nor can find a reference for.
trac_13240-review2-dg.patch (30.8 KB) - added by darij 4 years ago.
completed review patch. ignore the almost-review one.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 5 years ago by csar

  • Summary changed from Give posets polynomails (order, characteristic, zeta, etc.) to Give posets polynomials (order, characteristic, zeta, etc.)

comment:2 Changed 5 years ago by csar

  • Keywords days45 added

comment:3 Changed 4 years ago by chapoton

A first patch, with three of the simplest polynomials

comment:4 Changed 4 years ago by chapoton

I have added the flag f-vector

comment:5 Changed 4 years ago by chapoton

I have added the flag h-polynomial

comment:6 Changed 4 years ago by chapoton

I have added the characteristic polynomial

comment:7 Changed 4 years ago by chapoton

  • Description modified (diff)

comment:8 Changed 4 years ago by csar

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.

comment:9 Changed 4 years ago by chapoton

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

comment:10 Changed 4 years ago by csar

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.

Last edited 4 years ago by csar (previous) (diff)

comment:11 Changed 4 years ago by csar

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.

Changed 4 years ago by csar

add chain polynomial and order polynomial

comment:12 Changed 4 years ago by csar

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.

comment:13 Changed 4 years ago by chapoton

  • Description modified (diff)

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

I will have a closer look at your code soon.

comment:14 Changed 4 years ago by chapoton

  • Description modified (diff)

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.

comment:15 Changed 4 years ago by kdilks

  • Cc kdilks added

comment:16 Changed 4 years ago by chapoton

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

comment:17 Changed 4 years ago by chapoton

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

comment:18 Changed 4 years ago by chapoton

  • Status changed from new to needs_review

comment:19 follow-up: Changed 4 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:20 in reply to: ↑ 19 Changed 4 years ago by csar

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.

comment:21 Changed 4 years ago by chapoton

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

comment:22 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 4 years ago by chapoton

comment:23 Changed 4 years ago by chapoton

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

comment:24 Changed 4 years ago by chapoton

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

comment:25 Changed 4 years ago by chapoton

Maybe this ticket can be considered good enough ?

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

comment:26 Changed 4 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:27 Changed 4 years ago by ncohen

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

comment:28 follow-up: Changed 4 years ago by chapoton

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 ?

comment:29 in reply to: ↑ 28 Changed 4 years ago by ncohen

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

Changed 4 years ago by chapoton

comment:30 Changed 4 years ago by chapoton

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.

comment:31 Changed 4 years ago by ncohen

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

comment:32 Changed 4 years ago by darij

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.

Changed 4 years ago by darij

qfold

Changed 4 years ago by darij

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

comment:33 Changed 4 years ago by darij

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​

Last edited 4 years ago by darij (previous) (diff)

comment:34 Changed 4 years ago by ncohen

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

comment:35 Changed 4 years ago by chapoton

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.

Changed 4 years ago by darij

completed review patch. ignore the almost-review one.

comment:36 Changed 4 years ago by darij

Hi Frederic,

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

1) 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);

2) 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);

3) 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

Last edited 4 years ago by darij (previous) (diff)

comment:37 Changed 4 years ago by darij

  • Description modified (diff)

comment:38 Changed 4 years ago by darij

  • Reviewers set to Darij Grinberg, Nathann Cohen

comment:39 Changed 4 years ago by chapoton

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

comment:40 Changed 4 years ago by chapoton

  • Authors changed from Alex Csar, Kevin Dilks to Alex Csar, Kevin Dilks, Frédéric Chapoton
  • Status changed from needs_review to positive_review

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

:)

comment:41 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.13.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.