An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions
<|reference_start|>An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions: We prove an asymptotically tight bound (asymptotic with respect to the number of polynomials for fixed degrees and number of variables) on the number of semi-algebraically connected components of the realizations of all realizable sign conditions of a family of real polynomials. More precisely, we prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of a family of $s$ polynomials in $\R[X_1,...,X_k]$ whose degrees are at most $d$ is bounded by \[ \frac{(2d)^k}{k!}s^k + O(s^{k-1}). \] This improves the best upper bound known previously which was \[ {1/2}\frac{(8d)^k}{k!}s^k + O(s^{k-1}). \] The new bound matches asymptotically the lower bound obtained for families of polynomials each of which is a product of generic polynomials of degree one.<|reference_end|>
@article{basu2006an,
    title={An asymptotically tight bound on the number of semi-algebraically
  connected components of realizable sign conditions},
    author={Saugata Basu, Richard Pollack, Marie-Francoise Roy},
    journal={arXiv preprint arXiv:math/0603256},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0603256},
    primaryClass={math.CO cs.CG math.AG}
}