#18023: Add methods for shelling orders
-------------------------------------+-------------------------------------
Reporter: fcastillo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: simplicial | Merged in:
complex, shellable | Reviewers: Travis Scrimshaw
Authors: Federico | Work issues:
Castillo, Travis Scrimshaw | Commit:
Report Upstream: N/A | 120d0864906938f51f649e052757871d6dcd271d
Branch: | Stopgaps:
public/combinat/shelling_order-18023|
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by jhpalmieri):
First, I'm not an expert on shellability; my background is algebraic
topology, not combinatorics. The basic code looks fine, but I'm worried
that this method for testing for shellability is going to be very slow for
even modestly sized simplicial complexes. If I naively do
{{{
sage: T = simplicial_complexes.Torus()
sage: T
Simplicial complex with vertex set (0, 1, 2, 3, 4, 5, 6) and 14 facets
sage: T.is_shellable()
}}}
I'm going to be in for a long wait. Part of the problem is that `T` isn't
shellable, so it tries all 87 billion permutations of the facets to see if
any ordering works.
At least add a warning in the documentation that it is likely to be slow,
maybe even mention that it is a brute force method. A "to do" pointing to
some possible improvements would be a good idea, too. An internet search
led me to the page http://mathoverflow.net/questions/121371/testing-
simplicial-complexes-for-shellability. Maybe implement some ideas from
there? Is it true that if any component of the h-vector is negative, then
the complex is not shellable? That would return `False` immediately for
the triangulation of the torus in my example. If there are any other quick
checks that rule out classes of non-shellable simplicial complexes, you
should add them. (You can check whether the homology is concentrated in
the top degree, but that won't be nearly as fast as f-vector or h-vector
criteria.)
--
Ticket URL: <http://trac.sagemath.org/ticket/18023#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
