what is the correct defintion of a vertex graph for polyhedra with lines?

[Jonathan Kliem]

In #28626 I want to use `CombinatorialPolyhedron` to obtain the vertex graph of polyhedra.

However, I seem to have a different opinion of a vertex graph than is currently implemented in sage.

Should the vertex graph of an unpointed polyhedron return the vertex graph of the projection or should it be empty?

As of now the method `vertices` returns the defining vertices, which are the proper vertices except for unpointed polyhedra.

I don't think this ambiguous meaning of vertex should continue for the vertex graph.

However the current behavior is at the moment assumed in a strange doctest of `combinatorial_automorphism_group`.

(E.g. the order of the combinatorial automorphism group does not change when you add lines.)

[jplab]

Hi Jonathan,

Could you be more precise with what you mean with "projection"?

What is the status quo? (Please provide a minimal reproducible working example that shows the contrast along with the proposed wished change that you have in mind, otherwise we are left to guess what you mean and that is leaving the door open to a lot of misunderstanding)

What is the proposed changed?

What is the assumption in the mentioned doctest?

For computational aid, when no vertices exists (i.e. there is a lineality space) the current implementation creates an appropriate vertex. I guess we have to deal with this eventhough the object does not have a 0-dimensional face in reality. This is to have consistency between H- and V-representations. In order to have a consistent V-representation, you need an anchor point, otherwise just having rays and lines does not determine uniquely the object.

That said, if you are interested in making a vertex-graph for unbounded polyhedra, then, edges should have two vertices.

One way is to ask to keep only bounded edges in the definition, and the default behavior gives the vertex graph on bounded edges. If one wants the full graph with a point at infinity that compactifies the full vertex graph, then one could do so by adding an optional parameter "unbounded=False/True". Where the default would be False and return only compact edges and True would return one more vertex "the vertex at infinity".

To me this seems to be the most reasonable behavior. I don't know if this answer your question.

[Jonathan Kliem]

Let me try again. This is the current behaviour:

sage: P = Polyhedron(vertices=[[-1,0],[1,0]],lines=[[0,1]]); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 line
sage: P.vertex_graph()
Graph on 2 vertices
sage: P.faces(0)
()

Let P be a polyhedron defined by vertices/rays/lines. The vertex graph of P returns basically the vertex graph for Q, where Q is defined by the same vertices and rays, but not lines.

So

sage: P = Polyhedron(vertices=my_vertices, rays=my_rays, lines=my_lines)
sage: Q = Polyhedron(vertices=my_vertices, rays=my_rays)

have vertex graphs that are canonically isomorphic.

I don't think this is the way it should be and the vertex graph in the first case should be empty. If no one disagrees I will apply this change in #28626.

However, the current behaviour is somewhat fixed by a doctest.

As I understand it, the mentioned doctest tries to make a point about

sage: P.combinatorial_automorphism_group(vertex_graph_only=True)

In this case it is stated that the automorphism group can only interchange vertices with vertices, rays with rays and lines with lines. Strictly speaking, this is correct. But an automorphism group obtained from this will never interchange rays with rays or lines with lines.

Even worse, it will completely ignore the rays and lines, so that

sage: P = Polyhedron(vertices=[[0,0,0],[0,1,1],[1,0,1],[-1,-1,1]],rays=[[0,0,1]]); P
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices and 1 ray
sage: len(P.combinatorial_automorphism_group(vertex_graph_only=True))
24

This is why I consider the doctest strange.

To me it does not make sense to use the vertex graph to obtain the automorphism group.

Btw (and really not the point of this post), I'm not sure that the automorphism group of the vertex-facet graph is what one should consider for the automorphism group of an unbounded polyhedron. At least in dimension higher than 4 this might behave differently than at least I would define it. I would instead consider the vertex-facet-graph with an extra marked vertex at infinity.

[Dima Pasechnik]

t

On Sat, Oct 19, 2019 at 1:59 PM 'Jonathan Kliem' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> Let me try again. This is the current behaviour:
>
> sage: P = Polyhedron(vertices=[[-1,0],[1,0]],lines=[[0,1]]); P
> A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 line
> sage: P.vertex_graph()
> Graph on 2 vertices
> sage: P.faces(0)
> ()
>
> Let P be a polyhedron defined by vertices/rays/lines. The vertex graph of P returns basically the vertex graph for Q, where Q is defined by the same vertices and rays, but not lines.
>
> So
> sage: P = Polyhedron(vertices=my_vertices, rays=my_rays, lines=my_lines)
> sage: Q = Polyhedron(vertices=my_vertices, rays=my_rays)
>
> have vertex graphs that are canonically isomorphic.

V-representation is only unique for compact polyhedra, anyway, so one
can talk about the graph of
a V-representation, not about the graph of a polyhedron, in general.

To me, a polyhedron with a linearity space should have no vertices, full stop.
Compute a partial decomposition into the linearity space and something
poined, then do something with it...

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/91149799-da9b-49a4-b9c0-bd9629a386e3%40googlegroups.com.