SMS scnews item created by Leo Tzou at Wed 15 Jun 2016 0554
Type: Seminar
Distribution: World
Expiry: 15 Dec 2016
Calendar1: 21 Jun 2016 1400-1500
CalLoc1: RC-M032, The Red Centre, UNSW
CalTitle1: Towards a semi-algebraic combinatorics
Auth: (ltzo2369) in SMS-WASM

Colloquium: Janos Pach -- Towards a semi-algebraic combinatorics

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.