## Computing all lex-positive bases representing a given vertex

For details about lrs options visit:   http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html

sony% cat cross4.ine
cross
H-representation

begin
16 5 rational
1  -1  1  1  1
1  -1  -1  1  1
1  -1  1  -1  1
1  -1  -1  -1  1
1  -1  1  1  -1
1  -1  -1  1  -1
1  -1  1  -1  -1
1  -1  -1  -1  -1
1  1  1  1  1
1  1  -1  1  1
1  1  1  -1  1
1  1  -1  -1  1
1  1  1  1  -1
1  1  -1  1  -1
1  1  1  -1  -1
1  1  -1  -1  -1
end

If you run lrs on this file you see that it is degenerate with each of its 8 vertices having 6 lex-pos bases.

1. We select vertex   0 1 0 0 and ask for all lex-pos bases that contain it.
It is contained on 8 facets in the file cross4.ine: all of the facets with a +1 in column 3.
Add the normals of these facets together to get an objective function z= 8 x2  that maximizes at 0 1 0 0.

2. Now run lrs in linear programming mode to get a lex-pos basis for the vertex 0 1 0 0.
To do this add the following 3 lines to the end of cross4.ine

maximize 0 0 8 0 0
lponly
printcobasis 1

Running lrs we get:

sony% lrs cross4.ine

*lrs:lrslib v.4.2c, 2010.7.7(32bit,lrsmp.h)
*Copyright (C) 1995,2010, David Avis   avis@cs.mcgill.ca
*Input taken from file cross4.ine
cross
*maximize:   0  0  8  0  0
*printcobasis 1
V#1 R#0 B#1 h=0 facets  8 10 12 14 I#8 det= 8  in_det= 8
1  0  1  0  0
*LP solution only requested

3. We now use the cobasis  8 10 12 14 to do an lrs run on cross4.ine with the truncate option.
Replace the three options for the lp only run with:

startingcobasis 8 10 12 14
allbases
printcobasis 1
truncate

Run lrs and you get the following output:
sony% lrs cross4.ine
*truncate
V-representation
begin
***** 5 rational
V#1 R#0 B#1 h=0 facets  8 10 12 14 I#8 det= 8  in_det= 8
1  0  1  0  0
V#2 R#0 B#2 h=1 facets  8 12 14 16 I#8 det= 8  in_det= 8
1  0  1  0  0
V#3 R#0 B#3 h=2 facets  8 12 15 16 I#8 det= 8  in_det= 8
1  0  0  1  0
V#4 R#0 B#4 h=2 facets  12 14 15 16 I#8 det= 8  in_det= 8
1 -1  0  0  0
V#5 R#0 B#5 h=2 facets  8 14 15 16 I#8 det= 8  in_det= 8
1  0  0  0  1
V#6 R#0 B#6 h=1 facets  4 8 10 12 I#8 det= 8  in_det= 8
1  0  1  0  0
V#7 R#0 B#7 h=1 facets  10 12 14 15 I#8 det= 8  in_det= 8
1 -1  0  0  0
V#8 R#0 B#8 h=1 facets  6 8 10 14 I#8 det= 8  in_det= 8
1  0  1  0  0
V#9 R#0 B#9 h=2 facets  4 6 8 10 I#8 det= 8  in_det= 8
1  0  1  0  0
V#10 R#0 B#10 h=3 facets  2 4 6 10 I#8 det= 8  in_det= 8
1  0  1  0  0
end
*Tree truncated at each new vertex
*Totals: vertices=10 rays=0 bases=10 integer_vertices=4

4. You obtain a list of the 6 lex-pos cobases that represent 0 1 0 0 and also 4 other cobases that you simply discard.
The reverse search tree corresponding to step 3 is below.
To see how it is constructed, note it is a depth first search tree based on the height parameter h=integer in the above output.
Note that their are 6 vertices adjacent to 0 1 0 0 on the polytope of which 3 are computed, and one, (-1,0,0,0) appears twice.
So this is not equivalent to computing the vertex figure at 0 1 0 0.

To understand this tree, it is useful to compute all lex-pos bases of the polytope by running step 3 with 'truncate' removed.
In the full reverse search tree containing 48 notes, we see that the cobases 4 8 10 12  and 2 4 6 10 are leaves of the tree, so no truncation is performed.
The remaining 38 nodes of the tree are all in subtrees of the truncated vertices. The maximum depth is 8.
(If anyone cares to draw this tree and send it to me, I am happy to post it :-)  )