О реализации подграфов случайного графа графами диаметров на плоскости и в пространстве

Автор: Кокоткин А.А., Райгородский А.М.

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

Статья в выпуске: 2 (22) т.6, 2014 года.

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

Получены новые оценки для максимального числа вершин в индуцированном подграфе случайного графа Эрдеша-Реньи, который с высокой вероятностью можно реализовать как граф диаметров в размерности 2 или 3, имеющий максимальное для этой размерности хроматическое число.

Граф диаметров, случайный граф

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

IDR: 142186000

Список литературы О реализации подграфов случайного графа графами диаметров на плоскости и в пространстве

Borsuk K. Drei S¨atze ¨uber die 𝑛-dimensionale euklidische Sph¨are//Fundamenta Math. -1933. -V. 20. -P. 177-190
Kahn J., Kalai G. A counterexample to Borsuk’s conjecture//Bulletin (new series) of the AMS. -1993. -V. 29, N 1. -P. 60-62
Райгородский А.М. О размерности в проблеме Борсука//Успехи матем. наук. -1997. -Т. 52, № 6. -C. 181-182
Райгородский А.М. Об одной оценке в проблеме Борсука//Успехи матем. наук. -1999. -Т. 54, № 2. -C. 185-186
Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств//Успехи матем. наук. -2001. -T. 56, № 1. -C. 107-146
Райгородский А.М. Проблема Борсука. -M.: МЦНМО, 2006
Raigorodskii A.M. Three lectures on the Borsuk partition problem//London Mathematical Society Lecture Note Series. -2007. -V. 347. -P. 202-248
Райгородский А.М. Вокруг гипотезы Борсука//Итоги науки и техники. Серия «Современная математика». -2007. -T. 23. -C. 147-164
Райгородский А.М. Контрпримеры к гипотезе Борсука на сферах малого радиуса//Доклады РАН. -2010. -T. 434, № 2. -C. 61-163
Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters//Thirty Essays on Geometric Graph Theory/J. Pach ed. -Springer, 2013. -P. 429-460
Raigorodskii A.M. The Borsuk partition problem: the seventieth anniversary//Mathematical Intelligencer. -2004. -V. 26. -N 3. -P. 4-12
Болтянский В.Г., Гохберг И.Ц. Теоремы и задачи комбинаторной геометрии. -М.: Наука, 1965
Boltyanski V.G., Martini H., Soltan P.S. Excursions into combinatorial geometry. -Berlin: Universitext, Springer, 1997
Райгородский А.М. Гипотеза Кнезера и топологические методы в комбинаторике. -M.: МЦНМО, 2011
Matouˇsek J. Using the Borsuk-Ulam theorem. -Berlin: Universitext, Springer, 2003
Райгородский А.М. Модели случайных графов. -M.: МЦНМО, 2011
Bollob´as B. Random Graphs. -Cambridge Univ. Press. -Second Edition, 2001
Колчин В.Ф. Случайные графы. -M.: Физматлит, 2002
Janson S., Luczak T., Ruci´nski A. Random graphs. -NY: Wiley, 2000
Erd˝os P., R´enyi A. On random graphs I//Publ. Math. Debrecen. -1959. V. 6. -P. 290-297
Erd˝os P., R´enyi A. On the evolution of random graphs//Publ. Math. Inst. Hungar. Acad. Sci. -1960. -V. 5. -P. 17-61
Erd˝os P., R´enyi A. On the evolution of random graphs//Bull. Inst. Int. Statist. Tokyo. -1961. -V. 38. -P. 343-347
Кокоткин А.А., Райгородский А.М. О реализации случайных графов графами диаметров//Труды МФТИ. -2012. -T. 4, № 1. -C. 19-28
Райгородский А.М. Проблема Нелсона-Эрдеша-Хадвигера и реализация случайных графов в пространстве//Успехи матем. наук. -2006. -V. 61, № 4. -C. 195-196
Нагаева С.В., Райгородский А.М. О вложимости конечных графов расстояний с большим хроматическим числом в случайные графы//Итоги науки и техники. Сер. «Современная математика». -2009. -T. 62. -C. 47-66
Нагаева С.В., Райгородский А.М. О реализации случайных графов графами расстояний в пространствах фиксированной размерности//Доклады РАН. -2009. -T. 424, № 3. -C. 315-317
Brass P., Moser W., Pach J. Research problems in discrete geometry. -Berlin: Springer, 2005
Bollob´as B. The chromatic number of random graphs//Combinatorica. -1988. -V. 8, N 1. -P. 49-55
Алон Н., Спенсер Дж. Вероятностный метод. -М.: Бином. Лаборатория знаний, 2007

Еще

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