FYI (KMRS Seminar)
Random points and lattice points in convex bodies
Imre Barany
Hungarian Academy of Sciences & University College London
Hungarian Academy of Sciences & University College London
2014/08/25-08/26 Monday & Tuesday
4:00PM – 5:00PM Room 1409
4:00PM – 5:00PM Room 1409
Assume K is a convex body in R^d and X is a (large) finite subset of K. How many convex polytopes are there whose vertices belong toX? Is there a typical shape of such polytopes? How well does the maximal such polytope (which is actually the convex hull of X) approximate K? In this lecture I will talk about these questions mainly in two cases. The first is when X is a random sample of n uniform, independent points from K. In this case motivation comes from Sylvester’s famous four-point problem and from the theory of random polytopes. The second case is when X is the set of lattice points contained in K and the questions come from integer programming and geometry of numbers. Surprisingly (or not so surprisingly), the answers in the two cases are rather similar. The methods are, however, very different.
of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that 
, and 
if and only if G contains 
. Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and 
if and only if G contains 
. They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that 
if and only if G contains 
. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither 
(a