János Pach
Abstract:
By Ramsey's theorem, any system of n segments in the plane has roughly log n members that are either pairwise disjoint or pairwise intersecting. Analogously, any set of n points p(1),..., p(n) in the plane has a subset of roughly loglog n elements with the property that the orientation of p(i)p(j)p(k) is the same for all triples from this subset with i<j<k. (The elements of such a subset form the vertex set of a convex polygon.) However, in both cases we know that there exist
much larger "homogeneous" subsystems satisfying the above conditions. What is behind this favorable behavior? One of the common features of the above problems is that the underlying graphs and triple-systems
can be defined by a small number of polynomial equations and inequalities in terms of the coordinates of the segments and points. We show that "semi-algebraically" defined graphs and hypergraphs obey much nicer and stronger combinatorial theorems than general ones.
Speaker
Research Area
Affiliation
EPFL, Lausanne and Renyi Institute, Budapest
Date
Tue, 21/06/2016 - 2:00pm to 3:00pm
Venue
RC-M032, The Red Centre, UNSW
About the Speaker:
Prof. Pach has been affiliated with the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences since 1977. In 2008, he joined École Polytechnique Fédérale de Lausanne as Professor of Mathematics. He received numerous awards, including the Grünwald Medal of the János Bolyai Mathematical Society (1982), the Ford Award from the Mathematical Association of America (1990), and the Alfréd Rényi Prize from the Hungarian Academy of Sciences (1992). He became a fellow of the American Mathematical Society in 2015. See his wikipedia page for more information