MIT Combinatorics Seminar

The Convex Dimension Of A Graph

Nir Halman (MIT)
Email: halman@mit.edu

Wednesday, April 5, 2006   4:30 pm    Room 2-105


The convex dimension of a graph $G=(V,E)$ is the smallest dimension d for which G admits an embedding $f:V \rightarrow R^d$ of its vertices into $d$-space, such that the barycenters of the images of its edges are in convex position. We say that $d$ is the strong convex dimension of $G$ if the above condition is augmented with the requirement that the image of the vertices of $G$ are in convex position. The convex and strong convex dimensions of graphs arise naturally in connection with a special class of convex combinatorial optimization problems. In this talk we will study the convex and strong convex dimensions and the extremal number of edges of graphs with given convex dimension.

Joint work with Shmuel Onn (Technion) and Uriel G. Rothblum (Technion).