CONSTRUCTIVE LOWER BOUNDS ON THE INDEPENDENCE NUMBERS OF DISTANCE GRAPHS WITH VERTICES IN {-1, 0, 1}n
- Авторлар: Akhiiarov A.R1, Bobu A.V2, Raigorodskii A.M1,3,4,5
-
Мекемелер:
- Moscow Institute of Physics and Technology (State University)
- Criteo S.A.
- Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
- Caucasus Mathematical Center, Adyghe State University
- Buryat State University, Institute of Mathematics and Computer Science
- Шығарылым: Том 61, № 2 (2025)
- Беттер: 69-82
- Бөлім: Large Systems
- URL: https://genescells.com/0555-2923/article/view/691888
- DOI: https://doi.org/10.7868/S3034583925020054
- ID: 691888
Дәйексөз келтіру
Аннотация
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
Әдебиет тізімі
- Hadwiger H. Ein ¨Uberdeckungssatz f¨ur den euklidischen Raum // Portugal. Math. 1944. V. 4. P. 140–144.
- Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств // УМН. 2001. Т. 56. №1 (337). С. 107–146. https://doi.org/10.4213/rm358
- Brass P., Moser W., Pach J. Research Problems in Discrete Geometry. Berlin: Springer, 2005. https://doi.org/10.1007/0-387-29929-7
- 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
- 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
- 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.
- de Grey A.D.N.J. The Chromatic Number of the Plane Is at Least 5 // Geombinatorics. 2018. V. 28. № 1. P. 18–31.
- 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
- 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
- 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
- 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
- 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
- Nagy Z. A Certain Constructive Estimate of the Ramsey Number // Mat. Lapok. 1972. V. 23. P. 301–302.
- 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.
- 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
- Frankl P., Wilson R. Intersection Theorems with Geometric Consequences // Combinatorica. 1981. V. 1. № 4. P. 357–368. https://doi.org/10.1007/BF02579457
- 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
- 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
- Пономаренко Е.И., Райгородский А.М. Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения // Пробл. передачи информ. 2013. Т. 49. № 4. С. 98–104. https://www.mathnet.ru/rus/ppi2127
- Бобу А.В., Куприянов А.Э., Райгородский А.М. Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением // Матем. сб. 2016. Т. 207. № 5. С. 17–42. https://doi.org/10.4213/sm8473
- Райгородский А.М., Синельников-Мурылев П.С. Графы Джонсона, их случайные подграфы и некоторые их экстремальные характеристики // УМН. 2025. Т. 80. № 3 (483). С. 113–176. https://doi.org/10.4213/rm10233
- Райгородский А.М. Ох роматическом числе пространства // УМН. 2000. Т. 55. № 2 (332). С. 147–148. https://doi.org/10.4213/rm281
- Райгородский А.М., Харламова А.А. Осовок упностях (−1, 0, 1)-векторов с запретами на величины попарных скалярных произведений // Тр. семинара по векторному и тензорному анализу. Т. 29. М.: Изд-во МГУ, 2013. C. 130–146.
- Гутерман А.Э., Любимов В.К., Райгородский А.М., Усачев С.А. Очис лах независимости графов расстояний с вершинами в {−1, 0, 1}n // Мат. заметки. 2009. Т. 86. № 5. С. 794–796. https://doi.org/10.4213/mzm8518
- Гутерман А.Э., Любимов В.К., Райгородский А.М., Усачев С.А. Очис лах независимости дистанционных графов с вершинами в {−1, 0, 1}n: оценки, гипотезы и приложения к проблемам Нельсона–Эрдеша–Хадвигера и Борсука // Итоги науки и техн. Сер. Соврем. мат. и ее прил. 2009. Т. 65. М: ВИНИТИ, 2009. С. 82–100.
- Любимов В.К., Райгородский А.М. Он ижних оценках чисел независимости некоторых графов расстояний с вершинами в {−1, 0, 1}n // Докл. РАН. 2009. Т. 427. № 4. С. 458–460. https://www.mathnet.ru/rus/dan20968
- Москва В.Ф., Райгородский А.М. Новые нижние оценки чисел независимости графов расстояний с вершинами в {−1, 0, 1}n // Матем. заметки. 2011. Т. 89. № 2. С. 319–320. https://doi.org/10.4213/mzm8940
- Пономаренко Е.И., Райгородский А.М. Новые верхние оценки чисел независимости графов с вершинами в {−1, 0, 1}n и их приложения в задачах о хроматических числах дистанционных графов // Матем. заметки. 2014. Т. 96. № 1. С. 138–147. https://doi.org/10.4213/mzm10352
- 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].
- 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
- 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
- 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
- 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
- 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
- Канель-Белов А.Я., Воронов В.А., Черкашин Д.Д. Охро матическом числе плоскости // Алгебра и анализ. 2017. Т. 29. №5. С. 68–89. https://www.mathnet.ru/rus/aa1557
- Воронов В.А., Канель-Белов А.Я., Струков Г.А., Черкашин Д.Д. Охро матических числах трехмерных слоек // Комбинаторика и теория графов. XIII. Зап. научн. сем. ПОМИ, Т. 518. СПб.: ПОМИ, 2022. С. 94–113. https://www.mathnet.ru/rus/znsl7293
- Райгородский А.М. Линейно-алгебраический метод в комбинаторике. М.: МЦНМО, 2015.
- Райгородский А.М. Проблема Эрдеша–Хадвигера и хроматические числа конечных геометрических графов // Матем. сб. 2005. Т. 196. № 1. С. 123–156. https://doi.org/10.4213/sm1263
- 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
- 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
- Ahlswede R., Blinovsky V.M. Lectures on Advances in Combinatorics. Berlin: Springer, 2008. https://doi.org/10.1007/978-3-540-78602-3
- Варшамов Р.Р. Оценка числа сигналов в кодах с коррекцией ошибок // ДАН СССР. 1957. Т. 117. № 5. С. 739–741. https://www.mathnet.ru/rus/dan22571
- 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
- Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
Қосымша файлдар
