Posts Tagged ‘EdwardKim’

KAIST Discrete Geometry Day 2012

Wednesday, January 25th, 2012
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
Arseniy Akopyan (Institute for Information Transmission Problems)
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
Roman Karasev (Moscow Institute of Physics and Technology)
It is proved that if we partition a d-dimensional cube into nd 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)=nd-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
Edward D. Kim (POSTECH)
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.

Edward D. Kim, On Diameters of Transportation and Network Flow Polytopes

Thursday, September 15th, 2011
On Diameters of Transportation and Network Flow Polytopes
Edward D. Kim
Department of Mathematics, POSTECH, Pohang
2011/10/14 Fri 4PM-5PM
Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos. To conclude, we discuss avenues for future work on transportation polytopes and their diameters.