О реализации случайных графов графами диаметров
Автор: Кокоткин Андрей Александрович, Райгородский Андрей Михайлович
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Случайные графы
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
Работа находится на стыке комбинаторной геометрии и теории случайных графов. Мы изучаем условия, при которых случайный граф в модели Эрдеша-Реньи содержит подграфы, изоморфные графам диаметров на плоскости с хроматическим числом 3. Для соответствующей экстремальной характеристики случайного графа удается получить точные по порядку оценки и дажеасимптотики.
Случайный граф, граф диаметров, хроматическое число
Короткий адрес: https://sciup.org/142186204
IDR: 142186204
Список литературы О реализации случайных графов графами диаметров
- Erdos P. On sets of distances of n points//Amer. Math. Monthly.-1946.-V. 53.-P. 248-250.
- Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости.-М.: Наука, 1965.
- Райгородский А.М. Проблема Борсука и хроматические числа метрических пространств//УМН. -2001.-Т. 56, вып. 1.-С. 107-146.
- Raigorodskii A.M. Three lectures on the Borsuk partition problem//London Mathematical Society Lecture Note Series. -2007. -V. 347. -P. 202-248.
- Raigorodskii A.M. The Borsuk partition problem: the seventieth anniversary//Mathematical Intelligencer. -2004. -V. 26, N 3. -P. 4-12.
- Райгородский А.М. Вокруг гипотезы Борсука//Итоги науки и техники.-Сер. "Современная математика".-2007.-Т. 23.-С. 147-164.
- Райгородский А.М. Проблема Борсука.-М.: МЦНМО, 2006.
- Bollobas B. Random Graphs.-Cambridge Univ. Press, 2001.
- Колчин В.Ф. Случайные графы.-М.: Физматлит, 2002.
- Janson S., Luczak T., Rucinski A. Random graphs.-New York: Wiley, 2000.
- Райгородский А.М. Проблема Нелсона-Эрдеша-Хадвигера и реализация случайных графов в пространстве//УМН. -2006.-Т. 61, вып. 4.-С. 195-196.
- Нагаева С. В., Райгородский А.М. О вложимости конечных графов расстояний с большим хроматическим числом в случайные графы//Итоги науки и техники.-Сер. "Современная математика".-2009.-Т. 62.-С. 47-66.
- Нагаева С.В., Райгородский А.М. О реализации случайных графов графами расстояний в пространствах фиксированной размерности//Доклады РАН. -2009.-Т. 424, № 3.-С. 315-317.
Статья научная
