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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

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.

作者简介

A. Akhiiarov

Moscow Institute of Physics and Technology (State University)

Email: akhiiarov.ar@phystech.edu

A. Bobu

Criteo S.A.

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

A. 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

参考

  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
下载

版权所有 © Russian Academy of Sciences, 2025