×

Representing simple \(d\)-dimensional polytopes by \(d\) polynomials. (English) Zbl 1210.52007

Each \(d\)-dimensional convex polytope \(P\) with \(m\) facets can be represented by minimal \(m\) linear inequalities. A generalization of such a H-representation of \(P\) is the representation of \(P\) as the set \(P=\{x\in\mathbb{R}^d: p(x)\geq 0 \wedge p\in {\mathcal P}\}\) where \(\mathcal{P}\) is a finite set of polynomials of \(d\) variables. Let \(s(d,P)\) denote the least cardinality of \(\mathcal{P}\) representing \(P\). H. Bosse, M. Grötschel and the second author [Math. Program. 103, No. 1 (A), 35–44 (2005; Zbl 1140.90528)] have conjectured that \(s(d,P)=d\) for \(d\)-polytopes. In the present paper the authors prove this conjecture for the class of simple \(d\)-polytopes \(P\) (every vertex of \(P\) is contained in exactly \(d\) facets). The essence of the proof is the explicit construction of \(d\) polynomials which represent a given \(d\)-polytope.
Reviewer: Eike Hertel (Jena)

MSC:

52B11 \(n\)-dimensional polytopes
52B12 Special polytopes (linear programming, centrally symmetric, etc.)

Citations:

Zbl 1140.90528

Software:

SINGULAR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andradas C., Bröcker L., Ruiz J.M.: Constructible sets in real geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 33. Springer, Berlin (1996) MR 98e:14056 · Zbl 0873.14044
[2] Averkov, G., Henk, M.: Three-dimensional polyhedra can be described by three polynomial inequalities, 23 pp. arXiv:0807.2137 (2008) · Zbl 1183.52009
[3] Averkov, G.: Representing elementary semi-algebraic sets by a few polynomial inequalities: a constructive approach, 14 pp. arXiv:0804.2134 (2008)
[4] Bădescu L.: Algebraic surfaces, Universitext. Springer, New York (2001). MR 2001k:14068
[5] Bochnak J., Coste M., Roy M.-F.: Real Algebraic Geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol 36. Springer, Berlin (1998) MR 2000a:14067 · Zbl 0912.14023
[6] Bernig, A.: Constructions for the theorem of Bröcker and Scheiderer, 48 pp. Diploma thesis, Universities Rennes and Dortmund (1998)
[7] Bosse H., Grötschel M., Henk M.: Polynomial inequalities representing polyhedra. Math. Program. 103(1A), 35–44 (2005) MR 2006k:52018 · Zbl 1140.90528
[8] Burési J., Mahé L.: Reducing inequalities with bounds. Math. Z. 227(2), 231–243 (1998) MR 98j:14073 · Zbl 0906.14024
[9] Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006). MR 2007b:14125 · Zbl 1102.14041
[10] Bröcker L.: Minimale Erzeugung von Positivbereichen, Geom. Dedicata 16(3), 335–350 (1984) MR 86c:11024 · Zbl 0546.14016
[11] Bröcker L.: On basic semialgebraic sets. Exposition. Math. 9(4), 289–334 (1991) MR 93b:14085 · Zbl 0783.14035
[12] Bröcker, L.: Private communication (2008)
[13] Barvinok, A.I., Vershik, A.M.: Polynomially computable approximation of families of semi-algebraic sets, and combinatorial complexity. Trudy Leningrad. Mat. Obshch. 1, 8–26, 245 (1990). MR 92f:14065
[14] Barvinok A., Veomett A.: The computational complexity of convex bodies. Surv. Discrete Comput. Geom. Contemp. Math. 453, 117–137 (2008) · Zbl 1145.52002
[15] Firey W.J.: Approximating convex bodies by algebraic ones. Arch. Math. (Basel) 25, 424–425 (1974) MR 50 #5632 · Zbl 0294.52003
[16] Grötschel M., Henk M.: The representation of polyhedra by polynomial inequalities. Discrete Comput. Geom. 29(4), 485–504 (2003) MR 2004b:14098 · Zbl 1128.14308
[17] Greuel G.-M., Pfister G.: A singular Introduction to Commutative Algebra. Springer, Berlin (2002) MR 2003k:13001 · Zbl 1023.13001
[18] Hammer P.C.: Approximation of convex surfaces by algebraic surfaces. Mathematika 10, 64–71 (1963) MR 27 #4135 · Zbl 0122.41004
[19] Handelman D.: Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132(1), 35–62 (1988) MR 90e:52005 · Zbl 0659.52002
[20] Henk M.: Polynomdarstellungen von Polyedern. Jber. Deutsch. Math.-Verein. 109(2), 51–69 (2007) · Zbl 1135.52004
[21] Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988, Reprint of the 1952 edition. MR 89d:26016
[22] Lancaster P.: Theory of matrices. Academic Press, New York (1969) MR 39 #6885 · Zbl 0186.05301
[23] Mahé L.: Une démonstration élémentaire du théorème de Bröcker-Scheiderer. C. R. Acad. Sci. Paris Sér. I Math. 309(9), 613–616 (1989) MR 91h:14057
[24] Powers, V., Reznick, B.: A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Algebra 164(1–2), 221–229 (2001). Effective methods in algebraic geometry (Bath, 2000). MR 2002g:14087
[25] Scheiderer C.: Stability index of real varieties. Invent. Math. 97(3), 467–483 (1989) MR 90g:14011 · Zbl 0715.14049
[26] Schneider R.: Convex Bodies: The Brunn–Minkowski Theory, Encyclopedia of Mathematics and its Applications, vol. 44. Cambridge University Press, Cambridge (1993) MR 94d:52007 · Zbl 0798.52001
[27] vom Hofe, G.: Beschreibung von ebenen konvexen n-Ecken durch höchstens drei algebraische Uungleichungen, PhD thesis, University of Dortmund, (1992) · Zbl 0850.52001
[28] Zariski O.: Algebraic surfaces, Classics in Mathematics. Springer, Berlin (1995) MR 96c:14024 · Zbl 0845.14021
[29] Zhan X.: Matrix Inequalities, Lecture Notes in Mathematics, vol. 1790. Springer, Berlin (2002) MR 2003h:15030
[30] Ziegler G.M.: Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152. Springer, New York (1995) MR 96a:52011 · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.