О дистанционных графах с большим хроматическим и малым кликовым числами
Автор: Звонарев Артем Евгеньевич, Райгородский Андрей Михайлович
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Хроматические числа пространств
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
Работа связана с изучением хроматического числа χ (Rn) евклидова пространства, которое определяется как минимальное количество цветов, необходимых для такой покраски точек Rn, что любые две точки, отстоящие друг от друга на расстояние 1, покрашены в разные цвета. Известно, чтоχ (Rn) ≥ (ζ+o(1))n, где ζ = 1.239... Это равносильно существованию n-мерного дистанционного графа (вершины - точки, ребра - отрезки длины 1) с хроматическим числом (ζ +o(1))n. Мы доказываем гораздо большее: существуют дистанционные графы с хроматическим числом (ζ +o(1))n и без клик растущего размера.
Хроматическое число пространства, дистанционный граф, граф без клик, теория рамсея
Короткий адрес: https://sciup.org/142186201
IDR: 142186201
Список литературы О дистанционных графах с большим хроматическим и малым кликовым числами
- Erdos P. Graph theory and probability//Canadian Mathematical Bullettin.-1959.-V. 11.-P. 34-38.
- de Bruijn N.G., Erdos P. A colour problem for infinite graphs and a problem in the theory of relations//Proc. Koninkl. Nederl. Acad. Wet. Ser. A. -1951. -V. 54, N 5. -P. 371-373.
- Райгородский А.М. О хроматическом числе пространства//УМН. -2000. -Т. 55, вып. 2. -С. 147-148.
- Larman D.G., Rogers C.A. The realization of distances within sets in Euclidean space//Mathematika. -1972. -V. 19. -P. 1-24.
- Райгородский А.М. О дистанционных графах с большим хроматическим числом, не содержащих больших симплексов//УМН. -2007.-Т. 62, вып. 6.-С. 187-188.
- Raigorodskii A.M., Rubanov O. I. On the clique and the chromatic numbers of highdimensional distance graphs//Number Theory and Applications: Proceedings of the International Conferences on Number Theory and Cryptography S.D. Adhikari and B. Ramakrishnan, Harish-Chandra Research Institute, Editors -A publication of Hindustan Book Agency.-2009.-P. 149-157.
- Райгородский А.М., Рубанов О.И. О графах расстояний с большим хроматическим числом и без больших клик//Матем. заметки.-2010.-Т. 87, № 3.-С. 417-428.
- Демехин Е. Е., Райгородский А.М., Рубанов О.И. Графы расстояний, имеющие большие хроматические числа и не содержащие клик или циклов заданного размера//Матем. сборник.-Принято в печать.
- Райгородский А.М. Проблема Борсука и хроматические числа метрических пространств//УМН. -2001.-Т. 56, вып. 1. -С. 107-146.
- Szekely L. A. Erdos on unit distances and the Szemeredi-Trotter theorems//J. Bolyai Math. Soc. -2002. -V. 11. -P. 649-666.
- Райгородский А.М. Хроматические числа. М.: МЦНМО, 2003.
- Райгородский А.М. Линейно-алгебраический метод в комбинаторике. -М.: МЦНМО, 2007.
- Agarwal P.K., Pach J. Combinatorial geometry. -New York: John Wiley and Sons Inc., 1995.
- Klee V., Wagon S. Old and new unsolved problems in plane geometry and number theory. -Math. Association of America, 1991.
- Brass P., Moser W., Pach J. Research problems in discrete geometry. Berlin: Springer, 2005.
- Soifer A. The Mathematical Coloring Book. -Springer, 2009.
