Generalized (0, 1, 2)-polytopes

Generalized (0, 1, 2)-polytopes
Katy Beeler
Berlin Mathematical School
Berlin, Germany
katybeeler@mi.fu-berlin.deJanuary 19, 2017

K. Beeler
Generalized (0, 1, 2)-polytopes

BMSGeneralized (0, 1, 2)-polytopes

Motivation

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Definition
We say a polytope P ⊂ Rd is a (0, 1, 2)-polytope if for everyv ∈ vert(P), v ∈ {0, 1, 2}d .

K. Beeler
Generalized (0, 1, 2)-polytopes

BMSGeneralized (0, 1, 2)-polytopes

Definition
We say a polytope P ⊂ Rd is a (0, 1, a)-polytope if for everyv ∈ vert(P), v ∈ {0, 1, a}d .

K. Beeler
Generalized (0, 1, 2)-polytopes

BMSGeneralized (0, 1, 2)-polytopes

ExampleConsider the following (0, 1, 3)-polytope with vertex set:(1, 1, 0), (3, 0, 0), (0, 3, 0), (3, 3, 0), (0, 0, 1), (3, 0, 1),.
(0, 3, 1), (3, 3, 1), (0, 0, 3), (1, 0, 3), (0, 1, 3), (1, 1, 3)v

K. Beeler
Generalized (0, 1, 2)-polytopes

BMSGeneralized (0, 1, 2)-polytopes

Definition
Let a ∈ R d . We say a polytope P ⊂ Rd is a (0, 1, ai )-polytope if
for every v ∈ vert(P), v ∈ {0, 1, ai }d for i ∈ [d].

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

ExampleConsider the following (0, 1, ai )-polytope, for a = (2, 3, 4), withvertex set:(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 3, 0),(2, 1, 0), (2, 3, 1), (0, 0, 4), (1, 1, 4)v1v4

v7v0v2v3

K. Beeler
Generalized (0, 1, 2)-polytopes

v5v6BMSGeneralized (0, 1, 2)-polytopes

Question
Can we enumerate these guys?

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proposition
A (0, 1, 2)-polytope has at most 16 vertices.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

ExampleConsider the following polytope with vertex set:
 (1, 0, 0), (2, 0, 0), (2, 1, 0), (0, 1, 0), (0, 2, 0), (1, 2, 0), (0, 0, 1), (2, 0, 1), (0, 2, 1), (2, 2, 1), (0, 0, 2), (1, 0, 2),
(0, 1, 2), (2, 1, 2), (1, 2, 2), (2, 2, 2)

x3 = 0x3 = 1x3 = 2

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Question
Which values of a allow different combinatorial types?

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Find det(M) = 0 for

v1 v2 v3 v4 
M=
1 1 1 1for vi ∈ {0, 1, a}3 .

Only real solution greater than 2 is a = 3.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Find det(M) = 0 forv1 v2 v3 v4 
M=
1 1 1 1for vi ∈ {0, 1, a}3 .

Only real solution greater than 2 is a = 3.

Different combinatorial types could exist for(a)a=2(b)

2<a<3(c)a=3(d)

3<a

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Number of combinatorial types of (0, 1, a)-polytopes:
no. of vertices
678910111213
14
15
16
total
K. Beeler
Generalized (0, 1, 2)-polytopes

a=2
734
193
680
1758
2049
955
207
29
3
1
6017

2<a<3734
247
1215
∗
5243
2814
663
90
102
∗

a=3
734
249
1415
∗
6150
3134
700
91
102
∗

a>3
734
249
1406
∗
6196
3153
704
92
102
∗

total
734251
1462
∗
6437
3319
745
97
102
∗
BMS

Generalized (0, 1, 2)-polytopes

Question
Can we enumerate (0, 1, ai )-polytopes employing the previous
approach?

K. Beeler
Generalized (0, 1, 2)-polytopes

BMSGeneralized (0, 1, 2)-polytopes

Can we enumerate employing the previous approach?
Consider the 4 × 4 matrix
M = [mij ]where mij ∈ {0, 1, ai } and m4j = 1.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Can we enumerate employing the previous approach?
Consider the 4 × 4 matrix
M = [mij ]where mij ∈ {0, 1, ai } and m4j = 1.
334 determinants with solutions in the feasible range, R3≥2

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Can we enumerate employing the previous approach?
Consider the 4 × 4 matrix
M = [mij ]where mij ∈ {0, 1, ai } and m4j = 1.
334 determinants with solutions in the feasible range, R3≥2Choose ∼470, 000 points randomly, >540 distinct regions

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Can we enumerate employing the previous approach?
Consider the 4 × 4 matrix
M = [mij ]where mij ∈ {0, 1, ai } and m4j = 1.
334 determinants with solutions in the feasible range, R3≥2Choose ∼470, 000 points randomly, >540 distinct regions
Integral solutions return 188 distinct regions

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

The Hirsch conjectureStated by Warren M. Hirsch in 1957

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

The Hirsch conjectureStated by Warren M. Hirsch in 1957
Puts a bound on the diameter of a polytope with respect tothe number of facets

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

The Hirsch conjectureStated by Warren M. Hirsch in 1957
Puts a bound on the diameter of a polytope with respect tothe number of facets
Important with regards to the simplex method

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

The Hirsch conjectureStated by Warren M. Hirsch in 1957
Puts a bound on the diameter of a polytope with respect tothe number of facets
Important with regards to the simplex method

Disproven in general by Francisco Santos

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Statement of the Hirsch Conjecture
Let n > d ≥ 2. Let P be a d-dimensional polytope with n facets.
Then diam(P) ≤ n − d.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Theorem (Naddef, 1989)(0, 1)-polytopes satisfy the Hirsch conjecture.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof.
Step 1: The diameter is at most d.
Let u and v be distinct vertices of P.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof.
Step 1: The diameter is at most d.
Let u and v be distinct vertices of P.
We induct on the dimension d to show the diameter is at
most d.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMSGeneralized (0, 1, 2)-polytopes

Proof.
Step 1: The diameter is at most d.
Let u and v be distinct vertices of P.
We induct on the dimension d to show the diameter is at
most d.
Exhaustively check the case d = 2.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof.
Step 1: The diameter is at most d.
Let u and v be distinct vertices of P.
We induct on the dimension d to show the diameter is at
most d.
Exhaustively check the case d = 2.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof.
Step 1: The diameter is at most d.
Let u and v be distinct vertices of P.
We induct on the dimension d to show the diameter is at
most d.
Exhaustively check the case d = 2.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
Step 2: The Hirsch conjecture is satisfied.
Let u and v be distinct vertices of P.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
Step 2: The Hirsch conjecture is satisfied.
Let u and v be distinct vertices of P.
We induct once more on the dimension of P.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
Step 2: The Hirsch conjecture is satisfied.
Let u and v be distinct vertices of P.
We induct once more on the dimension of P.
Both u and v are contained in d facets. We are done if theyshare a common facet. Else, P contains at least 2d facets andwe’re done.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Hirsch conjecture on (0, 1, ai )-polytopes

Theorem
The diameter of a (0, 1, ai )-polytope is bounded by b 23 dc.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

This bound is tight!
In dimension 2, consider a hexagon.
In even dimension, consider the product of d2 hexagons.
In odd dimension, consider the prism over the product of d − 1hexagons.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

A little notation...

For i ∈ [d], we define
Vi0 := {v ∈ vert(P) : vi = 0}
Vi1 := {v ∈ vert(P) : vi = 1}
Vi2 := {v ∈ vert(P) : vi = ai }.
Note that Vi0 and Vi2 are either empty, or faces of P.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof.
We induct on the dimension d.
We want to show for u, v ∈ P, that one of the following two
inequalities holds:
δ(u, v ) ≤ δ d−1 + 1δ(u, v ) ≤ δ

K. Beeler
Generalized (0, 1, 2)-polytopes

d−2+3(1)(2)

BMS

Generalized (0, 1, 2)-polytopes

We can assume...

P is full-dimensional

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

We can assume...

P is full-dimensional

P intersects all facets of the d-orthotope[0, a1 ] × [0, a2 ] × [0, a3 ].

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
We will consider the following three cases:
Case 1. There exists an i ∈ [d] such that u ∈ V0i or V2i andv ∈ V1i .
Case 2. There exists an i ∈ [d] such that u, v ∈ V1i .
Case 3. For all i ∈ [d], |ui − vi | = ai .

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
Case 1: There exists an i ∈ [d] such that u ∈ V0i or V2i and v ∈ V1i .

Thus δ(u, v ) ≤ δ d−1 + 1 is satisfied.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
Case 2: There exists an i ∈ [d] such that u, v ∈ V1i .

Thus δ(u, v ) ≤ δ d−2 + 3 is satisfied.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

Proof ctd.
Case 3: For all i ∈ [d], |ui − vi | = ai .

Case 3aCase 3bThus, in Case 3a, δ(u, v ) ≤ δ d−1 + 1 is satisfied.
In Case 3b, δ(u, v ) ≤ δ d−2 + 3 is satisfied.
K. Beeler
Generalized (0, 1, 2)-polytopes

BMS

Generalized (0, 1, 2)-polytopes

References

Alberto Del Pia and Carla Michini. On the diameter of lattice
polytopes. Discrete and Computational Geometry,
55(3):681-687, April 2016.
D. Naddef. The Hirsch conjecture is true for (0, 1)-polytopes.
Math. Program., 45:109-110, 1989.
D. Naddef and W.R Pulleyblank. Hamiltonicity in(0,1)-polyhedra. Journal of Combinatorial Theory, Series B,
37(1):41 - 52, 1984.

K. Beeler
Generalized (0, 1, 2)-polytopes

BMS