{
  "id": "0708.3522",
  "version": "v2",
  "published": "2007-08-27T01:31:17.000Z",
  "updated": "2008-06-24T14:04:51.000Z",
  "title": "Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials",
  "authors": [
    "Saugata Basu",
    "Dmitrii V. Pasechnik",
    "Marie-Francoise Roy"
  ],
  "comment": "23 pages, 1 figure. Shortened revised version to appear in the J. Eur. Math. Soc",
  "journal": "J. European Math. Soc. 12(2010), 529-553",
  "doi": "10.1137/070711141",
  "categories": [
    "math.AG",
    "cs.SC",
    "math.AT",
    "math.GT"
  ],
  "abstract": "Let $\\R$ be a real closed field, $ {\\mathcal Q} \\subset \\R[Y_1,...,Y_\\ell,X_1,...,X_k], $ with $ \\deg_{Y}(Q) \\leq 2, \\deg_{X}(Q) \\leq d, Q \\in {\\mathcal Q}, #({\\mathcal Q})=m,$ and $ {\\mathcal P} \\subset \\R[X_1,...,X_k] $ with $\\deg_{X}(P) \\leq d, P \\in {\\mathcal P}, #({\\mathcal P})=s$, and $S \\subset \\R^{\\ell+k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0, P \\geq 0, P \\leq 0, P \\in {\\mathcal P} \\cup {\\mathcal Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by \\[ \\ell^2 (O(s+\\ell+m)\\ell d)^{k+2m}. \\] This is a common generalization of previous results on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. We also describe an algorithm for computing the Euler-Poincar\\'e characteristic of such sets, generalizing similar algorithms known before. The complexity of the algorithm is bounded by $(\\ell s m d)^{O(m(m+k))}$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-06-24T14:04:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "14P10",
      "14P25",
      "68W30"
    ],
    "keywords": [
      "semi-algebraic sets",
      "betti numbers",
      "partly quadratic systems",
      "polynomials",
      "real closed field"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0708.3522B"
    }
  }
}