Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T05:51:20.986Z Has data issue: false hasContentIssue false
  • English
  • Français

NEIGHBORLINESS OF THE SYMMETRIC MOMENT CURVE

Part of: Polytopes and polyhedra Polynomials, rational functions General convexity

Published online by Cambridge University Press:  12 April 2012

Alexander Barvinok ,
Seung Jin Lee  and
Isabella Novik
Alexander Barvinok
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, MI 48109-1043, U.S.A. (email: [email protected])
Seung Jin Lee
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, MI 48109-1043, U.S.A. (email: [email protected])
Isabella Novik
Affiliation:
Department of Mathematics, University of Washington, Seattle, WA 98195-4350, U.S.A. (email: [email protected])
Get access

Abstract

We consider the convex hull ℬk of the symmetric moment curve Uk(t)=(cos t,sin t,cos 3t,sin 3t,…,cos (2k−1)t,sin (2k−1)t) in ℝ2k, where t ranges over the unit circle 𝕊=ℝ/2πℤ. The curve Uk(t) is locally neighborly: as long as t1,…,tk lie in an open arc of 𝕊 of a certain length ϕk>0 , the convex hull of the points Uk (t1),…,Uk (tk) is a face of ℬk. We characterize the maximum possible length ϕk, proving, in particular, that ϕk >π/2 for all k and that the limit of ϕk is π/2 as k grows. This allows us to construct centrally symmetric polytopes with a record number of faces.

MSC classification

Secondary: 52A20: Convex sets in $n$ dimensions (including convex hypersurfaces) 52B12: Special polytopes (linear programming, centrally symmetric, etc.) 26C10: Polynomials
Type
Research Article
Information
Mathematika , Volume 59 , Issue 1 , January 2013 , pp. 223 - 249
Copyright
Copyright © University College London 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Barvinok, A., A Course in Convexity (Graduate Studies in Mathematics 54), American Mathematical Society (Providence, RI, 2002).CrossRefGoogle Scholar
[2]Barvinok, A., Lee, S. J. and Novik, I., Centrally symmetric polytopes with many faces info. Israel J. Math. (to appear).Google Scholar
[3]Barvinok, A. and Novik, I., A centrally symmetric version of the cyclic polytope. Discrete Comput. Geom. 39 (2008), 76–99.CrossRefGoogle Scholar
[4]Carathéodory, C., Über den Variabilitatsbereich det Fourierschen Konstanten von Positiven harmonischen Furktionen. Rend. Circ. Mat. Palermo 32 (1911), 193–217.CrossRefGoogle Scholar
[5]Donoho, D. L., Neighborly polytopes and sparse solutions of underdetermined linear equations. Technical Report, Department of Statistics, Stanford University, 2004.Google Scholar
[6]Donoho, D. L. and Tanner, J., Counting faces of randomly projected polytopes when the projection radically lowers dimension. J. Amer. Math. Soc. 22 (2009), 1–53.CrossRefGoogle Scholar
[7]Gale, D., Neighborly and cyclic polytopes. In Convexity (Proceedings of Symposia in Pure Mathematics, 7), American Mathematical Society (Providence, RI, 1963), 225–232.CrossRefGoogle Scholar
[8]Lee, S. J., Local neighborliness of the symmetric moment curve. Preprint, 2011, arXiv:1102.5143.Google Scholar
[9]Li, M., Faces of bicyclic polytopes. Undergraduate research project, University of Washington,2007.Google Scholar
[10]Linial, N. and Novik, I., How neighborly can a centrally symmetric polytope be? Discrete Comput. Geom. 36 (2006), 273–281.CrossRefGoogle Scholar
[11]McMullen, P., The maximum numbers of faces of a convex polytope. Mathematika 17 (1970), 179–184.CrossRefGoogle Scholar
[12]Motzkin, T. S., Comonotone curves and polyhedra. Bull. Amer. Math. Soc. 63 (1957), 35.Google Scholar
[13]Rudelson, M. and Vershynin, R., Geometric approach to error-correcting codes and reconstruction of signals. Int. Math. Res. Not. IMRN 2005 (2005), 4019–4041.CrossRefGoogle Scholar
[14]Smilansky, Z., Convex hulls of generalized moment curves. Israel J. Math. 52 (1985), 115–128.CrossRefGoogle Scholar
[15]Vinzant, C., Edges of the Barvinok–Novik orbitope. Discrete Comput. Geom. 46 (2011), 479–487.CrossRefGoogle Scholar