KAIST Discrete Geometry Day 2012

2012/2/1 Wed (Room: 3433, Building E6-1)

Poster (KAIST Discrete Geometry Day 2012)

List of speakers

- 10AM-11:50AM Michael Dobbins: Universality for families of non-crossing convex sets
- 11:00AM-11:50AM Arseniy Akopyan: Kadets type theorems for partitions of a convex body
- 3PM-3:50PM Roman Karasev: An analogue of Gromov’s waist theorem for coloring the cube
- 4PM-4:50PM Edward D. Kim: Lattice paths and Lagrangian matroids
- 5PM-5:50PM Alfredo Hubard: Space crossing numbers

Universality for families of non-crossing convex sets

Michael Dobbins (KAIST)

Mnev’s Universality theorem gives a construction showing that for any primary semialgebraic set, there is a family of points in the plane of fixed combinatorial type given by an oriented matroid such that the realization space of the family is homotopic to the semialgebraic set. Analogous universality results have also been shown for polytopes. Recently, we have found that the realization spaces of families of non-crossing convex sets in the plane with fixed combinatorial type are contractible, but that universality holds for families of non-crossing convex polygons with a bounded number of vertices.

Kadets type theorems for partitions of a convex body

For convex partitions of a convex body B we try to put a homothetic copy of B into each set of the partition so that the sum of homothety coefficients is greater or equal 1. In the plane this can be done for arbitrary partition, while in higher dimensions we need certain restrictions on the partition.

An analogue of Gromov’s waist theorem for coloring the cube

It is proved that if we partition a d-dimensional cube into n^{d} small cubes and color the small cubes into m+1 colors then there

exists a monochromatic connected component consisting of at least f(d, m)=n^{d-m} small cubes. The constant f(d,m) in our present approach looks quite ugly. In particular cases m=d-1 the question (and the answer) goes back to Lebesgue, the case m=1 was examined by Matousek and Privuetivy. They also conjectured the general case with other m. The same question was posed in informal discussions in Moscow by Alexey-Kanel-Belov. The proof will be based on (widely understood) Gromov’s method of contraction in the space of cycles. A different independent proof of a stronger fact was found by Marsel-Matdinov. Certain unsolved problems remain in this area. For example, Gromov’s question about extending the sphere waist theorem for maps into polyhedra which are not manifolds with bound depending only on the dimension.

Lattice paths and Lagrangian matroids

We investigate lattice path Lagrangian matroids, a family of Lagrangian matroids introduced by Joe Bonin and Anna de Mier. One definition for Lagrangian matroids involves a construction of ordinary matroids. We discuss the corresponding relationship holds between lattice path Lagrangian matroids and lattice path matroids, proving one direction of a conjecture by de Mier relating lattice path Lagrangian matroids and lattice path matroids.

Space Crossing Numbers

We define a higher dimensional geometric analogue of the the crossing number of graph theory. The basic idea comes from the theory of line transversals and the Tverberg-Vrecica conjecture. Namely, we think of a crossing as a transversal 0-flat to a pair of edges or faces, and define space crossing as a transversal k-flat to a number of edges or faces. We obtain an almost tight space crossing number inequality that implies the classical crossing number inequality (up to a logaritmic factor). Joint work with Boris Bukh.