Type: Seminar

Distribution: World

Expiry: 15 Dec 2016

CalTitle1: Towards a semi-algebraic combinatorics

Auth: leo@swgc.sizeit.se (ltzo2369) in SMS-WASM

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.