Campuses:

Combinatorial complexity in o-minimal geometry

Wednesday, April 11, 2007 - 11:15am - 12:15pm
Keller 3-180
Saugata Basu (Georgia Institute of Technology)
We prove tight bounds on the combinatorial and topological complexity of sets defined in terms of n definable sets belonging to some fixed definable family of sets in an o-minimal structure. This generalizes the combinatorial parts of similar bounds known in the case of semi-algebraic and semi-Pfaffian sets, and as a result vastly increases the applicability of results on combinatorial and topological complexity of arrangements studied in discrete and computational geometry. As a sample application, we extend a Ramsey-type theorem due to Alon et al. originally proved for semi-algebraic sets of fixed description complexity to this more general setting. The talk will be self-contained and I will go over the basic definitions of o-minimality for those who are unfamiliar with the notion.