Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников

Автор: Самиров Д.В., Райгородский А.М.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 2 (26) т.7, 2015 года.

Бесплатный доступ

В настоящей работе предложена модификация линейно-алгебраического метода в комбинаторике, позволяющая получать новые экспоненциальные нижние оценки в задаче о минимальном числе цветов, в которые можно так покрасить пространство, чтобы точки одного цвета не могли образовать равнобедренный треугольник с длинами сторон из некоторого множества.

Хроматические числа, евклидова теория рамсея, дистанционный граф

Короткий адрес: https://sciup.org/142186070

IDR: 142186070

Список литературы Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников

Райгородский A. M. Проблема Борсука и хроматические числа метрических пространств//Успехи матем. наук. 2001. Т. 56, вып. 1. С. 107-146
Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters//Thirty Essays on Geometric Graph Theory, J. Pach ed. 2013. P. 429-460
Raigorodskii A.M. Cliques and cycles in distance graphs and graphs of diameters//Discrete Geometry and Algebraic Combinatorics, AMS, Contemporary Mathematics. 2014. N 625. P. 93-109
Brass P., Moser W., Pach. J. Research problems in discrete geometry//Springer. 2005
Sz´ekely L. A. Erd˝os on unit distances and the Szemer´edi-Trotter theorems//J. Bolyai Math. Soc. 2002. N 11. P. 649-666
Soifer A. The Mathematical Coloring Book. Springer, 2009
Hadwiger H. Ein ¨ ur den Euklidischen Raum//Portugaliae Math. 1944. Uberdeckungssatz f¨ N 4. P. 140-144
Larman D.G., Rogers C.A. The realization of distances within sets in Euclidean space//Mathematika. 1972. N 19. P. 1-24
Frankl P, Wilson R. Intersection theorems with geometric consequences//Combinatorica. 1981. N 1. P. 357-368
Райгородский A. M. О хроматическом числе пространства//Успехи матем. наук. 2000. Т. 55, вып. 2. С. 147-148
Benda M., Perles M. Colorings of metric spaces//Geombinatorics. 2000. N 9. P. 113-126
Пономаренко E.I., Райгородский A.M. Новая нижняя оценка хроматического числа рационального пространства с одним и двумя запрещенными расстояниями//Матем. заметки. 2015. Т. 97, вып. 2. С. 84-89
Пономаренко E.I., Райгородский A.M. Новая нижняя оценка хроматического числа рационального пространства//Успехи матем. наук. 2013. Т. 68, вып. 5. C. 183-184
Пономаренко E.I., Райгородский A.M. О хроматическом числе пространства Q𝑛//Труды МФТИ. 2012. Т. 4, вып. 1. C. 127-130
Райгородский A.M. О хроматическом числе пространства с 𝑙𝑞-нормой//Успехи матем. наук. 2004. Т. 59, вып. 5. C. 161-162
Kang J.-H., F¨uredi Z. Distance graphs on Z𝑛 with 𝑙1-norm//Theoretical Comp. Sci. 2004. V. 319, N 1-3. P. 357-366
Kupavskii A. Б. On the chromatic NUMBER. of R𝑛 with an arbitrary norm//Discrete Math. 2011. N 311. P. 437-440
Lova´sz L. Self-dual polytopes and the chromatic NUMBER. of distance graphs on the sphere//Acta Sci. Math. 1983. N 45. P. 317-323
Купавский A. Б. О раскрасках сфер, вложенных в R𝑛//Матем. сборник. 2011. Т. 202, вып. 6. С. 83-110
Райгородский A.M. О хроматических числах сфер в евклидовых пространствах//Доклады РАН. 2010. Т. 432, вып. 2. С. 174-177
Raigorodskii A. M. On the chromatic NUMBER.s of spheres in R𝑛//Combinbatorica. 2012. V. 32, N 1. P. 111-123
Купавский A.Б. Хроматическое число пространства R𝑛 с множеством запрещенных расстояний//Доклады РАН. 2010. -Т. 435, вып. 6. С. 740-743
Райгородский A.M. О хроматическом числе пространства с двумя запрещенными расстояниями//Доклады РАН. 2006. Т. 408, вып. 5. С. 601-604
Райгородский A.M., Шитова И.М. О хроматических числах вещественных и рациональных пространств с вещественными или рациональными запрещенными расстояниями//Матем. сборник. 2008. Т. 199, вып. 4. С. 107-142
Горская Е.С., Митричева И.М., Протасов В.Ю., Райгородский A.M. Оценка хроматических чисел евклидова пространства методами выпуклой минимизации//Матем. сборник. 2009. Т. 200, вып. 6. С. 3-22
Мощевитин Н.Г., Райгородский A.M. О раскрасках пространства R𝑛 с несколькими запрещенными расстояниями//Матем. заметки. 2007. Т. 81, вып. 5. С. 733-744
Бердников А.В., Райгородский A.M. Хроматические числа евклидова пространства с двумя запрещенными расстояниями//Матем. заметки. 2014. Т. 96, вып. 5. С. 790-793
Graham R.L., Rothschild B.L.,Spencer J.H. Ramsey theory//John Wily and Sons, NY, Second Edition. 1990
Frankl P., R¨odl V. All triangles are Ramsey//Transactions of the Amer. Math. Soc. 1986. V. 297, N 2. P. 777-779
Frankl P., R¨odl V. Forbidden intersections//Transactions of the Amer. Math. Soc. 1987. V. 300, N 1. P. 259-286
Frankl P., R¨odl V. A partition property of simplices in Euclidean space//J. Amer. Math. Soc. 1990. V. 3, N 1. P. 1-7
Райгородский A.M., Звонарев A.E., Самиров Д.В., Харламова А.А. Улучшение теоремы Франкла-Рёдля о числе ребер гиперграфа с запретами на пересечения//Доклады РАН. 2014. Т. 457, вып. 2. С. 144-146
Райгородский A.M., Звонарев A.E., Самиров Д.В., Харламова А.А. О хроматическом числе пространства с запрещенным равносторонним треугольником//Матем. сборник. 2014. Т. 205, вып. 9. С. 97-120
Райгородский A.M., Звонарев A.E. Улучшения теоремы Франкла-Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником//Труды Математического Института имени В.А. Стеклова. 2015. Т. 288. С. 109-119
Райгородский A.M., Самиров Д.В. Хроматические числа пространств с запрещенными одноцветными треугольниками//Матем. заметки. 2013. Т. 93, вып. 1. С. 134-143
Райгородский A.M., Самиров Д.В. Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками//Итоги науки и техники, Современная математика и ее приложения. 2013. Т. 125. С. 252-268
Райгородский A.M., Самиров Д.В. Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками//Доклады РАН. 2014. Т. 456, вып. 3. С. 280-283
Прахар К. Распределение простых чисел//М.: Мир, 1967
Baker R.C., Harman G., Printz J. The difference between consecutive primes, II//Proceedings of the London Mathematical Society. 2001. N 83. P. 532-562
Райгородский A.M. Линейно-алгебраический метод в комбинаторике//М.: МЦНМО, Второе издание. 2015
Babai L., Frankl P. Linear algebra methods in combinatorics//Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2. 1992
Alon N., Babai L., Suzuki H. Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems//J. Combin. Theory A. 1991. N 58. P. 165-180

Еще

Статья научная