Monthly Archives: February 2013

Ann Lehman’s Sculpture Based on Herb Scarf’s Maximal Lattice Free Convex Bodies

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.

IMG_0305

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.)

photo

Herb Scarf, me , and the sculpture (picture taken by Kareen Rozen)

F ≤ 4E

1. E ≤ 3V

Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that

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 2E \ge 3F, 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 R^4. 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:

Conjecture:

4E

A weaker version which is also widely open and very interesting is:

For some absolute constant C,

C E

Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into R^{2r} then the conjecture is that

f_r(K) \le C_rf_{r-1}(K),

Where C_r is a constant depending on r.  Here f_i(K) is the number of i-dimensional faces of K. A stronger statement is that C_r= r+2. The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ’embed’ refers to a topological embedding.