Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety
Let R be a real closed field, P, Q subset of X-1, ... , X-k] finite subsets of polynomials, with the degrees of the polynomials in P (resp., Q) bounded by d (resp., d(0)). Let V subset of R-k be the real algebraic variety defined by the polynomials in Q and suppose that the real dimension of V is bounded by k'. We prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family P on V is bounded by [GRAPHICS] (in this form the bound was suggested by Matousek 2011). Our result improves in certain cases (when d(0) << d) the best known bound of Sigma 1 <= j <= k' ((s)(j)) 4(j) d(2d - 1)(k-1) on the same number proved in Basu et al. (Proc. Am. Math. Soc. 133( 4): 965-974, 2005) in the case d = d(0). The distinction between the bound d(0) on the degrees of the polynomials defining the variety V and the bound d on the degrees of the polynomials in P that appears in the new bound is motivated by several applications in discrete geometry (Guth and Katz in arXiv: 1011.4105v1 [math. CO], 2011; Kaplan et al. in arXiv: 1107.1077v1 [math. CO], 2011; Solymosi and Tao in arXiv: 1103.2926v2 [math. CO], 2011; Zahl in arXiv: 1104.4987v3 [math. CO], 2011).
connected components sign conditions semi-algebraic sets betti numbers