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.


János Pach

Research Area

EPFL, Lausanne and Renyi Institute, Budapest


Tue, 21/06/2016 - 2:00pm to 3:00pm


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