Geometric combinatorics, graphs and hypergraphs

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