# The Reluctant Semi-Algebraist<br><br/><br/><em>Introduced by: Janos Pintz</em>

Saturday, December 1, 2012 - 9:00am - 10:00am

Keller 3-180

János Pach (Hungarian Academy of Sciences (MTA))

By Ramsey's theorem, any system of n segments in the plane

has roughly logn 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 loglogn 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 less than j less than 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 discuss some structural properties of semi-algebraically

defined graphs and hypergraphs, including Szemeredi-type partition

theorems. Finally, we mention some joint results with Conlon, Fox,

Sudakov, and Suk, establishing new Ramsey-type bounds for such

hypergraphs.

has roughly logn 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 loglogn 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 less than j less than 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 discuss some structural properties of semi-algebraically

defined graphs and hypergraphs, including Szemeredi-type partition

theorems. Finally, we mention some joint results with Conlon, Fox,

Sudakov, and Suk, establishing new Ramsey-type bounds for such

hypergraphs.

MSC Code:

05D10

Keywords: