Sage: Ticket #29898: vertex facet graph for trivial polyhedra fails
https://trac.sagemath.org/ticket/29898
<p>
The vertex facet graph of <code>CombinatorialPolyhedron</code> only works for polyhedra of dimension at least one. With <a class="closed ticket" href="https://trac.sagemath.org/ticket/29188" title="enhancement: Move vertex facet graph to combinatorial polyhedron (closed: fixed)">#29188</a> this makes it fail with for <code>Polyhedron_base</code> as well.
</p>
<p>
We fix this to return
</p>
<ul><li>the <code>Digraph</code> on 0 vertices for the empty polyhedron and
</li><li>the <code>Digraph</code> on 1 vertex for the 0-dimensional polyhedron (it was misbehaved even before <a class="closed ticket" href="https://trac.sagemath.org/ticket/29188" title="enhancement: Move vertex facet graph to combinatorial polyhedron (closed: fixed)">#29188</a>).
</li></ul><p>
We also "fix" the definition of facets to correspond to inequalities.
The <code>0</code>-dimensional polyhedron does not have facets in this case anymore.
(Before this ticket <code>n_facets</code> and <code>facets</code> would use different definitions of facets.)
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/29898
Trac 1.1.6gh-kliemFri, 19 Jun 2020 14:34:28 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/29898#comment:1
https://trac.sagemath.org/ticket/29898#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>790dfbcad639920619b3d792f728c6d4070bc40f</em>
</li>
<li><strong>branch</strong>
set to <em>public/29898</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=790dfbcad639920619b3d792f728c6d4070bc40f"><span class="icon"></span>790dfbc</a></td><td><code>fix trivial vertex facet graphs</code>
</td></tr></table>
TicketgitFri, 19 Jun 2020 17:40:40 GMTcommit changed
https://trac.sagemath.org/ticket/29898#comment:2
https://trac.sagemath.org/ticket/29898#comment:2
<ul>
<li><strong>commit</strong>
changed from <em>790dfbcad639920619b3d792f728c6d4070bc40f</em> to <em>d7cca4927943438b7091e10d036d08b19279f0a2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=d7cca4927943438b7091e10d036d08b19279f0a2"><span class="icon"></span>d7cca49</a></td><td><code>correct fix for 0-dimensional polyhedron</code>
</td></tr></table>
TicketmkoeppeMon, 22 Jun 2020 05:01:43 GMT
https://trac.sagemath.org/ticket/29898#comment:3
https://trac.sagemath.org/ticket/29898#comment:3
<p>
Does a 0-dimensional polyhedron really have a facet??
</p>
Ticketgh-kliemMon, 22 Jun 2020 06:14:49 GMT
https://trac.sagemath.org/ticket/29898#comment:4
https://trac.sagemath.org/ticket/29898#comment:4
<p>
I would say so. This is the "definition" from Günter Zieglers book "Lectures on Polytopes":
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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
</p>
<pre class="wiki">sage: P = Polyhedron([[0]])
sage: P.incidence_matrix()
[1]
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^1,)
</pre><p>
But of course, I might have be influential to "bug fixes" to make it behave like this.
</p>
TicketmkoeppeMon, 22 Jun 2020 06:18:38 GMT
https://trac.sagemath.org/ticket/29898#comment:5
https://trac.sagemath.org/ticket/29898#comment:5
<p>
Hm... the old version of Ziegler's at <a class="ext-link" href="https://arxiv.org/pdf/math/9909177.pdf"><span class="icon"></span>https://arxiv.org/pdf/math/9909177.pdf</a> says "The maximal non-trivial faces, of dimension dim(P) − 1, are the facets of P." -- which excludes the empty face as a possibility.
</p>
TicketmkoeppeMon, 22 Jun 2020 06:21:45 GMT
https://trac.sagemath.org/ticket/29898#comment:6
https://trac.sagemath.org/ticket/29898#comment:6
<p>
I find the version that allows the empty face pretty disturbing.
</p>
Ticketgh-kliemMon, 22 Jun 2020 06:23:03 GMT
https://trac.sagemath.org/ticket/29898#comment:7
https://trac.sagemath.org/ticket/29898#comment:7
<p>
Either definition is trouble:
</p>
<ul><li>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.
</li><li>If you define the facets by maximality than you loose that correspondence.
</li></ul>
Ticketgh-kliemMon, 22 Jun 2020 06:23:33 GMT
https://trac.sagemath.org/ticket/29898#comment:8
https://trac.sagemath.org/ticket/29898#comment:8
<p>
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.
</p>
TicketmkoeppeMon, 22 Jun 2020 06:25:40 GMT
https://trac.sagemath.org/ticket/29898#comment:9
https://trac.sagemath.org/ticket/29898#comment:9
<p>
Well the empty face is maximal in the proper faces but not maximal in the nontrivial faces.
</p>
Ticketgh-kliemMon, 22 Jun 2020 06:31:35 GMT
https://trac.sagemath.org/ticket/29898#comment:10
https://trac.sagemath.org/ticket/29898#comment:10
<p>
In the new definition that is different:
</p>
<blockquote class="citation">
<p>
We consider the polytope itself as a trivial
face; all other faces are called proper faces
</p>
</blockquote>
<p>
And then comes the part that I already quoted.
</p>
<p>
But...
</p>
<p>
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.
</p>
<p>
Than we have our irreducible inequality/facet correspondence. So I agree with you that this definition makes more sense.
</p>
<p>
But that would involve a few "fixes".
</p>
<p>
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.
</p>
Ticketgh-kliemMon, 22 Jun 2020 08:36:27 GMT
https://trac.sagemath.org/ticket/29898#comment:11
https://trac.sagemath.org/ticket/29898#comment:11
<blockquote class="citation">
<p>
An inequality is irredundant if and only if it defines a facet of P
and no multiple of it is contained in the system.
</p>
</blockquote>
<p>
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.
</p>
<p>
Btw the polarity for 0-dimensional polyhedra is broken as well (but only for base ring <code>ZZ</code>):
</p>
<pre class="wiki">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
</pre>
Ticketgh-kliemMon, 22 Jun 2020 10:32:57 GMT
https://trac.sagemath.org/ticket/29898#comment:12
https://trac.sagemath.org/ticket/29898#comment:12
<pre class="wiki">sage: P = Polyhedron([[]])
sage: P.n_facets()
0
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^0,)
</pre>
TicketmkoeppeFri, 26 Jun 2020 16:50:37 GMTstatus changed
https://trac.sagemath.org/ticket/29898#comment:13
https://trac.sagemath.org/ticket/29898#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/29898#comment:12" title="Comment 12">gh-kliem</a>:
</p>
<blockquote class="citation">
<pre class="wiki">sage: P = Polyhedron([[]])
sage: P.n_facets()
0
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^0,)
</pre></blockquote>
<p>
Yes, this is not good.
</p>
Ticketgh-kliemSat, 27 Jun 2020 09:46:00 GMT
https://trac.sagemath.org/ticket/29898#comment:14
https://trac.sagemath.org/ticket/29898#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/29898#comment:13" title="Comment 13">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/29898#comment:12" title="Comment 12">gh-kliem</a>:
</p>
<blockquote class="citation">
<pre class="wiki">sage: P = Polyhedron([[]])
sage: P.n_facets()
0
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^0,)
</pre></blockquote>
<p>
Yes, this is not good.
</p>
</blockquote>
<p>
The reason for this is simple. <code>n_facets</code> is just an alias of <code>n_inequalities</code>.
</p>
<p>
Either way, we cannot have it consistent:
</p>
<ul><li>The class of polyhedra without inequalities doesn't have any facets.
</li><li>Facets of polyhedra correspond to coatoms of their face lattice.
</li><li>vertices of polytopes correspond to facets of their polar/dual.
</li><li>(irredundant) Inequalities of polyhedra correspond to facets.
</li></ul><p>
I personally think that we should define facets as the <code>d-1</code>-faces of <code>d</code>-polyhedra.
</p>
<p>
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.
</p>
TicketmkoeppeSat, 27 Jun 2020 17:58:32 GMT
https://trac.sagemath.org/ticket/29898#comment:15
https://trac.sagemath.org/ticket/29898#comment:15
<p>
Either way, definitely <code>n_facets()</code> must be the same as the cardinality of <code>facets()</code>.
</p>
<p>
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).
</p>
TicketjipilabMon, 29 Jun 2020 07:35:09 GMT
https://trac.sagemath.org/ticket/29898#comment:16
https://trac.sagemath.org/ticket/29898#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/29898#comment:15" title="Comment 15">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Either way, definitely <code>n_facets()</code> must be the same as the cardinality of <code>facets()</code>.
</p>
<p>
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).
</p>
</blockquote>
<p>
+1
</p>
<p>
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...
</p>
<p>
Obviously, things go wrong in the following case:
</p>
<blockquote>
<p>
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...)
</p>
</blockquote>
<p>
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).
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
With this perspective, the next step is that
</p>
<blockquote>
<p>
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?
</p>
</blockquote>
Ticketgh-kliemMon, 29 Jun 2020 07:56:21 GMT
https://trac.sagemath.org/ticket/29898#comment:17
https://trac.sagemath.org/ticket/29898#comment:17
<p>
The case where vertices and facets are the same, is for 1-dimensional polyhedra.
</p>
Ticketgh-kliemMon, 29 Jun 2020 08:11:23 GMT
https://trac.sagemath.org/ticket/29898#comment:18
https://trac.sagemath.org/ticket/29898#comment:18
<p>
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 RR<sup>2
</sup></p>
<p>
The 0-dimensional polytope belongs to that family.
</p>
<p>
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.
</p>
<p>
To summarize this discussion, I think we agree that we should alter <code>facets</code> 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?
</p>
TicketmkoeppeSat, 04 Jul 2020 19:21:34 GMT
https://trac.sagemath.org/ticket/29898#comment:19
https://trac.sagemath.org/ticket/29898#comment:19
<p>
I think it's fine to do this here on this ticket.
</p>
Ticketgh-kliemSun, 05 Jul 2020 06:01:13 GMTstatus changed
https://trac.sagemath.org/ticket/29898#comment:20
https://trac.sagemath.org/ticket/29898#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_work</em>
</li>
</ul>
<p>
I will.
</p>
Ticketgh-kliemSun, 05 Jul 2020 08:03:53 GMTdescription changed
https://trac.sagemath.org/ticket/29898#comment:21
https://trac.sagemath.org/ticket/29898#comment:21
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/29898?action=diff&version=21">diff</a>)
</li>
</ul>
Ticketgh-kliemSun, 05 Jul 2020 08:46:04 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/29898#comment:22
https://trac.sagemath.org/ticket/29898#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>d7cca4927943438b7091e10d036d08b19279f0a2</em> to <em>d4379565f70a25c335d9f000450fa8239d1d557c</em>
</li>
<li><strong>branch</strong>
changed from <em>public/29898</em> to <em>public/29898-reb</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=569cdce2de2d6bd19df8a324e0874ccb6785ae0a"><span class="icon"></span>569cdce</a></td><td><code>Merge branch 'public/29898' of git://trac.sagemath.org/sage into public/29898-reb</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=d4379565f70a25c335d9f000450fa8239d1d557c"><span class="icon"></span>d437956</a></td><td><code>fix definition of facets</code>
</td></tr></table>
TicketmkoeppeMon, 06 Jul 2020 21:26:25 GMTreviewer set
https://trac.sagemath.org/ticket/29898#comment:23
https://trac.sagemath.org/ticket/29898#comment:23
<ul>
<li><strong>reviewer</strong>
set to <em>Matthias Koeppe</em>
</li>
</ul>
<p>
Typo "non-trival" -> "nontrivial".
</p>
<p>
When done, you can set "positive review"
</p>
TicketgitTue, 07 Jul 2020 06:01:01 GMTcommit changed
https://trac.sagemath.org/ticket/29898#comment:24
https://trac.sagemath.org/ticket/29898#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>d4379565f70a25c335d9f000450fa8239d1d557c</em> to <em>25cfaa04806fdd91dc1d5aebac5b946d10f19f83</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=25cfaa04806fdd91dc1d5aebac5b946d10f19f83"><span class="icon"></span>25cfaa0</a></td><td><code>typo</code>
</td></tr></table>
Ticketgh-kliemTue, 07 Jul 2020 06:01:45 GMTstatus changed
https://trac.sagemath.org/ticket/29898#comment:25
https://trac.sagemath.org/ticket/29898#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Thank you.
</p>
TicketvbraunFri, 10 Jul 2020 19:33:57 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/29898#comment:26
https://trac.sagemath.org/ticket/29898#comment:26
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/29898-reb</em> to <em>25cfaa04806fdd91dc1d5aebac5b946d10f19f83</em>
</li>
</ul>
Ticketgh-kliemThu, 27 Aug 2020 05:14:10 GMTdescription changed; commit deleted
https://trac.sagemath.org/ticket/29898#comment:27
https://trac.sagemath.org/ticket/29898#comment:27
<ul>
<li><strong>commit</strong>
<em>25cfaa04806fdd91dc1d5aebac5b946d10f19f83</em> deleted
</li>
<li><strong>description</strong>
modified (<a href="/ticket/29898?action=diff&version=27">diff</a>)
</li>
</ul>
Ticket