Explicit Constructions of Centrally Symmetric $$k$$ -Neighborly Polytopes and Large Strictly Antipodal Sets

Discrete & Computational Geometry - Tập 49 Số 3 - Trang 429-443 - 2013
Alexander Barvinok1, Seung Jin Lee1, Isabella Novik2
1Department of Mathematics, University of Michigan, Ann Arbor, USA
2Department of Mathematics, University of Washington, Seattle, USA

Tóm tắt

Từ khóa


Tài liệu tham khảo

Alon, N.: Explicit construction of exponential sized families of $$k$$ -independent sets. Discrete Math. 58(2), 191–193 (1986)

Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for $$k$$ -restrictions. ACM Trans. Algorithms 2(2), 153–177 (2006)

Averkov, G., Martini, H.: On reduced polytopes and antipodality. Adv. Geom. 8(4), 615–626 (2008)

Barvinok, A., Novik, I.: A centrally symmetric version of the cyclic polytope. Discrete Comput. Geom 39, 76–99 (2008)

Barvinok, A., Lee, S.J., Novik, I.: Centrally symmetric polytopes with many faces. Isr. J. Math. (2012). doi: 10.1007/s11856-012-0107-z

Barvinok, A., Lee, S.J., Novik, I.: Neighborliness of the symmetric moment curve. Mathematika 59, 223–249 (2013)

Böröczky Jr, K.: Finite packing and covering. Cambridge Tracts in Mathematics, vol. 154. Cambridge University Press, Cambridge (2004)

Danzer, L., Grünbaum, B.: Über zwei Probleme bezüglich konvexer Körper von P. Erdös und von V. L. Klee” (German). Math. Z. 79, 95–99 (1962)

Erdős, P., Füredi, Z.: The greatest angle among $$n$$ points in the $$d$$ -dimensional Euclidean space. In: Berge, C. (ed.) Combinatorial Mathematics (Marseille-Luminy, 1981). North-Holland Mathematics Studies, vol. 75, pp. 275–283. North-Holland, Amsterdam (1983)

Freiman, G., Lipkin, E., Levitin, L.: A polynomial algorithm for constructing families of $$k$$ -independent sets. Discrete Math. 70, 137–147 (1988)

Harangi, V.: Acute sets in Euclidean spaces. SIAM J. Discrete Math. 25(3), 1212–1229 (2011)

Indyk, P.: Uncertainty principles, extractors, and explicit embeddings of $$l_2$$ into $$l_1$$ . In: STOC’07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 615–620. ACM, New York (2007)

Linial, N., Novik, I.: How neighborly can a centrally symmetric polytope be? Discrete Comput. Geom 36, 273–281 (2006)

Makai, E., Jr., Martini, H.: On the number of antipodal or strictly antipodal pairs of points in finite subsets of $${ {R}}^d$$ . In: Gritzmann, P., Sturmfels, B. (eds.) Applied Geometry and Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 457–470. American Mathematical Society, Providence, RI (1991)

Martini, H., Soltan, V.: Antipodality properties of finite sets in Euclidean space. Discrete Math. 290(2–3), 221–228 (2005)

McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17, 179–184 (1970)

Rudelson, M., Vershynin, R.: Geometric approach to error correcting codes and reconstruction of signals. Int. Math. Res. Notices 64, 4019–4041 (2005)

Smilansky, Z.: Convex hulls of generalized moment curves. Isr. J. Math. 52, 115–128 (1985)