Mathematics – Combinatorics
Scientific paper
2006-03-10
Mathematics
Combinatorics
19 pages. Bibliography has been updated and a few more references have been added. This is the final version of this paper whi
Scientific paper
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.
Basu Saugata
Pollack Richard
Roy Marie-Françoise
No associations
LandOfFree
An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-114809