===== A Counter-example to an integer analog to Caratheodory's Theorem =====
==== The construction ====
This tutorial describes the construction of a specific rational cone in six dimensions which is due to:
* Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert: A counterexample to an integer analogue of Carathéodory's theorem. J. Reine Angew. Math. 510 (1999), 179-185.
The rows of this matrix describe a cone //C//:
> $M = new Matrix([[0,1,0,0,0,0],
> [0,0,1,0,0,0],
> [0,0,0,1,0,0],
> [0,0,0,0,1,0],
> [0,0,0,0,0,1],
> [1,0,2,1,1,2],
> [1,2,0,2,1,1],
> [1,1,2,0,2,1],
> [1,1,1,2,0,2],
> [1,2,1,1,2,0]]);
> $C=new Polytope(POINTS=>$M);
From
> print $C->HILBERT_BASIS;
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
1 0 2 1 1 2
1 1 1 2 0 2
1 1 2 0 2 1
1 2 0 2 1 1
1 2 1 1 2 0
one can see that the given generators of //C// form a Hilbert basis. Now we consider one particular point //x//. The output of the second command (all coefficients positive) shows that //x// is contained in the interior of //C//.
> $x=new Vector([9,13,13,13,13,13]);
> print $C->FACETS * $x;
17 13 13 17 13 15/7 19/8 17 13 13 17 15/7 19/8 9 4 4 4 4 4 17 19/8 15/7 19/8 15/7 19/8 11/6 15/7
The following loop iterates over all invertible 6x6 submatrices of //M// and computes the unique representation of //x// as a linear combination of the rows of the submatrix. The output (suppressed as it is too long) shows that each such linear combination requires at least one negative or one non-integral coefficient.
> foreach (@{all_subsets_of_k(range(0,9),6)}) {
> $B = $M->minor($_,All);
> if (det($B)) {
> print lin_solve(transpose($B),$x), "\n";
> }
> }
13 -5 4 4 -5 9
-5 13 -5 4 4 9
4 -5 13 -5 4 9
4 4 -5 13 -5 9
-5 4 4 -5 13 9
3 5 -1 4 4 5
8 -5 9 -1 4 5
8 -5/2 4 3/2 13/2 5/2
-1 9 -5 8 5 4
-5 17 -9 8 13 -4
4 -1 5 3 5 4
8 -9 17 -5 13 -4
3/2 4 -5/2 8 13/2 5/2
9 -5 8 -1 5 4
17 -9 8 -5 13 -4
5 -1 4 3 5 4
-1 5 3 4 5 4
-9 17 -5 8 13 -4
-5 9 -1 8 5 4
4 -5/2 8 3/2 13/2 5/2
-5/2 4 3/2 8 5/2 13/2
7 -3 7 4 1 4
7 1 3 8 5 -4
11 -7 7 8 -3 4
7 -4 8 3 5 1
8 -4 7 5 3 1
19/2 -4 11/2 8 -3/2 5/2
7 -7 11 -3 8 4
3 1 7 5 8 -4
11/2 -4 19/2 8 5/2 -3/2
5 3 4 -1 5 4
17 -5 8 -9 13 -4
9 -1 8 -5 5 4
-5/2 8 3/2 4 13/2 5/2
-5 8 -1 9 4 5
4 3/2 8 -5/2 5/2 13/2
-9 8 -5 17 -4 13
-1 4 3 5 4 5
7/2 4 7/2 4 9/2 1/2
4 4 3 5 5 -1
4 7/2 7/2 9/2 4 1/2
-1 4 8 -5 5 9
8 -1/2 7/2 17/2 -4 9/2
4 3/2 11/2 5/2 4 5/2
3/2 4 11/2 5/2 5/2 4
-1/2 8 7/2 17/2 9/2 -4
4 -1 8 -5 9 5
7/3 7/3 19/3 5/3 17/3 5/3
-7 11 7 -3 8 4
1 7 3 5 8 -4
-3 7 7 1 4 4
1 3 7 5 -4 8
-7 7 11 -3 4 8
-4 19/2 11/2 8 5/2 -3/2
-4 8 7 5 1 3
-4 7 8 3 1 5
-4 11/2 19/2 -3/2 5/2 8
7 4 11 8 -3 -7
4 7 8 11 -7 -3
15 -4 19 -11 -7 8
-4 15 19 8 -7 -11
8 3/2 4 -5/2 13/2 5/2
8 -1 9 -5 4 5
3 4 -1 5 4 5
3/2 8 -5/2 4 5/2 13/2
8 -5 17 -9 -4 13
-5 8 -9 17 -4 13
4 3 5 -1 4 5
-1 8 -5 9 4 5
11/2 4 3/2 4 5/2 5/2
8 4 -1 9 5 -5
19/3 7/3 7/3 17/3 5/3 5/3
3 4 4 -1 5 5
8 -1 4 9 -5 5
11/2 3/2 4 4 5/2 5/2
7/2 4 7/2 1/2 9/2 4
7/2 8 -1/2 9/2 17/2 -4
7/2 -1/2 8 -4 17/2 9/2
7/2 7/2 4 4 9/2 1/2
4 11/2 3/2 5/2 5/2 4
8 7/2 -1/2 17/2 9/2 -4
4 7/2 7/2 9/2 1/2 4
-1 8 4 -5 9 5
4 3 4 5 -1 5
7/2 7/2 4 4 1/2 9/2
7/3 19/3 7/3 5/3 17/3 5/3
4 8 -1 5 9 -5
-1/2 7/2 8 -4 9/2 17/2
3/2 11/2 4 4 5/2 5/2
7 4 7 4 1 -3
4 7 1 4 7 -3
15/2 7/2 8 4 -7/2 1/2
7/2 15/2 4 8 1/2 -7/2
19/2 11/2 -4 8 5/2 -3/2
8 7 -4 5 1 3
11 7 -7 8 4 -3
7 8 -4 3 1 5
7 3 1 8 -4 5
7 7 -3 4 4 1
11/2 19/2 -4 -3/2 5/2 8
3 7 1 -4 8 5
7 11 -7 4 8 -3
15/2 7/2 8 1/2 -7/2 4
4 7 1 -3 7 4
7 4 7 -3 1 4
7/2 15/2 -7/2 1/2 8 4
15 -4 19 8 -7 -11
4 7 8 -3 -7 11
7 4 11 -7 -3 8
-4 15 -11 -7 8 19
11 15 4 -7 -7 4
8 -5/2 4 3/2 5/2 13/2
-5 17 -9 8 -4 13
8 -9 17 -5 -4 13
3/2 4 -5/2 8 5/2 13/2
3 5 -1 4 4 5
8 -5 9 -1 4 5
-1 9 -5 8 5 4
4 -1 5 3 5 4
11 -7 7 4 8 -3
8 -4 7 1 5 3
19/2 -4 11/2 5/2 8 -3/2
3 1 7 -4 5 8
11/2 -4 19/2 -3/2 8 5/2
7 -3 7 4 1 4
7 1 3 8 5 -4
7 -4 8 3 5 1
7 -7 11 -3 8 4
4 7/2 7/2 1/2 9/2 4
8 -1/2 7/2 9/2 17/2 -4
4 3/2 11/2 5/2 5/2 4
-1/2 8 7/2 -4 17/2 9/2
4 -1 8 5 -5 9
7/3 7/3 19/3 5/3 5/3 17/3
7/2 4 7/2 4 9/2 1/2
4 4 3 5 5 -1
-1 4 8 -5 5 9
3/2 4 11/2 5/2 5/2 4
4 7 -3 8 11 -7
15 -4 8 19 -11 -7
-4 15 -11 19 8 -7
7 4 11 8 -3 -7
19/3 7/3 7/3 5/3 17/3 5/3
8 -1 4 5 9 -5
11/2 3/2 4 5/2 4 5/2
7/2 8 -1/2 -4 9/2 17/2
7/2 -1/2 8 9/2 -4 17/2
7/2 7/2 4 1/2 4 9/2
11/2 4 3/2 4 5/2 5/2
8 4 -1 9 5 -5
3 4 4 -1 5 5
7/2 4 7/2 1/2 9/2 4
4 7 -3 1 4 7
15/2 7/2 1/2 8 4 -7/2
7/2 15/2 -7/2 4 8 1/2
7 4 7 4 1 -3
15/2 7/2 4 8 1/2 -7/2
4 7 4 1 -3 7
7 4 4 7 -3 1
7/2 15/2 4 -7/2 1/2 8
11 4 15 4 -7 -7
19/2 -4 11/2 -3/2 5/2 8
11/2 -4 19/2 5/2 -3/2 8
7 1 3 -4 8 5
7 -4 8 1 3 5
7 -7 11 4 -3 8
11 -7 7 4 8 -3
8 -4 7 1 5 3
3 1 7 -4 5 8
7 -3 7 4 1 4
4 7 -7 -3 8 11
15 -4 -7 8 19 -11
-4 15 -7 -11 19 8
7 4 -7 11 8 -3
15/2 7/2 -7/2 1/2 8 4
7/2 15/2 1/2 -7/2 4 8
7 4 -3 7 4 1
4 7 -3 1 4 7
11 -7 4 15 4 -7
15 -4 -11 -7 8 19
-4 15 8 -7 -11 19
7 4 -3 -7 11 8
4 7 -7 -3 8 11
11 -7 -7 4 15 4
11 4 -7 -7 4 15
This means that //x// cannot be represented as a non-negative linear combination of any six of the given generators of //C//.
==== Analyzing the combinatorics ====
The following is taken from
* Michael Joswig, Benjamin Müller, and Andreas Paffenholz: ''%%polymake%%'' and lattice polytopes. In Christian Krattenthaler, Volker Strehl and Manuel Kauers (eds.), Proceedings of the 21th International Conference on Formal Power Series and Algebraic Combinatoric, Hagenberg, Austria, 2009, pp. 493-504.
> print $C->N_VERTICES, " ", $C->DIM;
> print rows_labeled($C->VERTICES_IN_FACETS);
10 50:1 3 4 5 7
1:1 2 3 4 5
2:0 1 2 3 9
3:0 1 3 7 9
4:0 1 3 4 7
5:3 5 6 7 9
6:3 4 5 6 7
7:0 2 3 6 9
8:0 2 3 4 6
9:0 1 2 4 8
10:0 2 4 6 8
11:2 5 6 8 9
12:2 3 5 6 9
13:0 1 2 3 4
14:1 2 3 5 7 9
15:0 3 4 6 7 9
16:0 1 2 6 8 9
17:2 3 4 5 6 8
18:0 1 4 5 7 8
19:1 2 4 5 8
20:0 1 7 8 9
21:1 5 7 8 9
22:1 2 5 8 9
23:0 6 7 8 9
24:0 4 6 7 8
25:5 6 7 8 9
26:4 5 6 7 8
There are two disjoint facets covering all the vertices. Beware the numbering of facets depends on the convex hull algorithm employed.
> print $C->VERTICES_IN_FACETS->[8];
> print $C->VERTICES_IN_FACETS->[22];
{0 2 3 4 6}{1 2 5 8 9}
> print rows_labeled($M);
0:0 1 0 0 0 0
1:0 0 1 0 0 0
2:0 0 0 1 0 0
3:0 0 0 0 1 0
4:0 0 0 0 0 1
5:1 0 2 1 1 2
6:1 2 0 2 1 1
7:1 1 2 0 2 1
8:1 1 1 2 0 2
9:1 2 1 1 2 0
Here is another polytope which is somewhat similar but not quite the same.
> $cross5=cross(5);
> print isomorphic($C,$cross5);
> print isomorphic($C->GRAPH->ADJACENCY,$cross5->GRAPH->ADJACENCY);
falsetrue
> print $cross5->F_VECTOR - $C->F_VECTOR;
0 0 0 5 5
Look at two facets of the five-dimensional cross polytope and their positions in the dual graph.
> print $cross5->VERTICES_IN_FACETS->[12];
> print $cross5->VERTICES_IN_FACETS->[13];
> print rows_labeled($cross5->DUAL_GRAPH->ADJACENCY);
{0 2 5 7 8}{1 2 5 7 8}0:1 2 4 8 16
1:0 3 5 9 17
2:0 3 6 10 18
3:1 2 7 11 19
4:0 5 6 12 20
5:1 4 7 13 21
6:2 4 7 14 22
7:3 5 6 15 23
8:0 9 10 12 24
9:1 8 11 13 25
10:2 8 11 14 26
11:3 9 10 15 27
12:4 8 13 14 28
13:5 9 12 15 29
14:6 10 12 15 30
15:7 11 13 14 31
16:0 17 18 20 24
17:1 16 19 21 25
18:2 16 19 22 26
19:3 17 18 23 27
20:4 16 21 22 28
21:5 17 20 23 29
22:6 18 20 23 30
23:7 19 21 22 31
24:8 16 25 26 28
25:9 17 24 27 29
26:10 18 24 27 30
27:11 19 25 26 31
28:12 20 24 29 30
29:13 21 25 28 31
30:14 22 26 28 31
31:15 23 27 29 30
Now we construct a new graph by manipulating the dual graph of the cross polytope by contracting a perfect matching.
> $g=new GraphAdjacency($cross5->DUAL_GRAPH->ADJACENCY);
> $g->contract_edge(12,13);
> $g->contract_edge(24,26);
> $g->contract_edge(17,21);
> $g->contract_edge(3,11);
> $g->contract_edge(6,22);
> $g->squeeze;
The last command renumbers the nodes sequentially, starting from 0. This is necessary to render the graph a valid object.
> print isomorphic($C->DUAL_GRAPH->ADJACENCY,$g);
true
This finally reveals the combinatorial structure: The cone //C// is a cone over a 5-polytope which can be obtained from the 5-dimensional cross polytope by straightening five pairs of adjacent (simplex) facets into bipyramids over 3-simplices.