Simplicity and simpliciality for CombinatorialPolyhedron

[kliem]

We add a function to CombinatorialPolyhedron that returns the largest k such that the polyhedron is k-simple/k-simplicial.

Depends on #28606

CC: @jplab

Component: geometry

Keywords: Polyhedron, CombinatorialPolyhedron, simple, simplicial, flag

Author: Jonathan Kliem

Branch/Commit: a19efd6

Reviewer: Jean-Philippe Labbé, Laith Rastanawi

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

[kliem]

Changed keywords from Polyhedron, CombinatorialPolyhedron, simple, simplicial to Polyhedron, CombinatorialPolyhedron, simple, simplicial, flag

[kliem]

comment:4

Posting this example, so I won't forget:

An example for simpliness and simpliciality could look like this:

sage: for i in Combinations(6,3):
....:     x.append(list(Integer(j in i) for j in range(6)))
....: P = Polyhedron(vertices=x)
....: C = CombinatorialPolyhedron(P)
....: C.simpliness()
4
....: C.simpliciality()
2
....: C.dimension()
5

One can replace 6 by n and this will alter 4 to n-2 and 5 to n-1.

(This example is taken from lecture notes from Günter M. Ziegler.)

[embray]

comment:5

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[kliem]

Changed dependencies from #26887 to #28606

[kliem]

Author: Jonathan Kliem

[kliem]

Commit: 9f6f172

[kliem]

Branch: public/27086

[kliem]

Last 10 new commits:

37592f9	replace attributes by methods; remove empty folder from source
e865f9d	removed attribute Vinv, as its not being used
84ef31b	added docstrings to the new methods
588afa4	removed method for Vinv
531222d	unbounded(self) -> is_bounded(self); _unbounded -> _bounded
fb93bed	partly added simpliness
c8c49c5	fixed small mistake in header file
2f0b931	Merge branch 'public/28606' of git://trac.sagemath.org/sage into public/27086
1fc57e3	method simpliciality
9f6f172	method simpliness

[sagetrac-git]

Changed commit from 9f6f172 to 6ec5053

[sagetrac-git]

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

6ec5053

cached the results; opted out when discovering not 2-simple/simplicial

[sagetrac-git]

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

6fd5b2a

using cached_method as described in #12951

[sagetrac-git]

Changed commit from 6ec5053 to 6fd5b2a

[jplab]

comment:12

I believe that 'simplicity' is more appropriate than simpliness.

[jplab]

Reviewer: Jean-Philippe Labbé

[kliem]

Last 10 new commits:

2e3e464	removed empty folder being created in source
7701062	removed attribute Vinv, as its not being used
1b17f6e	added docstrings to the new methods
c51cdd9	removed method for Vinv
dd21f9c	applied changes of 28605 to new code from 28625
4f49eac	undid change to module list
0f3b121	replace attributes by methods; remove attribute Vinv
6550083	unbounded(self) -> is_bounded(self); _unbounded -> _bounded
8aaaef5	unbounded(self) -> is_bounded(self); _unbounded -> _bounded
e36b271	added simplicity and simpliciality to CombinatorialPolyhedron

[kliem]

Changed commit from 50eeaf6 to e36b271

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b0eac08	replace attributes by methods; remove attribute Vinv
e44a557	unbounded(self) -> is_bounded(self); _unbounded -> _bounded
8e8ac4e	added simplicity and simpliciality to CombinatorialPolyhedron

[sagetrac-git]

Changed commit from e36b271 to 8e8ac4e

[kliem]

comment:17

Rebased again.

---

New commits:

f131286

added simplicity and simpliciality to CombinatorialPolyhedron

[kliem]

Changed commit from 8e8ac4e to f131286

[kliem]

Changed branch from public/27086-reb to public/27086-reb2

[sagetrac-git]

Changed commit from f131286 to 2113b47

[sagetrac-git]

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

2113b47

took into account the changes from #28614

[embray]

comment:19

Ticket retargeted after milestone closed

[LaisRast]

comment:20

In simplicity method:

• I suggest to change the definition of k-simple. Using the definition you give, one needs to know P/F.

-        A polytope `P` is `k`-simple, if for every face `F`
-        of codimension `k` the polytope `P/F` is simple.
+        A polytope `P` is `k`-simple, if every `(d-1-k)`-face
+        is contained in `k+1` facets of `P` for `1 <= k <= d-1`.

• coface instead of face:

            if face_iter.n_atom_rep() == d + 1:
-                # The current face is a simplex.
+                # The current coface is a simplex.
                face_iter.ignore_supfaces()

• Since you are dealing with cofaces, maybe you need to do the following change

-        cdef FaceIterator face_iter = self._face_iter(True, -2)
+        cdef FaceIterator coface_iter = self._face_iter(True, -2)

[kliem]

Changed commit from 2113b47 to a19efd6

[kliem]

Changed branch from public/27086-reb2 to public/27086-reb3

[kliem]

New commits:

dfa32fc	added simplicity and simpliciality to CombinatorialPolyhedron
e47a144	took into account the changes from #28614
a19efd6	small changes improving readibilty of code

[LaisRast]

comment:22

I believe it is good to go.

[LaisRast]

Changed reviewer from Jean-Philippe Labbé to Jean-Philippe Labbé, Laith Rastanawi

[vbraun]

Changed branch from public/27086-reb3 to a19efd6