Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
tutorial:caratheodory [2017/06/13 11:27] – added some formatting to enable automated tests oroehrig | user_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' | + | {{page> |
- | ==== 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' | ||
- | |||
- | The rows of this matrix describe a cone //C//: | ||
- | < | ||
- | polytope > $M = new Matrix< | ||
- | polytope (2)> [0, | ||
- | polytope (3)> [0, | ||
- | polytope (4)> [0, | ||
- | polytope (5)> [0, | ||
- | polytope (6)> [1, | ||
- | polytope (7)> [1, | ||
- | polytope (8)> [1, | ||
- | polytope (9)> [1, | ||
- | polytope (10)> [1, | ||
- | polytope > $C=new Polytope< | ||
- | </ | ||
- | |||
- | From | ||
- | < | ||
- | polytope > print $C-> | ||
- | 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 | ||
- | </ | ||
- | one can see that the given generators of //C// form a Hilbert basis. | ||
- | < | ||
- | polytope > $x=new Vector< | ||
- | polytope > print $C-> | ||
- | 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 | ||
- | </ | ||
- | |||
- | 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. | ||
- | < | ||
- | > foreach (all_subsets_of_k(6, | ||
- | > $B = $M-> | ||
- | > if (det($B)) { | ||
- | > print lin_solve(transpose($B), | ||
- | > } | ||
- | > } | ||
- | </ | ||
- | 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: '' | ||
- | |||
- | < | ||
- | polytope > print $C-> | ||
- | polytope > print rows_labeled($C-> | ||
- | </ | ||
- | |||
- | There are two disjoint facets covering all the vertices. Beware the numbering of facets depends on the convex hull algorithm employed. | ||
- | < | ||
- | polytope > print $C-> | ||
- | polytope > print $C-> | ||
- | </ | ||
- | |||
- | < | ||
- | polytope > print rows_labeled($M); | ||
- | </ | ||
- | |||
- | Here is another polytope which is somewhat similar but not quite the same. | ||
- | < | ||
- | polytope > $cross5=cross(5); | ||
- | polytope > print isomorphic($C, | ||
- | polytope > print isomorphic($C-> | ||
- | </ | ||
- | |||
- | < | ||
- | polytope > print $cross5-> | ||
- | </ | ||
- | Look at two facets of the five-dimensional cross polytope and their positions in the dual graph. | ||
- | < | ||
- | polytope > print $cross5-> | ||
- | polytope > print $cross5-> | ||
- | polytope > print rows_labeled($cross5-> | ||
- | </ | ||
- | |||
- | Now we construct a new graph by manipulating the dual graph of the cross polytope by contracting a perfect matching. | ||
- | < | ||
- | polytope > $g=new props:: | ||
- | polytope > $g-> | ||
- | polytope > $g-> | ||
- | polytope > $g-> | ||
- | polytope > $g-> | ||
- | polytope > $g-> | ||
- | polytope > $g-> | ||
- | </ | ||
- | The last command renumbers the nodes sequentially, | ||
- | < | ||
- | polytope > print isomorphic($C-> | ||
- | </ | ||
- | 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'' |