КОНСТРУКТИВНЫЕ НИЖНИЕ ОЦЕНКИ ЧИСЕЛ НЕЗАВИСИМОСТИ ДИСТАНЦИОННЫХ ГРАФОВ С ВЕРШИНАМИ В {-1, 0, 1}n

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Представлены новые конструктивные нижние оценки чисел независимости для дистанционных графов с вершинами в {-1, 0, 1}n. Получены асимптотически значимые нижние границы, действующие в широком диапазоне параметров. Численные расчеты демонстрируют соотношения между полученными результатами и известными верхними оценками.

Об авторах

А. П Ахняров

Московский физико-технический институт (национальный исследовательский университет)

Email: akhiiarov.ar@phystech.edu

А. В Бобу

Criteo S.A.

Email: a.v.bobu@gmail.com
Париж, Франция

А. М Райгородский

Московский физико-технический институт (национальный исследовательский университет); МГУ им. М.В. Ломоносова, механико-математический факультет; Кавказский математический центр Адмесинского государственного университета; Бурлянский государственный университет, институт математики и информатики

Email: mraigor@yandex.ru
кафедра дискретной математики и лаборатории профилирующей комбинаторики и сетевых приложений; кафедра математической статистики и случайных процессов

Список литературы

  1. Hadwiger H. Ein ¨Uberdeckungssatz f¨ur den euklidischen Raum // Portugal. Math. 1944. V. 4. P. 140–144.
  2. Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств // УМН. 2001. Т. 56. №1 (337). С. 107–146. https://doi.org/10.4213/rm358
  3. Brass P., Moser W., Pach J. Research Problems in Discrete Geometry. Berlin: Springer, 2005. https://doi.org/10.1007/0-387-29929-7
  4. Soifer A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2009. https://doi.org/10.1007/978-0-387-74642-5
  5. Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory. New York: Springer, 2013. P. 429–460. https://doi.org/10.1007/978-1-4614-0110-0_23
  6. Raigorodskii A.M. Cliques and Cycles in Distance Graphs and Graphs of Diameters // Discrete Geometry and Algebraic Combinatorics (AMS Special Session on Discrete Geometry and Algebraic Combinatorics. San Diego, CA, USA. Jan. 11, 2013). Contemp. Math., V. 625. Providence, RI: Amer. Math. Soc., 2014. P. 93–109.
  7. de Grey A.D.N.J. The Chromatic Number of the Plane Is at Least 5 // Geombinatorics. 2018. V. 28. № 1. P. 18–31.
  8. Exoo G., Ismailescu D. The Chromatic Number of the Plane Is at Least 5: A New Proof // Discrete Comput. Geom. 2020. V. 64. № 1. P. 216–226. https://doi.org/10.1007/s00454-019-00058-1
  9. Cherkashin D., Kulikov A., Raigorodskii A. On the Chromatic Numbers of Small-Dimensional Euclidean Spaces // Discrete Appl. Math. 2018. V. 243. P. 125–131. https://doi.org/10.1016/j.dam.2018.02.005
  10. Arman A., Bondarenko A., Prymak A., Radchenko D. Upper Bounds on Chromatic Number of En in Low Dimensions // Electron. J. Combin. 2024. V. 31. №2. Paper No. P2.35 (20 pp.). https://doi.org/10.37236/11794
  11. Larman D.G., Rogers C.A. The Realization of Distances within Sets in Euclidean Space // Mathematika. 1972. V. 19. № 1. P. 1–24. https://doi.org/10.1112/S0025579300004903
  12. Prosanov R. A New Proof of the Larman–Rogers Upper Bound for the Chromatic Number of the Euclidean Space // Discrete Appl. Math. 2020. V. 276. P. 115–120. https://doi.org/10.1016/j.dam.2019.05.020
  13. Nagy Z. A Certain Constructive Estimate of the Ramsey Number // Mat. Lapok. 1972. V. 23. P. 301–302.
  14. Erd˝os P. Problems and Results in Graph Theory and Combinatorial Analysis // Proc. 5th British Combinatorial Conf. (Univ. Aberdeen, Aberdeen, 1975). Congress. Numer. No. XV. Winnipeg, MB: Utilitas Math., 1976. P. 169–192.
  15. Frankl P. Extremal Problems and Coverings of the Space // Europ. J. Combin. 1980. V. 1. № 2. P. 101–106. https://doi.org/10.1016/S0195-6698(80)80045-X
  16. Frankl P., Wilson R. Intersection Theorems with Geometric Consequences // Combinatorica. 1981. V. 1. № 4. P. 357–368. https://doi.org/10.1007/BF02579457
  17. Frankl P., F¨uredi Z. Forbidding Just One Intersection // J. Combin. Theory Ser. A. 1985. V. 39. № 2. P. 160–176. https://doi.org/10.1016/0097-3165(85)90035-4
  18. R¨odl V. On a Packing and Covering Problem // Europ. J. Combin. 1985. V. 6. №1. P. 69–78. https://doi.org/10.1016/S0195-6698(85)80023-8
  19. Пономаренко Е.И., Райгородский А.М. Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения // Пробл. передачи информ. 2013. Т. 49. № 4. С. 98–104. https://www.mathnet.ru/rus/ppi2127
  20. Бобу А.В., Куприянов А.Э., Райгородский А.М. Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением // Матем. сб. 2016. Т. 207. № 5. С. 17–42. https://doi.org/10.4213/sm8473
  21. Райгородский А.М., Синельников-Мурылев П.С. Графы Джонсона, их случайные подграфы и некоторые их экстремальные характеристики // УМН. 2025. Т. 80. № 3 (483). С. 113–176. https://doi.org/10.4213/rm10233
  22. Райгородский А.М. Ох роматическом числе пространства // УМН. 2000. Т. 55. № 2 (332). С. 147–148. https://doi.org/10.4213/rm281
  23. Райгородский А.М., Харламова А.А. Осовок упностях (−1, 0, 1)-векторов с запретами на величины попарных скалярных произведений // Тр. семинара по векторному и тензорному анализу. Т. 29. М.: Изд-во МГУ, 2013. C. 130–146.
  24. Гутерман А.Э., Любимов В.К., Райгородский А.М., Усачев С.А. Очис лах независимости графов расстояний с вершинами в {−1, 0, 1}n // Мат. заметки. 2009. Т. 86. № 5. С. 794–796. https://doi.org/10.4213/mzm8518
  25. Гутерман А.Э., Любимов В.К., Райгородский А.М., Усачев С.А. Очис лах независимости дистанционных графов с вершинами в {−1, 0, 1}n: оценки, гипотезы и приложения к проблемам Нельсона–Эрдеша–Хадвигера и Борсука // Итоги науки и техн. Сер. Соврем. мат. и ее прил. 2009. Т. 65. М: ВИНИТИ, 2009. С. 82–100.
  26. Любимов В.К., Райгородский А.М. Он ижних оценках чисел независимости некоторых графов расстояний с вершинами в {−1, 0, 1}n // Докл. РАН. 2009. Т. 427. № 4. С. 458–460. https://www.mathnet.ru/rus/dan20968
  27. Москва В.Ф., Райгородский А.М. Новые нижние оценки чисел независимости графов расстояний с вершинами в {−1, 0, 1}n // Матем. заметки. 2011. Т. 89. № 2. С. 319–320. https://doi.org/10.4213/mzm8940
  28. Пономаренко Е.И., Райгородский А.М. Новые верхние оценки чисел независимости графов с вершинами в {−1, 0, 1}n и их приложения в задачах о хроматических числах дистанционных графов // Матем. заметки. 2014. Т. 96. № 1. С. 138–147. https://doi.org/10.4213/mzm10352
  29. Frankl P., Kupavskii A. Intersection Theorems for {0,Ѓ}1}-Vectors and s-Cross-Intersecting Families // Mosc. J. Comb. Number Theory. 2017. V. 7. № 2. P. 3–21 [P. 91–109].
  30. Frankl P., Kupavskii A. Correction to the Article “Intersection Theorems for (0,Ѓ}1)-Vectors and s-Cross-Intersecting Families” // Mosc. J. Comb. Number Theory. 2019. V. 8. № 4. P. 389–391. https://doi.org/10.2140/moscow.2019.8.385
  31. Frankl P., Kupavskii A. Erd˝os–Ko–Rado Theorem for {0,Ѓ}1}-Vectors // J. Combin. Theory Ser. A. 2018. V. 155. P. 157–179. https://doi.org/10.1016/j.jcta.2017.11.003
  32. Frankl P., Kupavskii A. Families of Vectors without Antipodal Pairs // Studia Sci. Math. Hungar. 2018. V. 55. № 2. P. 231–237. https://doi.org/10.1556/012.2018.55.2.1394
  33. Cherkashin D., Kiselev S. Independence Numbers of Johnson-Type Graphs // Bull. Braz. Math. Soc. (N.S.). 2023. V. 54. № 3. Paper No. 30 (23 pp.). https://doi.org/10.1007/s00574-023-00350-y
  34. Frankl P., Kupavskii A. Intersection Theorems for (−1, 0, 1)-Vectors // European J. Combin. 2024. V. 117. Paper No. 103830 (9 pp.). https://doi.org/10.1016/j.ejc.2023.103830
  35. Канель-Белов А.Я., Воронов В.А., Черкашин Д.Д. Охро матическом числе плоскости // Алгебра и анализ. 2017. Т. 29. №5. С. 68–89. https://www.mathnet.ru/rus/aa1557
  36. Воронов В.А., Канель-Белов А.Я., Струков Г.А., Черкашин Д.Д. Охро матических числах трехмерных слоек // Комбинаторика и теория графов. XIII. Зап. научн. сем. ПОМИ, Т. 518. СПб.: ПОМИ, 2022. С. 94–113. https://www.mathnet.ru/rus/znsl7293
  37. Райгородский А.М. Линейно-алгебраический метод в комбинаторике. М.: МЦНМО, 2015.
  38. Райгородский А.М. Проблема Эрдеша–Хадвигера и хроматические числа конечных геометрических графов // Матем. сб. 2005. Т. 196. № 1. С. 123–156. https://doi.org/10.4213/sm1263
  39. Ahlswede R., Khachatrian L.H. The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets // J. Combin. Theory Ser. A. 1996. V. 76. № 1. P. 121–138. https://doi.org/10.1006/jcta.1996.0092
  40. Ahlswede R., Khachatrian L.H. The Complete Intersection Theorem for Systems of Finite Sets // European J. Combin. 1997. V. 18. № 2. P. 125–136. https://doi.org/10.1006/eujc.1995.0092
  41. Ahlswede R., Blinovsky V.M. Lectures on Advances in Combinatorics. Berlin: Springer, 2008. https://doi.org/10.1007/978-3-540-78602-3
  42. Варшамов Р.Р. Оценка числа сигналов в кодах с коррекцией ошибок // ДАН СССР. 1957. Т. 117. № 5. С. 739–741. https://www.mathnet.ru/rus/dan22571
  43. Gilbert E.N. A Comparison of Signalling Alphabets // Bell Syst. Tech. J. 1952. V. 31. № 3. P. 504–522. https://doi.org/10.1002/j.1538-7305.1952.tb01393.x
  44. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025