maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1022Research ArticleОригинальные статьиArticlesО числе фасет 2-смежностного многогранникаOn the number of facets of a 2-neighborly polytopeМаксименкоА. Н.maksimenko_a_n@mail.ruЯрославский государственный университет им. П.Г. ДемидоваRussian Federation2010200320101717682Copyright © Максименко А.Н., 20102010Максименко А.Н.Максименко А.Н.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1022

Многогранник Р называется 2-смежностным, если любые две его вершины образуют ребро (1-грань) многогранника P. Высказывается предположение, что число fо(Р) вершин такого многогранника не превосходит числа его фасет (граней наибольшей размерности). Доказывается справедливость утверждения для случаев d < 7 и fо(Р) < d + 6, где d - размерность многогранника.

A d-polytope P is 2-neighborly if each 2 vertices of P determine an edge. It is conjectured that the number f0(P) of vertices for such polytope does not exceed the number fd-1(P) of facets. The conjecture is separately proved for d < 7 and for f0(P) < d+6.

2-смежностные многогранникичисло фасет2-neighborly polytopesnumber of facetsReferencesБондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогран-никах // Дискретная математика. 2008. Т. 20, № 1. С. 64-69.Бондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогран-никах // Дискретная математика. 2008. Т. 20, № 1. С. 64-69.Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. 184 с.Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. 184 с.Деза М.М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.Деза М.М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптими¬зация. М.: Наука, 1981. 344 с.Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптими¬зация. М.: Наука, 1981. 344 с.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.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.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.htmlAvis 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.htmlBarnette D. The minimum number of vertices of a simple polytope // Israel J. Math. 1971. V. 10. P. 121-125.Barnette D. The minimum number of vertices of a simple polytope // Israel J. Math. 1971. V. 10. P. 121-125.Barnette D. A proof for the lower bound conjecture for convex polytopes // Pacific J. Math. 1973. V. 46. P. 349-354.Barnette D. A proof for the lower bound conjecture for convex polytopes // Pacific J. Math. 1973. V. 46. P. 349-354.Bisztriczky T. On sewing neighbourly polytopes // Note di Matematica. 2000/2001. V. 20, № 1. P. 73--80.Bisztriczky T. On sewing neighbourly polytopes // Note di Matematica. 2000/2001. V. 20, № 1. P. 73--80.Blind G. and Blind R. Convex polytopes without triangular faces // Isr. J. Math. 1990. V. 71. P. 129-134.Blind G. and Blind R. Convex polytopes without triangular faces // Isr. J. Math. 1990. V. 71. P. 129-134.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.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.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.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.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.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.Onn S. Geometry, Complexity, and Combinatorics of Permutation Polytopes // J. Comb. Theory, Series A. 1993. V. 64, № 1. P. 31-49.Onn S. Geometry, Complexity, and Combinatorics of Permutation Polytopes // J. Comb. Theory, Series A. 1993. V. 64, № 1. P. 31-49.Shemer I. Neighborly polytopes // Isr. J. Math. 1982. V. 43. P. 291-314.Shemer I. Neighborly polytopes // Isr. J. Math. 1982. V. 43. P. 291-314.

The authors declare that there are no conflicts of interest present.