user_guide:tutorials:caratheodory

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
user_guide:tutorials:caratheodory [2019/01/25 09:27]
oroehrig ↷ Page moved from tutorial:caratheodory to user_guide:caratheodory
user_guide:tutorials:caratheodory [2019/02/11 23:09] (current)
Line 1: Line 1:
-===== A Counter-example to an integer analog to Caratheodory'​s Theorem =====+{{page>​.:​latest:​@FILEID@}}
  
-==== 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>​ 
-polytope > $M = new Matrix<​Rational>​([[0,​1,​0,​0,​0,​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>​ 
- 
-From 
-<​code>​ 
-polytope > 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>​ 
-polytope > $x=new Vector<​Rational>​([9,​13,​13,​13,​13,​13]);​ 
-polytope > 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>​ 
-> foreach (all_subsets_of_k(6,​0..9)) { 
->   $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>​ 
-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. 
  • user_guide/tutorials/caratheodory.txt
  • Last modified: 2019/02/11 23:09
  • (external edit)