user_guide:tutorials:latest:caratheodory

Differences

This shows you the differences between two versions of the page.


—user_guide:tutorials:latest:caratheodory [2023/11/06 10:57] (current) – created - external edit 127.0.0.1
Line 1: Line 1:
 +===== 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//:
 +
 +<code perl>
 +> $M = new Matrix<Rational>([[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<Rational>(POINTS=>$M);
 +</code>
 +From
 +
 +<code perl>
 +> 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
 +</code>
 +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//.
 +
 +<code perl>
 +> $x=new Vector<Rational>([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
 +</code>
 +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.
 +
 +<code perl>
 +> 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
 +</code>
 +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.
 +
 +<code perl>
 +> 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
 +</code>
 +There are two disjoint facets covering all the vertices. Beware the numbering of facets depends on the convex hull algorithm employed.
 +
 +<code perl>
 +> 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
 +</code>
 +Here is another polytope which is somewhat similar but not quite the same.
 +
 +<code perl>
 +> $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
 +</code>
 +Look at two facets of the five-dimensional cross polytope and their positions in the dual graph.
 +
 +<code perl>
 +> 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
 +</code>
 +Now we construct a new graph by manipulating the dual graph of the cross polytope by contracting a perfect matching.
 +
 +<code perl>
 +> $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;
 +</code>
 +The last command renumbers the nodes sequentially, starting from 0. This is necessary to render the graph a valid object.
 +
 +<code perl>
 +> print isomorphic($C->DUAL_GRAPH->ADJACENCY,$g);
 +true
 +</code>
 +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.
 +