Premium
Combinatorial complexity in o‐minimal geometry
Author(s) -
Basu Saugata
Publication year - 2010
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/pdp031
Subject(s) - mathematics , pfaffian , discrete geometry , combinatorics , algebraic number , discrete mathematics , topological complexity , pure mathematics , mathematical analysis
In this paper 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. [Crossing patterns of semi‐algebraic sets, J. Combin. Theory Ser. A 111 (2005), 310–326. MR 2156215 (2006k:14108)], originally proved for semi‐algebraic sets of fixed description complexity to this more general setting.