implementation of the generalized associahedron as a polyhedral complex #10817

stumpc5 · 2011-02-21T22:25:24Z

The patch contains the implementation of the generalized associahedron, as constructed in [CFZ] Chapoton, Fomin, Zelevinsky - Polytopal realizations of the generalized associahedra, http://arxiv.org/abs/math/0202004.

sage: Associahedron(['A',3])
Generalized associahedron of type ['A', 3] with 14 vertices

The class inherits from Polyhedra, and uses several new methods for root spaces:

RootLatticeRealization.index_bipartition, returns the bipartition of the indices of the Dynkin diagram vertices, if it is bipartite
RootLatticeRealization.almost_positive_roots, returns the sorted list of positive and simple negative roots
RootLatticeRealization.tau_plus_minus, returns two piecewise linear operators on the root space which are used to define the "tropical Coxeter element" in [CFZ]
RootLatticeRealization.almost_positive_root_decomposition, returns the orbit decomposition of the almost positive roots under the dihedral group action of < tau_plus, tau_minus > as defined above

Component: combinatorics

Keywords: associahedra

Author: Christian Stump

Reviewer: Frédéric Chapoton, Nicolas M. Thiéry

Merged: sage-5.0.beta8

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

The text was updated successfully, but these errors were encountered:

stumpc5 · 2011-06-10T17:31:15Z

Dependencies: #10538

stumpc5 · 2011-06-10T17:48:21Z

comment:5

As many files are touched in #11187, this "depends" on it to apply properly.

stumpc5 · 2011-06-10T17:48:21Z

Changed dependencies from #10538 to #11187

fchapoton · 2011-06-10T19:42:58Z

comment:6

Apply trac_10817-generalized_associahedra-cs.patch

fchapoton · 2011-06-12T07:54:05Z

comment:8

Let us try without the dependency, which is not obviously needed.

Apply trac_10817-generalized_associahedra-cs.patch

fchapoton · 2011-06-12T07:54:05Z

Changed dependencies from #11187 to none

fchapoton · 2011-06-12T07:56:41Z

comment:9

well, too bad, it does really depends on #11187

fchapoton · 2011-06-12T07:56:41Z

Dependencies: #11187

stumpc5 · 2011-06-12T13:30:58Z

comment:10

Replying to @fchapoton:

well, too bad, it does really depends on #11187

I removed the dependencies so we can get it done without waiting for the other patch - Thanks for looking at it!

stumpc5 · 2011-06-12T13:30:58Z

Changed dependencies from #11187 to none

fchapoton · 2011-06-13T19:04:09Z

comment:11

Apply trac_10817-generalized_associahedra-cs.patch

fchapoton · 2012-02-23T12:41:27Z

Reviewer: Frédéric Chapoton, Nicolas M. Thiéry

fchapoton · 2012-02-23T12:41:27Z

comment:14

A review has been done, and a reviewer patch follows soon.

nthiery · 2012-02-24T14:40:16Z

comment:15

I just pushed the reviewer patch on the sage-combinat server; please check if you agree with it. I still want to have a last look, but this may not occur before next week (vacations here).

Cheers,
Nicolas

nthiery · 2012-02-24T17:35:09Z

comment:16

Replying to @nthiery:

I just pushed the reviewer patch on the sage-combinat server; please check if you agree with it. I still want to have a last look, but this may not occur before next week (vacations here).

Ok, I finally could do it. The patch is on the queue. If you are happy with it, you may fold the two patches, upload them here, and set a positive review on my behalf.

stumpc5 · 2012-02-24T19:04:06Z

comment:17

Thanks for the review -- you should add yourself as an author actually... .

I set a positive review on Nicolas' behalf.

Best, Christian

nthiery · 2012-02-24T22:54:39Z

comment:18

For the record: all tests pass on 5.0 beta4, with the following patches applied:

trac_11003-folded.patch
trac_10998-categories-posets-nt.patch
trac_11118-finite_enumset_list_cache-fh.patch
trac_11250-action_coerce_doc-fh.patch
trac_11257_avoid_coercion_power_zero-nb.patch
trac_12483-family-workaround_12482-nt.patch
trac_12464-free_module_classcall-fh.patch
trac_12490-trac_role-fh.patch
trac_10670_integral_mobius_matrix_for_posets-fh.patch
trac_11382-subposet_to_vertex_speedup-fh.patch
trac_12484-free_module-monomials_cmp-nt.patch
trac_12489-freemod_eq-nt.patch
trac_10347_is_skew_symmetrizable-cs.patch
trac_12476-lattice_join_matrix_speedup-fh.patch
trac_9469-category-membership_without_arguments-nt.patch
trac_10603-union_enumset_elconstr_fix-fh.patch
trac_12528_free_module-optimize-nt.patch
trac_10817-generalized_associahedra-cs.patch
trac_10817-generalized_associahedra-review-nt.patch

Most of the above patches are either orthogonal or already merged in beta5, so I assume the test pass without them too.

nthiery · 2012-02-24T22:55:39Z

comment:19

Replying to @stumpc5:

Thanks for the review -- you should add yourself as an author actually... .

Bah, just my reviewer's job. You drove this patch through!

jdemeyer · 2012-02-26T22:13:47Z

comment:20

There is a doctest failure on hawk (OpenSolaris 06.2009-32):

**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta6/devel/sage-main/sage/combinat/root_system/associahedron.py", line 43:
    sage: sorted(Asso.Hrepresentation())
Expected:
    [An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0]
Got:
    [An inequality (0, -1) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0]
**********************************************************************

stumpc5 · 2012-02-27T08:39:10Z

comment:21

Replying to @jdemeyer:

There is a doctest failure on hawk (OpenSolaris 06.2009-32):

    sage: sorted(Asso.Hrepresentation())

The buildbot doesn't find the failure, and the list has actually the same content. So the problem must be something with the cmp of inequalities.

I wouldn't know how to fix that in this patch actually.

Best, Christian

jdemeyer · 2012-02-27T11:16:59Z

comment:22

On Cicero (Linux i386):

**********************************************************************
File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-5.0.beta6/devel/sage-main/sage/combinat/root_system/associahedron.py", line 43:
    sage: sorted(Asso.Hrepresentation())
Expected:
    [An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0]
Got:
    [An inequality (0, 1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0]
**********************************************************************

stumpc5 · 2012-02-27T13:58:29Z

comment:23

Replying to @jdemeyer:

I updated the patch with this order in the sorted list of inequalities.

But now I see that the two machines you are using sort this list differently - in particular, we have no chance to get no failure on any of the two machines you used...

Any suggestions?

nthiery · 2012-03-06T12:19:52Z

comment:24

Replying to @stumpc5:

But now I see that the two machines you are using sort this list differently - in particular, we have no chance to get no failure on any of the two machines you used...

Any suggestions?

What about:

    sage: sorted(Asso.Hrepresentation(), key=repr)
    [An inequality (-1, 0) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0]

Then the result should be sorted according to their string
representation, and string comparison should be platform independent.

stumpc5 · 2012-03-07T08:18:16Z

Attachment: trac_10817-generalized_associahedra-cs.patch.gz

stumpc5 · 2012-03-07T08:21:19Z

comment:25

Replying to @nthiery:

Replying to @stumpc5:
Then the result should be sorted according to their string
representation, and string comparison should be platform independent.

Done - how can I know that string representations should be platform independent and some others aren't?

Thanks! Christian

nthiery · 2012-03-07T09:54:53Z

comment:26

Replying to @stumpc5:

Replying to @nthiery:

Replying to @stumpc5:
Then the result should be sorted according to their string
representation, and string comparison should be platform independent.

Done

Thanks! Positive review, assuming the tests pass.

how can I know that string representations should be platform independent and some others aren't?

Because:

I am amost certain that Python compares strings lexicographically (it does for e.g. tuples; see http://docs.python.org/library/stdtypes.html; it's certainly specified somewhere for strings too)
The Inequality class implements _repr_ independently of the platform
On the other hand, this class does not implement __cmp__, so its behavior is unspecified. And likely to be platform dependent.

stumpc5 · 2012-03-07T11:08:21Z

comment:27

Replying to @nthiery:

Thanks! Positive review, assuming the tests pass.

The buildbot somehow doesn't like the test

for root in L.almost_positive_roots():
         print 'tau({:<41}) ='.format(root), tau(root)

I guess, you added it, didn't you? On my 5.0.beta6, it passed though.

Best, Christian

nthiery · 2012-03-07T11:25:39Z

comment:28

Replying to @stumpc5:

Replying to @nthiery:

Thanks! Positive review, assuming the tests pass.

The buildbot somehow doesn't like the test
for root in L.almost_positive_roots():
         print 'tau({:<41}) ='.format(root), tau(root)
I guess, you added it, didn't you? On my 5.0.beta6, it passed though.

Indeed.

Python has been upgraded to 2.7 in Sage 5.0. I guess this syntax for format was not yet supported in Python 2.6. Let's just wait for the buildbot to run on 5.0.

jdemeyer · 2012-03-13T08:22:07Z

Merged: sage-5.0.beta8

stumpc5 added c: combinatorics labels Feb 21, 2011

stumpc5 assigned sagetrac-sage-combinat Feb 21, 2011

stumpc5 added the s: needs review label Feb 24, 2011

This comment has been minimized.

Sign in to view

stumpc5 unassigned sagetrac-sage-combinat Jun 10, 2011

stumpc5 added this to the sage-4.7.2 milestone Jun 11, 2011

This comment has been minimized.

Sign in to view

stumpc5 modified the milestones: sage-4.7.2, sage-4.7.1 Jun 14, 2011

stumpc5 added s: positive review and removed s: needs review labels Feb 24, 2012

jdemeyer added s: needs work and removed s: positive review labels Feb 26, 2012

stumpc5 added s: needs review and removed s: needs work labels Mar 7, 2012

nthiery added s: positive review and removed s: needs review labels Mar 7, 2012

jdemeyer removed the s: positive review label Mar 13, 2012

jdemeyer closed this as completed Mar 13, 2012

nthiery mentioned this issue Apr 2, 2012

Categories for root systems and many misc improvements #6588

Closed

sagetrac-mhampton mannequin mentioned this issue Mar 13, 2012

Base Polyhedron on PPL (by default) #11634

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

implementation of the generalized associahedron as a polyhedral complex #10817

implementation of the generalized associahedron as a polyhedral complex #10817

stumpc5 commented Feb 21, 2011

This comment has been minimized.

This comment has been minimized.

stumpc5 commented Jun 10, 2011

stumpc5 commented Jun 10, 2011

stumpc5 commented Jun 10, 2011

fchapoton commented Jun 10, 2011

fchapoton commented Jun 12, 2011

fchapoton commented Jun 12, 2011

fchapoton commented Jun 12, 2011

fchapoton commented Jun 12, 2011

stumpc5 commented Jun 12, 2011

stumpc5 commented Jun 12, 2011

fchapoton commented Jun 13, 2011

This comment has been minimized.

fchapoton commented Feb 23, 2012

fchapoton commented Feb 23, 2012

nthiery commented Feb 24, 2012

nthiery commented Feb 24, 2012

stumpc5 commented Feb 24, 2012

nthiery commented Feb 24, 2012

nthiery commented Feb 24, 2012

jdemeyer commented Feb 26, 2012

stumpc5 commented Feb 27, 2012

jdemeyer commented Feb 27, 2012

stumpc5 commented Feb 27, 2012

nthiery commented Mar 6, 2012

stumpc5 commented Mar 7, 2012

stumpc5 commented Mar 7, 2012

nthiery commented Mar 7, 2012

stumpc5 commented Mar 7, 2012

nthiery commented Mar 7, 2012

jdemeyer commented Mar 13, 2012

implementation of the generalized associahedron as a polyhedral complex #10817

implementation of the generalized associahedron as a polyhedral complex #10817

Comments

stumpc5 commented Feb 21, 2011

This comment has been minimized.

This comment has been minimized.

stumpc5 commented Jun 10, 2011

stumpc5 commented Jun 10, 2011

stumpc5 commented Jun 10, 2011

fchapoton commented Jun 10, 2011

fchapoton commented Jun 12, 2011

fchapoton commented Jun 12, 2011

fchapoton commented Jun 12, 2011

fchapoton commented Jun 12, 2011

stumpc5 commented Jun 12, 2011

stumpc5 commented Jun 12, 2011

fchapoton commented Jun 13, 2011

This comment has been minimized.

fchapoton commented Feb 23, 2012

fchapoton commented Feb 23, 2012

nthiery commented Feb 24, 2012

nthiery commented Feb 24, 2012

stumpc5 commented Feb 24, 2012

nthiery commented Feb 24, 2012

nthiery commented Feb 24, 2012

jdemeyer commented Feb 26, 2012

stumpc5 commented Feb 27, 2012

jdemeyer commented Feb 27, 2012

stumpc5 commented Feb 27, 2012

nthiery commented Mar 6, 2012

stumpc5 commented Mar 7, 2012

stumpc5 commented Mar 7, 2012

nthiery commented Mar 7, 2012

stumpc5 commented Mar 7, 2012

nthiery commented Mar 7, 2012

jdemeyer commented Mar 13, 2012