Opened 10 months ago

Closed 9 months ago

Last modified 8 months ago

#29898 closed defect (fixed)

vertex facet graph for trivial polyhedra fails

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords: polyhedra, vertex facet graph
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 25cfaa0 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

The vertex facet graph of CombinatorialPolyhedron only works for polyhedra of dimension at least one. With #29188 this makes it fail with for Polyhedron_base as well.

We fix this to return

  • the Digraph on 0 vertices for the empty polyhedron and
  • the Digraph on 1 vertex for the 0-dimensional polyhedron (it was misbehaved even before #29188).

We also "fix" the definition of facets to correspond to inequalities. The 0-dimensional polyhedron does not have facets in this case anymore. (Before this ticket n_facets and facets would use different definitions of facets.)

Change History (27)

comment:1 Changed 10 months ago by gh-kliem

  • Branch set to public/29898
  • Commit set to 790dfbcad639920619b3d792f728c6d4070bc40f
  • Status changed from new to needs_review

New commits:

790dfbcfix trivial vertex facet graphs

comment:2 Changed 10 months ago by git

  • Commit changed from 790dfbcad639920619b3d792f728c6d4070bc40f to d7cca4927943438b7091e10d036d08b19279f0a2

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

d7cca49correct fix for 0-dimensional polyhedron

comment:3 Changed 10 months ago by mkoeppe

Does a 0-dimensional polyhedron really have a facet??

comment:4 Changed 10 months ago by gh-kliem

I would say so. This is the "definition" from Günter Zieglers book "Lectures on Polytopes":

Also the empty set is a face for every polytope. Less trivially, one has as faces the vertices of the polytope, which are single points, the edges, which are 1-dimensional line segments, and the facets, i.e., the maximal proper faces, whose dimension is one less than that of the polytope itself.

According to this the facets of the 0-dimensional polytope is the empty face. And I would say that this is reasonable. There is also an inequality defining that face: "(0,...,0)*x + 1 >= 0" (and the 0-vector might have lenght 0 according to ambient dimension). This is how it is currently handled in most parts

sage: P = Polyhedron([[0]])
sage: P.incidence_matrix()
[1]
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^1,)

But of course, I might have be influential to "bug fixes" to make it behave like this.

comment:5 Changed 10 months ago by mkoeppe

Hm... the old version of Ziegler's at https://arxiv.org/pdf/math/9909177.pdf says "The maximal non-trivial faces, of dimension dim(P) − 1, are the facets of P." -- which excludes the empty face as a possibility.

comment:6 Changed 10 months ago by mkoeppe

I find the version that allows the empty face pretty disturbing.

comment:7 Changed 10 months ago by gh-kliem

Either definition is trouble:

  • If you define facets by correspondence with irreducible inequalites than the empty face of the 0-dimensional polytope is not a facet. However it is certainly maximal.
  • If you define the facets by maximality than you loose that correspondence.

comment:8 Changed 10 months ago by gh-kliem

Either way, I set up the vertex-facet graph wrong. There shouldn't be an edge, as the vertex is not contained in the facet.

comment:9 Changed 10 months ago by mkoeppe

Well the empty face is maximal in the proper faces but not maximal in the nontrivial faces.

comment:10 Changed 10 months ago by gh-kliem

In the new definition that is different:

We consider the polytope itself as a trivial face; all other faces are called proper faces

And then comes the part that I already quoted.

But...

The facets not corresponding to inequalities is huge trouble. I myself made "mistakes" because of that. It seems much easier to define the facets as maximal non-trival faces with the empty face being trivial as well.

Than we have our irreducible inequality/facet correspondence. So I agree with you that this definition makes more sense.

But that would involve a few "fixes".

I'll also send a quick note to Günter Ziegler and see what he thinks, as he is still revising his new definition I believe.

comment:11 Changed 10 months ago by gh-kliem

An inequality is irredundant if and only if it defines a facet of P and no multiple of it is contained in the system.

This statement is exercise 2.15 (iii) and clearly doesn't fit to the definition. Then again we loose the vertex-facet correspondence for polarity.

Btw the polarity for 0-dimensional polyhedra is broken as well (but only for base ring ZZ):

sage: P = Polyhedron([[]])
sage: P
A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex
sage: P.polar()
The empty polyhedron in ZZ^0

comment:12 follow-up: Changed 10 months ago by gh-kliem

sage: P = Polyhedron([[]])
sage: P.n_facets()
0
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^0,)

comment:13 in reply to: ↑ 12 ; follow-up: Changed 10 months ago by mkoeppe

  • Status changed from needs_review to needs_info

Replying to gh-kliem:

sage: P = Polyhedron([[]])
sage: P.n_facets()
0
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^0,)

Yes, this is not good.

comment:14 in reply to: ↑ 13 Changed 10 months ago by gh-kliem

Replying to mkoeppe:

Replying to gh-kliem:

sage: P = Polyhedron([[]])
sage: P.n_facets()
0
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^0,)

Yes, this is not good.

The reason for this is simple. n_facets is just an alias of n_inequalities.

Either way, we cannot have it consistent:

  • The class of polyhedra without inequalities doesn't have any facets.
  • Facets of polyhedra correspond to coatoms of their face lattice.
  • vertices of polytopes correspond to facets of their polar/dual.
  • (irredundant) Inequalities of polyhedra correspond to facets.

I personally think that we should define facets as the d-1-faces of d-polyhedra.

But I have no hard feelings either way. It just should be made clear that the 0-polytope cannot be made consistent in some ways.

comment:15 follow-up: Changed 10 months ago by mkoeppe

Either way, definitely n_facets() must be the same as the cardinality of facets().

To me, the bijection between facets and irredundant inequalities is the most important. Let me add that even the status of the empty set as a face is not uniform across the literature. For example, in Schrijver, Theory of Linear and Integer Programming, faces are nonempty by definition (section 8.3), and the face lattice is obtained by considering the empty set as a special element in addition to the faces (section 8.6).

comment:16 in reply to: ↑ 15 Changed 10 months ago by jipilab

Replying to mkoeppe:

Either way, definitely n_facets() must be the same as the cardinality of facets().

To me, the bijection between facets and irredundant inequalities is the most important. Let me add that even the status of the empty set as a face is not uniform across the literature. For example, in Schrijver, Theory of Linear and Integer Programming, faces are nonempty by definition (section 8.3), and the face lattice is obtained by considering the empty set as a special element in addition to the faces (section 8.6).

+1

Looking at the subsets of the polytope obtained through supporting hyperplanes gives faces. My interpretation here is that it is a combinatorial discussion to have "the whole polytope" and "the empty face" included in the poset of faces, as of course adding them makes it a lattice. This act of "adding the trivial faces" forces an eventual consideration of "non-proper/non-trivial" faces when defining anything...

Obviously, things go wrong in the following case:

one removes the non-proper faces and obtains a poset which consists of an anti-chain (can only contain 1 or 2 elements in our case...)

In this case, "vertices" and "facets" are the same. Now you can even go wild and think about the actual object in space (not-being full-dimensional).

If you have one element only, i.e., you have a 0-dimensional polytope, then, what happens combinatorially is that the two elements are fusioned into one and yes, there isn't a bijection between actual maximal subsets given by supporting hyperplanes and the facet defining inequalities.

I would say that the 0-dimensional polytopes form "the exception that confirms the rule", as we say in French. Because of the fact that vertices and facet are the same, this creates this special situation, otherwise, the bijection should exist.

With this perspective, the next step is that

one removes the non-proper faces and obtains an empty poset, for the empty polyhedron. Does the empty polyhedron have facets? I hope not, right?

comment:17 Changed 10 months ago by gh-kliem

The case where vertices and facets are the same, is for 1-dimensional polyhedra.

comment:18 Changed 10 months ago by gh-kliem

One other problem with the definition as maximal subfaces (including the empty face) is that it doesn't make any sense for any polyhedron without inequalities. Surely you don't want that the empty face is a facet of RR2

The 0-dimensional polytope belongs to that family.

The other thing is that the vertex-facet-digraph relies on the fact that vertices are contained in facets or not. If facets are -1-dimensional and vertices 0-dimensional, this doesn't make any sense anymore.

To summarize this discussion, I think we agree that we should alter facets and maybe other methods, such that facets need to be proper faces of polyhedra. Where proper means neither empty nor full-dimensional. Should I open a seperate ticket for it?

comment:19 Changed 9 months ago by mkoeppe

I think it's fine to do this here on this ticket.

comment:20 Changed 9 months ago by gh-kliem

  • Status changed from needs_info to needs_work

I will.

comment:21 Changed 9 months ago by gh-kliem

  • Description modified (diff)

comment:22 Changed 9 months ago by gh-kliem

  • Branch changed from public/29898 to public/29898-reb
  • Commit changed from d7cca4927943438b7091e10d036d08b19279f0a2 to d4379565f70a25c335d9f000450fa8239d1d557c
  • Status changed from needs_work to needs_review

New commits:

569cdceMerge branch 'public/29898' of git://trac.sagemath.org/sage into public/29898-reb
d437956fix definition of facets

comment:23 Changed 9 months ago by mkoeppe

  • Reviewers set to Matthias Koeppe

Typo "non-trival" -> "nontrivial".

When done, you can set "positive review"

comment:24 Changed 9 months ago by git

  • Commit changed from d4379565f70a25c335d9f000450fa8239d1d557c to 25cfaa04806fdd91dc1d5aebac5b946d10f19f83

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

25cfaa0typo

comment:25 Changed 9 months ago by gh-kliem

  • Status changed from needs_review to positive_review

Thank you.

comment:26 Changed 9 months ago by vbraun

  • Branch changed from public/29898-reb to 25cfaa04806fdd91dc1d5aebac5b946d10f19f83
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:27 Changed 8 months ago by gh-kliem

  • Commit 25cfaa04806fdd91dc1d5aebac5b946d10f19f83 deleted
  • Description modified (diff)
Note: See TracTickets for help on using tickets.