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:caratheodory [2019/01/25 09:27] – ↷ Page moved from tutorial:caratheodory to user_guide:caratheodory oroehriguser_guide:tutorials:caratheodory [2019/02/11 23:09] (current) – external edit 127.0.0.1
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
  • by 127.0.0.1