О числе фасет 2-смежностного многогранника
Аннотация
Многогранник Р называется 2-смежностным, если любые две его вершины образуют ребро (1-грань) многогранника P. Высказывается предположение, что число fо(Р) вершин такого многогранника не превосходит числа его фасет (граней наибольшей размерности). Доказывается справедливость утверждения для случаев d < 7 и fо(Р) < d + 6, где d - размерность многогранника.
Список литературы
1. Бондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогран-никах // Дискретная математика. 2008. Т. 20, № 1. С. 64-69.
2. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. 184 с.
3. Деза М.М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.
4. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптими¬зация. М.: Наука, 1981. 344 с.
5. Aichholzer O. Extremal properties of 0/1-polytopes of dimension 5 // G. Ziegler and G. Kalai, editors, Polytopes - Combinatorics and Computation. Birkhauser, 2000. P. 111-130.
6. Avis D. lrslib Ver 4.2 is a self-contained ANSI C implementation as a callable library of the reverse search algorithm for vertex enumeration/convex hull problems: http://cgm.cs.mcgill.ca/~avis/C/lrs.html
7. Barnette D. The minimum number of vertices of a simple polytope // Israel J. Math. 1971. V. 10. P. 121-125.
8. Barnette D. A proof for the lower bound conjecture for convex polytopes // Pacific J. Math. 1973. V. 46. P. 349-354.
9. Bisztriczky T. On sewing neighbourly polytopes // Note di Matematica. 2000/2001. V. 20, № 1. P. 73--80.
10. Blind G. and Blind R. Convex polytopes without triangular faces // Isr. J. Math. 1990. V. 71. P. 129-134.
11. Gale D. Neighboring vertices on a convex polyhedron // Linear inequalities and related systems / Eds. H.W. Kuhn, A.W. Tucker. Princeton, New Jersey: Princeton University Press, 1956.
12. Henk M., Richter-Gebert J. and Ziegler G. Basic properties of convex polytopes // J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 16. Chapman & Hall/CRC Press, Boca Raton, second edition, 2004. P. 355-382.
13. Kovalev M., Maurras J.-F., Vaxes Y. On the convex hull of 3-cycles of the complete graph // Pesquisa Operacional. 2003. V. 23, № 1. P. 99-109.
14. Onn S. Geometry, Complexity, and Combinatorics of Permutation Polytopes // J. Comb. Theory, Series A. 1993. V. 64, № 1. P. 31-49.
15. Shemer I. Neighborly polytopes // Isr. J. Math. 1982. V. 43. P. 291-314.
Рецензия
Для цитирования:
Максименко А.Н. О числе фасет 2-смежностного многогранника. Моделирование и анализ информационных систем. 2010;17(1):76-82.
For citation:
On the number of facets of a 2-neighborly polytope. Modeling and Analysis of Information Systems. 2010;17(1):76-82. (In Russ.)
Просмотров: 395
Послать статью по эл. почте 