Add methods for shelling orders

[2734658e-4e8e-403b-8240-541f6fa6862a]

We add methods to check if a given order of facets is a shelling order and for calculating restricted sets (when shellable). This also adds code to construct the f-triangle and h-triangles (to use for basic tests for shellability). We add some code in a doctest for a specialized method for computing the h vector, which should get merged into a class for ShellableComplexes (when such a class gets created).

CC: @jhpalmieri

Component: combinatorics

Keywords: simplicial complex, shellable, days74

Author: Federico Castillo, Travis Scrimshaw

Branch/Commit: cc56de8

Reviewer: Travis Scrimshaw, Jeremy Martin

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

[tscrim]

Author: Federico Castillo

[tscrim]

Changed keywords from none to simplicial complex, shellable

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+We add methods to check if a given order of facets is a shelling order and for calculating  restricted sets (when shellable). We add some code in a doctest for a specialized method for computing the *h* vector, which should get merged into a class for `ShellableComplexes` (when such a class gets created).

[tscrim]

comment:2

Federico, I rewrote your algorithm to reflect the mathematics more closely. I think the next step after this would be to implement a new class ShellableSimplicialComplex to take advantage of specialized implementations (such as your h_vector code).

John, do you think you could do a (second) review of this?

---

New commits:

120d086

Implement code to check for shellable complexes.

[tscrim]

Branch: public/combinat/shelling_order-18023

[tscrim]

Changed author from Federico Castillo to Federico Castillo, Travis Scrimshaw

[tscrim]

Commit: 120d086

[jhpalmieri]

comment:3

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 120d086 to 42e0396

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c23dd64	Merge branch 'public/combinat/shelling_order-18023' of trac.sagemath.org:sage into public/combinat/shelling_order-18023
42e0396	Rewriting algorithm for is_shellable.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b4f8282

Added f_triangle and h_triangle methods.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 42e0396 to b4f8282

[tscrim]

comment:6

Good points. I've made some minor tweaks so that this works for non-pure complexes as well. I've added the f/h triangles and do shortcuts for shellability testing. I've also rewritten the algorithm for is_shellable to do backtracing in following the link you posted. I'll also run some more tests with Federico (next week when I get back to Davis).

[tscrim]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-We add methods to check if a given order of facets is a shelling order and for calculating  restricted sets (when shellable). We add some code in a doctest for a specialized method for computing the *h* vector, which should get merged into a class for `ShellableComplexes` (when such a class gets created).
+We add methods to check if a given order of facets is a shelling order and for calculating  restricted sets (when shellable). This also adds code to construct the f-triangle and h-triangles (to use for basic tests for shellability). We add some code in a doctest for a specialized method for computing the *h* vector, which should get merged into a class for `ShellableComplexes` (when such a class gets created).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e9cc716

Merge branch 'public/combinat/shelling_order-18023' of trac.sagemath.org:sage into public/combinat/shelling_order-18023

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b4f8282 to e9cc716

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

08cd54c	Merge branch 'public/combinat/shelling_order-18023' of trac.sagemath.org:sage into public/combinat/shelling_order-18023
8b7e4bb	Reviewer changes.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e9cc716 to 8b7e4bb

[16bee037-a40f-49da-80f6-39ef26539405]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Jeremy Martin

[16bee037-a40f-49da-80f6-39ef26539405]

comment:9

The mathematics looks correct to me and the code works.

[tscrim]

Changed keywords from simplicial complex, shellable to simplicial complex, shellable, days74

[16bee037-a40f-49da-80f6-39ef26539405]

comment:11

Going to add to the documentation.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

cc56de8

Last little details of documentation.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8b7e4bb to cc56de8

[vbraun]

Changed branch from public/combinat/shelling_order-18023 to cc56de8