Make CombinatorialPolyhedron an element class, define morphisms of combinatorial polyhedral sets

[mkoeppe]

... of a parent class CombinatorialPolyhedra in a new category of CombinatorialPolyhedralSets. A parent is defined by (possibly infinite) sets of allowed vertices and facets; every element's set of vertices and facets is a subset of these.

Morphisms in the category:

• permutations of the Vrep
• permutations of the Hrep
• relabelings of the Vrep
• relabelings of the Hrep
• degenerations.

This setup of element/parent/category is parallel to geometric polyhedra: Polyhedron/Polyhedra/PolyhedralSets.

Assigning coordinates in QQ^3 to labeled vertices then defines a morphism from CombinatorialPolyhedra(vertices, facets) to Polyhedra(QQ, 3).

CC: @kliem @jplab @tscrim @jhpalmieri @yuan-zhou

Component: geometry

Author: Matthias Koeppe

Branch/Commit: u/mkoeppe/make_combinatorialpolyhedron_an_element_class @ 0a15b46

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

[mkoeppe]

Branch: u/mkoeppe/make_combinatorialpolyhedron_an_element_class

[sagetrac-git]

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

60f3ddb

CombinatorialPolyhedra: New parent class, use it to make CombinatorialPolyhedron an element class

[sagetrac-git]

Commit: 60f3ddb

[sagetrac-git]

Changed commit from 60f3ddb to 4380cd0

[sagetrac-git]

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

4380cd0

src/sage/geometry/polyhedron/combinatorial_polyhedron/parent.py: Add missing imports

[sagetrac-git]

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

67d1e89	CombinatorialPolyhedralSets: Add element methods dim/dimension, subcategory Finite with parent method dimension
80026c2	PolyhedralSets: Make it a subcategory of CombinatorialPolyhedralSets

[sagetrac-git]

Changed commit from 4380cd0 to 80026c2

[sagetrac-git]

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

f8307da

CombinatorialPolyhedra: Use the category CombinatorialPolyhedralSets()

[sagetrac-git]

Changed commit from 80026c2 to f8307da

[mkoeppe]

comment:6

Here's a beginning, without adding anything useful yet.

[mkoeppe]

Author: Matthias Koeppe

[kliem]

comment:8

Thanks for taking care of this.

I have no experience with categories and what is best practice there. But I think it makes sense to mention my ideas/plans for this module so they can be considered if they need to.

Status quo (from my point of view):

CombinatorialPolyhedron is mainly a wrapper around FaceIterator. To make it complete, there is also PolyhedronFaceLattice which collects all faces from the FaceIterator and calculates all the cover relations.

FaceIterator works for simplicial complexes and for the intersection lattice of reflection groups of a root system (as in ReflectionGroup(['E',6])).

Plans, Ideas:

• Implement parallel f-vector for polytopes #31245 uses the FaceIterator in parallel for the f-vector. This parallel approach is applicable to other problems.
• Now that we use data_structures/bitset the underlying bitsets are much easier to handle. This allows doing polyhedral constructions just on the combinatorial polyhedron (and trusting bitsets to do the right thing instead of rethinking everything).
• Eventually some of the code should be moved to a more generic place in sage. Probably it makes sense to have CombinatorialPolyhedron inherit from a more generic interface to FaceIterator. (I'm currently waiting for Implement parallel f-vector for polytopes #31245). Then simplicial complexes and reflection groups should have access to it as well. In the end it is just an iterator that works over lattices with one of the following properties (atomic = all elements are joins of atoms):
  • intervals of length 2 contain at least 2 elements (true for polytopes and true enough for unbounded polyhedra)
  • simplicial coatomic lattices (or the dual thing) -- a lattice where each interval not containing the upper bound is boolean (true for simplicial complexes and for simplicial polytopes), this iterator is much faster than the previous version
  • it would also for atomic and coatomic lattices in general with some minor changes (however, I don't see a use case yet)
• There is still the big agenda that CombinatorialPolyhedron should replace all combinatorial things in cones, lattice polytopes and polyhedra. In particular it should deprecate sage/src/sage/geometry/hasse_diagram.py.

[mkoeppe]

comment:9

Thanks a lot for sharing this valuable perspective.

Regarding PolyhedronFaceLattice, perhaps this could become a parent class in the categories CombinatorialPolyhedralSets and FiniteLatticePosets. (Currently you go through making a digraph and calling Poset -- perhaps this can be implemented more directly.)

I think most of the other things are orthogonal to this ticket.

[sagetrac-git]

Changed commit from f8307da to c0c7631

[sagetrac-git]

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

c0c7631

sage.geometry.polyhedron.combinatorial_polyhedron.{homset,morphism}: New

[mkoeppe]

comment:12

Missing: The actual implementation of the morphism (CombinatorialPolyhedraMorphism.__call__ method).

[mkoeppe]

Dependencies: #30469

[mkoeppe]

Changed dependencies from #30469 to #30469, #31821

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

3896c32	fix naming and fix a doctest
82db408	reintroduce spaces to fix merge conflict
f460b23	improve documentation
479f743	better variable names for documentation
ab9d41e	Merge #30469
79983a9	fix pickling of representation objects with backend normaliz
5e65a5e	add doctest
b285d95	run testsuite on combinatorial polyhedron
db82c83	Merge #31821
25f7e34	CombinatorialPolyhedron: Make it a factory function, rename class to CombinatorialPolyhedron_class

[sagetrac-git]

Changed commit from c0c7631 to 25f7e34

[sagetrac-git]

Changed commit from 25f7e34 to 24e2d5d

[sagetrac-git]

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

24e2d5d

CombinatorialPolyhedraMorphism: Add example

[mkoeppe]

comment:17

Should SimplicialComplexes become a subcategory of CombinatorialPolyhedralSets?

[sagetrac-git]

Changed commit from 24e2d5d to df05a1a

[sagetrac-git]

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

df05a1a

SimplicialComplexes: Make it a subcategory of CombinatorialPolyhedralSets

[sagetrac-git]

Changed commit from df05a1a to 0a15b46

[sagetrac-git]

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

f9d15f3	sage.categories.polyhedra (PolyhedralSets): Explain what the parents and elements are
1f1922a	sage.categories.combinatorial_polyhedral_sets: New
6728fdc	CombinatorialPolyhedra: New parent class, use it to make CombinatorialPolyhedron an element class
ced1988	CombinatorialPolyhedralSets: Add element methods dim/dimension, subcategory Finite with parent method dimension
633db6d	PolyhedralSets: Make it a subcategory of CombinatorialPolyhedralSets
c3ccc63	CombinatorialPolyhedra: Use the category CombinatorialPolyhedralSets()
05aa347	sage.geometry.polyhedron.combinatorial_polyhedron.{homset,morphism}: New
0aa274f	CombinatorialPolyhedron: Make it a factory function, rename class to CombinatorialPolyhedron_class
d0243fb	CombinatorialPolyhedraMorphism: Add example
0a15b46	SimplicialComplexes: Make it a subcategory of CombinatorialPolyhedralSets

[mkoeppe]

Changed dependencies from #30469, #31821 to none