Geometric combinatorics, graphs and hypergraphs

Series
Other Talks
Time
Monday, February 25, 2013 - 11:05am for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Gil Kalai – Hebrew University and Yale University
Organizer
Prasad Tetali
In the lecture I will describe how several questions in geometric combinatorics translate into questions about graphs and hypergraphs. 1. Borsuk's problem. 2. Tverberg theorem and Tverberg's type problems. Tverberg's theorem asserts that (r-1)(d+1)+1 points in d-space can be divided into r parts whose convex hull intersect. I will discuss situations where less points admit such a partition and connections with graph theory. (For more background, look at this MO question Tverberg partitions with less than (r-1)(d+1)+1 points<http://mathoverflow.net/questions/88718/tverberg-partitions-with-less-than-r-1d11-points> ) 3. Helly type theorems and conditions on induced subgraphs and sub-hypergraphs. I will explain the origin to the following conjecture of Meshulam and me: There is an absolute upper bound for the chromatic number of graphs with no induced cycles of length divisible by 3. 4. Embedding of 2-dimensional complexes and high dimensional minors. I will discuss the following conjecture: A 2-dimensional simplicial complex with E edges and F 2-dimensional faces that can be embedded into 4-space satisfies F < 4e. (For more background see my post *F ≤ 4E*<http://gilkalai.wordpress.com/2013/02/01/f-4e/> )