Improve combinatorial_automorphism_group in polyhedra class

[mo271]

Currently, the combinatorial_automorphism_group method in the polyhedron class returns a group isomorphic to the automorphism group of the vertex-edge graph of the polyhedron. I propose to changes two the method:

(1) don't return a permutation group on the number 1, 2,.. self.n_vertices(), but rather a permutation group on the actual objects (vertices of the polyhedron)

(2) wide the functionality to not only return the automorphism group of the vertex-edge graph, but also of the vertex-facet graph.

The second improvement has the advantage that the automorphism group of the vertex-facet graph is the same as the automorphism of the face lattice.

Since the vertex-facet graph is also used in the related .is_combinatorially_isomorphic method (see #22500) and it might be useful on its own, it is now a seperate function.

Depends on #22500

CC: @jplab

Component: geometry

Keywords: polyhedron, days84

Author: Moritz Firsching

Branch/Commit: 128d28e

Reviewer: Jean-Philippe Labbé

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

[mo271]

Branch: u/moritz/combinatorial_automorphism_group

[mo271]

Commit: aa80ed3

[mo271]

Dependencies: https://trac.sagemath.org/ticket/22500

[mo271]

New commits:

508bc6b	initial version
ca97480	pep8 errors fixed
03dbd96	better assertins, improved docstrings
5a2307d	reference added
0a29d25	whitespace
f0ec516	little improvements, change 'algo' to 'algorithm'
aa80ed3	new version of combinatorial_automorphism_group of polyhedra

[mo271]

comment:3

This addition does everything I propose to do and illustrate the differences with examples.

[jplab]

Changed dependencies from https://trac.sagemath.org/ticket/22500 to #22500

[videlec]

comment:5

• Aren't the vertices actually numbered from 0 up to n-1?

sage: p = polytopes.associahedron(['A',2])
sage: p.faces(0)
(<0>, <1>, <2>, <3>, <4>)

• typo in the ticket description returns the a group isomorphic

• in the docstring, I am not sure that whether to the graph is proper english

• Why _vertex_facet_graph starts with a underscore?

[mo271]

comment:6

Thanks for the comments, Vincent!

• about the numbering: yes the vertices have their labeling from 0 to n-1, and also the facets of dimension P.dim()-1 have their labeling. From this it is not quite clear to me, what the best labeling for the nodes in the vertex_facet_graph would be. if labels=True, we get consistent result with the .graph method:

sage: p = polytopes.associahedron(['A',2])
sage: p.graph().vertices()

[A vertex at (-1, 0),
 A vertex at (-1, 1),
 A vertex at (0, -1),
 A vertex at (1, -1),
 A vertex at (1, 1)]
sage: p.vertex_facet_graph().vertices()

[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,
 A vertex at (-1, 0),
 A vertex at (-1, 1),
 A vertex at (0, -1),
 A vertex at (1, -1),
 A vertex at (1, 1)]

The reason to have the options labels=False is basically only for internal use by the .is_combinatorially_isomorphic method.

• typo in the description fixed
• changed the sentence to "decide how the nodes of the graph are labelled. Either with the original vertices/facets of the Polyhedron or with integers."
• I have no strong opinion if this method should be public or start with an underscore, I guess there are reasons for both. (Now I removed the underscore).

[sagetrac-git]

Changed commit from aa80ed3 to a56630b

[sagetrac-git]

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

a56630b

make method cached and public; better wording for the INPUT docstring

[jplab]

comment:9

Is the description of the ticket missing a sentence at the end?

[jplab]

comment:10

• There is a space missing here:

sage: O=polytopes.octahedron(); O

• There is an indentation too much it seems in the OUTPUT field of combinatorial_automorphism_group

[sagetrac-git]

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

9843c05	new version of combinatorial_automorphism_group of polyhedra
950f824	make method cached and public; better wording for the INPUT docstring
e72d2cb	immprovements in docstring, including SEEALSOs

[sagetrac-git]

Changed commit from a56630b to e72d2cb

[mo271]

comment:13

Thanks for looking at the ticket, JP! I fixed up the things you mentioned and added some little improvements in the docstring. Also I rebased on the current rc0.

[sagetrac-git]

Changed commit from e72d2cb to 7fe551f

[sagetrac-git]

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

e07a18c	new version of combinatorial_automorphism_group of polyhedra
c303ed7	make method cached and public; better wording for the INPUT docstring
6b938f8	immprovements in docstring, including SEEALSOs
7fe551f	rebased

[jplab]

comment:17

There are failed doctests. See the bot shortlog,

**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 498, in sage.geometry.polyhedron.base.Polyhedron_base.vertex_facet_graph
Failed example:
    G.vertices()
Expected:
    [An inequality (-1, 0, 0) x + 1 >= 0,
     An inequality (0, -1, 0) x + 1 >= 0,
     An inequality (0, 0, -1) x + 1 >= 0,
     An inequality (0, 0, 1) x + 1 >= 0,
     An inequality (0, 1, 0) x + 1 >= 0,
     An inequality (1, 0, 0) x + 1 >= 0,
     A vertex at (-1, -1, -1),
     A vertex at (-1, -1, 1),
     A vertex at (-1, 1, -1),
     A vertex at (-1, 1, 1),
     A vertex at (1, -1, -1),
     A vertex at (1, -1, 1),
     A vertex at (1, 1, -1),
     A vertex at (1, 1, 1)]
Got:
    [A vertex at (-1, -1, -1),
     A vertex at (-1, -1, 1),
     A vertex at (-1, 1, -1),
     A vertex at (-1, 1, 1),
     A vertex at (1, -1, -1),
     A vertex at (1, -1, 1),
     A vertex at (1, 1, -1),
     A vertex at (1, 1, 1),
     An inequality (-1, 0, 0) x + 1 >= 0,
     An inequality (0, -1, 0) x + 1 >= 0,
     An inequality (0, 0, -1) x + 1 >= 0,
     An inequality (0, 0, 1) x + 1 >= 0,
     An inequality (0, 1, 0) x + 1 >= 0,
     An inequality (1, 0, 0) x + 1 >= 0]
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 4909, in sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group
Failed example:
    quadrangle.combinatorial_automorphism_group()
Expected:
    Permutation Group with generators [(An inequality (0,1) x + 0 >= 0,An inequality (1,0) x + 0 >= 0)(An inequality (1,-1) x + 1 >= 0,An inequality (-3,1) x + 3 >= 0)(A vertex at (0,1),A vertex at (1,0)), (An inequality (0,1) x + 0 >= 0,An inequality (1,-1) x + 1 >= 0)(A vertex at (0,0),A vertex at (0,1))(A vertex at (1,0),A vertex at (2,3))]
Got:
    Permutation Group with generators [(A vertex at (0,1),A vertex at (1,0))(An inequality (0,1) x + 0 >= 0,An inequality (1,0) x + 0 >= 0)(An inequality (1,-1) x + 1 >= 0,An inequality (-3,1) x + 3 >= 0), (A vertex at (0,0),A vertex at (0,1))(A vertex at (1,0),A vertex at (2,3))(An inequality (0,1) x + 0 >= 0,An inequality (1,-1) x + 1 >= 0)]
**********************************************************************

[jplab]

Reviewer: Jean-Philippe Labbé

[sagetrac-git]

Changed commit from 7fe551f to 128d28e

[sagetrac-git]

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

128d28e

fixed dependency on order in doctests

[mo271]

comment:20

This should fix the problem.

[jplab]

comment:21

Looks good to me.

[vbraun]

Changed branch from u/moritz/combinatorial_automorphism_group to 128d28e