Differences

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

--- tutorial:caratheodory [2010/08/10 10:39] – joswig
+++ tutorial:caratheodory [2017/06/13 11:27] – added some formatting to enable automated tests oroehrig
@@ Line 1: / Line 1: @@
-===== A Counter-example to an integer analogue to Caratheodory's Theorem =====
+===== 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:
@@ Line 6: / Line 8: @@
 The rows of this matrix describe a cone //C//:
 <code>
-polytope > $M=new
+polytope > $M = new Matrix<Rational>([[0,1,0,0,0,0],
-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]]);
+polytope (2)> [0,0,1,0,0,0],
+polytope (3)> [0,0,0,1,0,0],
+polytope (4)> [0,0,0,0,1,0],
+polytope (5)> [0,0,0,0,0,1],
+polytope (6)> [1,0,2,1,1,2],
+polytope (7)> [1,2,0,2,1,1],
+polytope (8)> [1,1,2,0,2,1],
+polytope (9)> [1,1,1,2,0,2],
+polytope (10)> [1,2,1,1,2,0]]);
 polytope > $C=new Polytope<Rational>(POINTS=>$M);
 </code>
@@ Line 34: / Line 44: @@
 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>
-foreach (all_subsets_of_k(6,0..9)) {
+> foreach (all_subsets_of_k(6,0..9)) {
-  $B=$M->minor($_,All);
+>   $B = $M->minor($_,All);
-  if (det($B)) {
+>   if (det($B)) {
-    print lin_solve(transpose($B),$x), "\n";
+>     print lin_solve(transpose($B),$x), "\n";
-  }
+>   }
-}
+> }
 </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>
+polytope > print $C->N_VERTICES, " ", $C->DIM;
+polytope > print rows_labeled($C->VERTICES_IN_FACETS);
+</code>
+There are two disjoint facets covering all the vertices. Beware the numbering of facets depends on the convex hull algorithm employed.
+<code>
+polytope > print $C->VERTICES_IN_FACETS->[8];
+polytope > print $C->VERTICES_IN_FACETS->[22];
+</code>
+<code>
+polytope > print rows_labeled($M);
+</code>
+Here is another polytope which is somewhat similar but not quite the same.
+<code>
+polytope > $cross5=cross(5);
+polytope > print isomorphic($C,$cross5);
+polytope > print isomorphic($C->GRAPH->ADJACENCY,$cross5->GRAPH->ADJACENCY);
+</code>
+<code>
+polytope > print $cross5->F_VECTOR - $C->F_VECTOR;
+</code>
+Look at two facets of the five-dimensional cross polytope and their positions in the dual graph.
+<code>
+polytope > print $cross5->VERTICES_IN_FACETS->[12];
+polytope > print $cross5->VERTICES_IN_FACETS->[13];
+polytope > print rows_labeled($cross5->DUAL_GRAPH->ADJACENCY);
+</code>
+Now we construct a new graph by manipulating the dual graph of the cross polytope by contracting a perfect matching.
+<code>
+polytope > $g=new props::Graph($cross5->DUAL_GRAPH->ADJACENCY);
+polytope > $g->contract_edge(12,13);
+polytope > $g->contract_edge(24,26);
+polytope > $g->contract_edge(17,21);
+polytope > $g->contract_edge(3,11);
+polytope > $g->contract_edge(6,22);
+polytope > $g->squeeze;
+</code>
+The last command renumbers the nodes sequentially, starting from 0.  This is necessary to render the graph a valid object.
+<code>
+polytope > print isomorphic($C->DUAL_GRAPH->ADJACENCY,$g);
+</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.