CONSTRUCTIVE LOWER BOUNDS ON THE INDEPENDENCE NUMBERS OF DISTANCE GRAPHS WITH VERTICES IN {-1, 0, 1}n

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

New constructive lower bounds on the independence numbers of distance graphs with vertices in {-1, 0, 1}n are presented. Asymptotically significant lower bounds valid for a wide range of parameters are obtained. Numerical calculations demonstrate relationships between the obtained results and known upper bounds.

About the authors

A. R Akhiiarov

Moscow Institute of Physics and Technology (State University)

Email: akhiiarov.ar@phystech.edu

A. V Bobu

Criteo S.A.

Email: a.v.bobu@gmail.com
Paris, France

A. M Raigorodskii

Moscow Institute of Physics and Technology (State University); Lomonosov Moscow State University, Faculty of Mechanics and Mathematics; Caucasus Mathematical Center, Adyghe State University; Buryat State University, Institute of Mathematics and Computer Science

Email: mraigor@yandex.ru
Department of Discrete Mathematics and Laboratory of Advanced Combinatorics and Network Applications; Department of Mathematical Statistics and Random Processes

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences