Given a generic m by n matrix A, a lattice point h in Z is a neighbor of the origin if the body {x : Ax < b}, with bi = max{0, aih}, i = 1, …, m, contains no lattice point other than 0 and h. The set of neighbors, N(A), is finite and Asymmetric. We show that if A’ is another matrix of the same size with the property that sign aih = sign ai’ h for every i and every h in N(A), then A’ has precisely the same set of neighbors as A. The collection of such matrices is a polyhedral cone, described by a finite set of linear inequalities, each such inequality corresponding to a generator of one of the cones Ci = pos(h in N(A) : aih < 0}. Computational experience shows that Ci has “few” generators. We demonstrate this in the first nontrivial case n = 3, m = 4.
Given a generic m x n matrix A, the simplicial complex K(A) is defined to be the collection of simplices representing maximal lattice point free convex bodies of the form {x : Ax < b}. The main result of this paper is that the topological space associated with K(A) is homeomorphic with Rm-1.
The simplicial complex K(A) is defined to be the collection of simplices, and their proper subsimplices, representing maximal lattice free bodies of the form {x : Ax < b}, with A a fixed (n + 1) × n matrix. The topological space associated with K(A) is shown to be homeomorphic to Rn, and the space obtained by identifying lattice translates of these simplices is homeomorphic to the n-torus.
The set of possible outcomes of a strongly ordinal bimatrix game is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we count the number of different Pareto optimal sets of each cardinality; we establish asymptotic bounds for the number of different convex hulls of the point sets, for the average shape of the set of points dominated by the Pareto optimal set, and for the average shape of the convex hull of the point set. We also indicate the effect of individual rationality considerations on our results. As most of our results are asymptotic, the appendix includes a careful examination of the important case of 2 x 2 games.
Given a polyhedron P subset Rn we write PI for the convex hull of the integral points in P. It is known that PI can have at most O(ϕn-1) vertices if P is a rational polyhedron with size ϕ. Here we give an example showing that PI can have as many as Ω(ϕn-1) vertices. The construction uses the Dirichlet unit theorem.
Keywords: Polyhedra; integral points, Dirichlet unit theorem