KAIST Discrete Math Seminar

A result due to Gyárfás, Hubenko, and Solymosi, answering a question of Erdős, asserts that if a graph G does not contain K_2,2 as an induced subgraph yet has at least c n(n-1)/2 edges, then G has a complete subgraph on at least c^2 n /10 vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced K_2,2, which allows us to extend their result to k-uniform hypergraphs. Our result also has interesting consequences in topological combinatorics and abstract convexity, where it can be used to answer questions by Bukh, Kalai, and several others.

We will give a topological generalization of the planar (p,q) theorem due to Alon and Kleitman. In particular we will show that the assertion of the (p,q) theorem holds for families of open connected sets in the plane under the hypothesis that the intersection of any subfamily is empty or connected. The proof is based on a surprising connection between nerve complexes and complete minors in graphs. This is join work with Minki Kim and Seunghun Lee.

Very recently, Andrew Suk made a major breakthrough on the Erdos-Szekeres convex polygon problem, in which he solves asymptotically this 80 year old problem of determining the minimum number of points in the plane in general position that always guarantees n points in convex position. I will review his proof in full detail.

Around 15 years ago, Aharoni and Haxell gave a wonderful generalization of Hall’s marriage theorem. Their proof introduced topological methods in matching theory which were further developed by Berger, Meshulam, and others. Recently, motivated by some geometric questions, we extended these methods further, and in this talk I’ll explain the ideas and some of our results.

In 1935 Erdős and Szekeres showed that every “sufficiently large” set of points in general position in the plane contains a “large” subset which is in convex position. Since then many mathematicians have tried to determine good bounds for “sufficiently large” in  terms of “large”, as well as given numerous generalizations and refinements. In this talk I will survey this famous problem and extend it to a natural object which we call generalized wiring diagram. This unifies several proposed generalizations, and as a result we will settle several conjectures in this area. This is joint work with Michael Dobbins and Alfredo Hubard.