Till innehåll på sidan

János Pach: Semi-Algebraic Combinatorics

Tid: On 2017-06-07 kl 15.15 - 17.00

Plats: E1, Lindstedtsvägen 3, KTH

Medverkande: János Pach, EPFL, Switzerland and Rényi Institute in Budapest, Hungary

Exportera till kalender

Schedule

14:00-15:00 Prelcolloquium by Nima Amini (Room E36, Lindstedtsvägen 3, KTH)

15:15-16:15 Colloquium lecture by János Pach (Room E1 , Lindstedtsvägen 3, KTH)

16:15-17:00 SMC social get together with refreshments 

Abstract

It follows from Ramsey's theorem for graphs that any family of n segments in the plane has roughly log n members that are either pairwise disjoint or pairwise intersecting. By another well known result for hypergraphs, any set of n points in the plane has a subset of roughly log log n elements that form the vertex set of a convex polygon. However, in both cases one can prove much stronger results using ad hoc methods rather than the standard techniques of extremal combinatorics. How can we explain this curious phenomenon? It turns out that a common features of the above problems is that the underlying graphs and hypergraphs can be defined using a small number of polynomial equations or inequalities in terms of the coordinates of the segments and the points, respectively. Such "semi-algebraically" defined graphs and hypergraphs have surprisingly nice and simple structural properties. No prior knowledge in extremal combinatorics or algebra is assumed.