Geometric combinatorics, graphs and hypergraphs

Series: 
Other Talks
Monday, February 25, 2013 - 11:05
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Hebrew University and Yale University
Organizer: 
  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/> )