О больших подграфах графа расстояний, имеющих маленькое хроматическое число
- Авторы: Кокоткин А.А.1, Райгородский А.М.1
-
Учреждения:
- Московский физико-технический институт
- Выпуск: Том 51, № (2013)
- Страницы: 64-73
- Раздел: Статьи
- URL: https://ogarev-online.ru/2413-3639/article/view/347334
- ID: 347334
Цитировать
Аннотация
В настоящей работе доказано, что в каждом дистанционном графе на плоскости есть индуцированный подграф, содержащий более 91 процента вершин исходного графа и имеющий хроматическое число, не большее четырех. С помощью этого результата найден порядок роста пороговой вероятности для свойства случайного графа быть изоморфным некоторому дистанционному графу на плоскости. Предложены обобщения результатов на другие размерности.
Об авторах
А. А. Кокоткин
Московский физико-технический институт141700, Московская область, г. Долгопрудный, Институтский переулок, 9
А. М. Райгородский
Московский физико-технический институт141700, Московская область, г. Долгопрудный, Институтский переулок, 9
Список литературы
- Колчин В. Ф. Случайные графы. - М.: Физматлит, 2002.
- Купавский А. Б., Райгородский А. М., Титова М. В. О плотнейших множествах без расстояния единица в пространствах малых размерностей// Тр. МФТИ. - 4, № 1. - 2012. - С. 91-110.
- Райгородский А. М. Проблема Борсука и хроматические числа метрических пространств// Усп. мат. наук. - 2001. - 56, № 1. - С. 107-146.
- Райгородский А. М. О хроматическом числе пространства// Усп. мат. наук. - 2000. - 55, № 2. - С. 147-148.
- Райгородский А. М. Хроматические числа. - М.: МЦНМО, 2003.
- Райгородский А. М. Линейно-алгебраический метод в комбинаторике. - М.: МЦНМО, 2007.
- Райгородский А. М. Модели случайных графов. - М.: МЦНМО, 2011.
- Сойфер А. Хроматическое число плоскости: его прошлое, настоящее и будущее// Мат. просвещ. - 2004. - 8.
- Agarwal P. K., Pach J. Combinatorial geometry. - New York: John Wiley and Sons Inc., 1995.
- Alon N., Spencer J. The probabilistic method. - Wiley-Interscience Ser. Discr. Math. Optim., 2000.
- Bolloba´ s B. Random graphs. - Cambridge Univ. Press, 2001.
- Brass P., Moser W., Pach J. Research problems in discrete geometry. - Springer, 2005.
- Coulson D. A 15-colouring of 3-space omitting distance one// Discrete Math. - 2002. - 256. - С. 83-90.
- Croft H. T. Incident incidents// Eureka (Cambridge). - 1967. - 30. - С. 22-26.
- De Bruijn N. G., Erdo˝s P. A colour problem for in nite graphs and a problem in the theory of relations// Proc. Koninkl. Nederl. Acad. Wet. Ser. A. - 54, № 5. - 1951. - С. 371-373.
- Janson S., Luczak T., Rucin´ ski A. Random graphs. - New York: Wiley, 2000.
- Klee V., Wagon S. Old and new unsolved problems in plane geometry and number theory. - Math. Association of America, 1991.
- Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean space// Mathematika. - 1972. - 19. - С. 1-24.
- Nechushtan O. Note on the space chromatic number// Discrete Math. - 2002. - 256. - С. 499-507.
- Soifer A. The mathematical coloring book. - Springer, 2009.
- Sze´kely L. A., Erdo˝s P. On unit distances and the Szemere´di-Trotter theorems// Paul Erdo˝s and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11. - 2002. - С. 649-666.
Дополнительные файлы
