user_guide:tutorials:latest:caratheodory

Differences

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

Link to this comparison view

user_guide:tutorials:latest:caratheodory [2020/01/22 09:02] (current)
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
 +1 0 2 1 1 2
 +0 1 0 0 0 0
 +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;
 +8 15 19/2 19/2 17 13 17 13 9 13 13 17 8 19/2 13 17 15 19/2 15 15 19/2 17 11 15 8 8 8
 +
 +</​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";​
 +>   }
 +> }
 +</​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);​
 +</​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];​
 +> print rows_labeled($M);​
 +</​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);​
 +> 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 perl>
 +> print $cross5->​VERTICES_IN_FACETS->​[12];​
 +> print $cross5->​VERTICES_IN_FACETS->​[13];​
 +> 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 perl>
 +> $g=new props::​Graph($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);​
 +</​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.
 +
  
  • user_guide/tutorials/latest/caratheodory.txt
  • Last modified: 2020/01/22 09:02
  • (external edit)