ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 52C99 Koshevoy, Gleb, CEMI RAS, Moscow, Russia Discrete convexity and unimodularity A class K of discrete convex sets is defined as a collection of subsets of an integral lattice M = Z^{N} with the following properties: 1) ∀ A ∈ K, A = co(A) ∩ M; 2) if A ∩ B = ∅, A, B ∈ K, then there exists an integral linear functional which separates A and B; 3) ∀ A ∈ K any face of A belongs to K; 4) ∀ m ∈ M and ∀ A ∈ K, m + A ∈ K; 5) A + B ∈ K with any A, B ∈ K. We prove that a class K satisfies 1)–5) iff there is a unimodular system of vectors R such that elements of K are sets of integral points of integral polyhedra of P(R). A polyhedron P ∈ P(R) iff the affine span of each face of P is parallel to a linear span of some subset of R. For example, a class of integral polyhedra with a unimodular system A_{N} = {±e_{i}, i ∈ N, e_{i} − e_{j}, i, j ∈ N} coincides with well-known class of integral g-polymatroids.