Maximal lattice-free convex bodies introduced by Herb Scarf and the related complex of maximal lattice free simplices (also known as the Scarf complex) are remarkable geometric constructions with deep connections to combinatorics, convex geometry, integer programming, game theory, fixed point computations, algebraic geometry, and economics. It is certainly an object I would like to think more and tell you more about. Here is a sculpture made by artist Ann Lehman based on such a body generated by a certain 4 by 3 matrix.
Ann Lehman: A sculpture based on a maximal lattice free convex body (photograph taken by the sculptress).
The body described in this sculpture is topologically a (two dimensional) disk, triangulated in a specific way. The boundary is a polygon embedded in 3-space consist of 21 “blue” edges. The “black” edges are internal edges of the triangulation. The triangles of the triangulation are not part of the sculpture but it is easy to figure out what they are and the shape has a remarkable zigzag nature. All vertices are integral. The only interior integral point is in “red”. (The “green” point is the origin, it is not in the body.)
Herb Scarf, me , and the sculpture (picture taken by Kareen Rozen)
1. E ≤ 3V
Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that
E ≤ 3V
In fact, we have (when V is at least 3,) that E ≤ 3V – 6.
To see this, denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that
E – V + F = 2
V – E + F = 2
and now note that every face must have at least three edges and every edge is contained in two faces and therefore , so 6=3V – 3E + 3F ≤ 3V – 3E +2E.
2. F ≤ 4E
Now let K be a two-dimensional simplicial complex and suppose that K can be embedded in . Denote by E the number of edges of K and by F the number of 2-faces of K.
Here is a really great conjecture:
F ≤ 4E
A weaker version which is also widely open and very interesting is:
For some absolute constant C,
F ≤ C E
Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into then the conjecture is that
Where is a constant depending on r. Here is the number of i-dimensional faces of K. A stronger statement is that . The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ’embed’ refers to a topological embedding.