Е. Е. Демёхин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера”, Матем. сб., 204:4 (2013), 49–78; E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508

Математический сборник

RUS ENG

ЖУРНАЛЫ ПЕРСОНАЛИИ ОРГАНИЗАЦИИ КОНФЕРЕНЦИИ СЕМИНАРЫ ВИДЕОТЕКА ПАКЕТ AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Общая информация
	Последний выпуск
	Скоро в журнале
	Архив
	Импакт-фактор
	Правила для авторов
	Лицензионный договор
	Загрузить рукопись
	Историческая справка

	Поиск публикаций
	Поиск ссылок

	RSS
	Последний выпуск
	Текущие выпуски
	Архивные выпуски
	Что такое RSS

Матем. сб.:
Год:
Том:
Выпуск:
Страница:
	Найти

Персональный вход:
Логин:
Пароль:
	Запомнить пароль
	Войти
	Забыли пароль?
	Регистрация

Математический сборник, 2013, том 204, номер 4, страницы 49–78
DOI: https://doi.org/10.4213/sm7830 (Mi sm7830)

Эта публикация цитируется в 21 научных статьях (всего в 21 статьях)

Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера

Е. Е. Демёхин^a, А. М. Райгородский^ab, О. И. Рубанов^ab

^a Механико-математический факультет Московского государственного университета им. М. В. Ломоносова
^b Факультет инноваций и высоких технологий Московского физико-технического института

PDF полного текста (732 kB) PDF английской версии (494 kB) Список цитирования (21)

Список литературы:

PDF

HTML

DOI: https://doi.org/10.4213/sm7830

Аннотация: Доказано существование последовательностей дистанционных графов

$G_n\subset\mathbb R^n$ , хроматические числа которых растут экспоненциально, но которые в то же время не содержат клик или циклов заданного наперед размера.
Библиография: 42 названия.

Ключевые слова: дистанционный граф, случайный граф, хроматическое число, клика, цикл.

Финансовая поддержка	Номер гранта
Российский фонд фундаментальных исследований	12-01-00683
Министерство образования и науки Российской Федерации	НШ-2519.2012.1
Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант № 12-01-00683) и Программы Президента РФ поддержки ведущих научных школ (грант № НШ-2519.2012.1).

Поступила в редакцию: 14.12.2010 и 09.12.2011

Англоязычная версия:
Sbornik: Mathematics, 2013, Volume 204, Issue 4, Pages 508–538
DOI: https://doi.org/10.1070/SM2013v204n04ABEH004310

Реферативные базы данных:

Тип публикации: Статья

УДК: 519.112.4+519.174+519.176

MSC: 05C15, 05C35, 05D10

Образец цитирования: Е. Е. Демёхин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера”, Матем. сб., 204:4 (2013), 49–78; E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508–538

Цитирование в формате AMSBIB

\RBibitem{DemRaiRub13}

\by Е.~Е.~Демёхин, А.~М.~Райгородский, О.~И.~Рубанов

\paper Дистанционные графы, имеющие большое хроматическое число

и не содержащие клик или циклов заданного размера

\jour Матем. сб.

\yr 2013

\vol 204

\issue 4

\pages 49--78

\mathnet{http://mi.mathnet.ru/sm7830}

\crossref{https://doi.org/10.4213/sm7830}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3097579}

\zmath{https://zbmath.org/?q=an:1268.05070}

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2013SbMat.204..508D}

\elib{https://elibrary.ru/item.asp?id=19066661}

\transl

\by E.~E.~Demekhin, A.~M.~Raigorodskii, O.~I.~Rubanov

\paper Distance graphs having large chromatic numbers and containing no cliques or cycles of a~given size

\jour Sb. Math.

\yr 2013

\vol 204

\issue 4

\pages 508--538

\crossref{https://doi.org/10.1070/SM2013v204n04ABEH004310}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000320302700003}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84888343984}

Образцы ссылок на эту страницу:

https://www.mathnet.ru/rus/sm7830

https://doi.org/10.4213/sm7830

https://www.mathnet.ru/rus/sm/v204/i4/p49

Эта публикация цитируется в следующих 21 статьяx:

Ю. А. Демидович, М. Е. Жуковский, “Хроматические числа дистанционных графов без коротких нечетных циклов в рациональных пространствах”, Матем. заметки, 109:5 (2021), 723–733 ; Yu. A. Demidovich, M. E. Zhukovskii, “Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces”, Math. Notes, 109:5 (2021), 727–734
Ф. А. Пушняков, А. М. Райгородский, “Оценка числа ребер в особых подграфах некоторого дистанционного графа”, Матем. заметки, 107:2 (2020), 286–298 ; Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332
Ю. А. Демидович, “Дистанционные графы в рациональном пространстве с большим хроматическим числом и без клик заданного размера”, Матем. заметки, 106:1 (2019), 24–39 ; Yu. A. Demidovich, “Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space”, Math. Notes, 106:1 (2019), 38–51
А. А. Сагдеев, “Об одной теореме Франкла–Уилсона”, Пробл. передачи информ., 55:4 (2019), 86–106 ; A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395
Sagdeev A.A. Raigorodskii A.M., “On a Frankl-Wilson Theorem and Its Geometric Corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033
А. А. Соколов, “О хроматических числах рациональных пространств”, Матем. заметки, 103:1 (2018), 120–128 ; A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103:1-2 (2018), 111–117
А. В. Бердников, “Хроматические числа графов расстояний с несколькими запрещенными расстояниями без клик заданного размера”, Пробл. передачи информ., 54:1 (2018), 78–92 ; A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Problems Inform. Transmission, 54:1 (2018), 70–83
А. А. Сагдеев, “О нижних оценках хроматических чисел дистанционных графов с большим обхватом”, Матем. заметки, 101:3 (2017), 430–445 ; A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth”, Math. Notes, 101:3 (2017), 515–528
А. А. Сагдеев, “О хроматическом числе пространства с запрещенным правильным симплексом”, Матем. заметки, 102:4 (2017), 579–585 ; A. Sagdeev, “The Chromatic Number of Space with Forbidden Regular Simplex”, Math. Notes, 102:4 (2017), 541–546
A.A. Sagdeev, “On a Frankl–Rödl theorem and its geometric corollaries”, Electronic Notes in Discrete Mathematics, 61 (2017), 1033
М. М. Пядёркин, “Числа независимости случайных подграфов некоторого дистанционного графа”, Матем. заметки, 99:2 (2016), 288–297 ; M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319
С. Н. Попова, “Закон нуля или единицы для случайных подграфов некоторых дистанционных графов с вершинами в $\mathbb Z^n$ ”, Матем. сб., 207:3 (2016), 153–174 ; S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in $\mathbb Z^n$ ”, Sb. Math., 207:3 (2016), 458–478
Ф. А. Пушняков, “О числе ребер в индуцированных подграфах специального дистанционного графа”, Матем. заметки, 99:4 (2016), 550–558 ; Ph. Pushnyakov, “On the Number of Edges in Induced Subgraphs of a Special Distance Graph”, Math. Notes, 99:4 (2016), 545–551
С. Н. Попова, “Законы нуля или единицы для случайных графов с вершинами в булевом кубе”, Матем. тр., 19:1 (2016), 106–177 ; S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75
Л. Исхаков, М. Миронов, “Диаметр случайного дистанционного графа”, Совр. матем. и ее приложения, 100 (2016), 24–35 ; L. Iskhakov, M. Mironov, “Diameters of random distance graphs”, Journal of Mathematical Sciences, 227:4 (2017), 407–418
В. В. Уткин, “Гамильтоновы цепи в дистанционных графах”, Матем. заметки, 97:6 (2015), 904–916 ; V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929
М. М. Пядеркин, “Об устойчивости в теореме Эрдеша–Ко–Радо”, Докл. РАН, 462:2 (2015), 144–147 ; M. M. Pyaderkin, “On the stability of the ErdH os-Ko-Rado theorem”, Dokl. Math., 91:3 (2015), 290–293
Ф. А. Пушняков, “Новая оценка числа ребер в индуцированных подграфах специального дистанционного графа”, Пробл. передачи информ., 51:4 (2015), 71–77 ; Ph. A. Pushnyakov, “A new estimate for the number of edges in induced subgraphs of a special distance graph”, Problems Inform. Transmission, 51:4 (2015), 371–377
А. Б. Купавский, “Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами”, Изв. РАН. Сер. матем., 78:1 (2014), 65–98 ; A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers”, Izv. Math., 78:1 (2014), 59–89
С. Н. Попова, “Законы нуля или единицы для случайных дистанционных графов с вершинами в $\{0,1\}^n$ ”, Докл. РАН, 458:1 (2014), 18–21 ; S. N. Popova, “Zero-one laws for random distance graphs with vertices in $\{0,1\}^n$ ”, Dokl. Math., 90:2 (2014), 535–538

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Статистика просмотров:
Страница аннотации:	831
PDF русской версии:	507
PDF английской версии:	38
Список литературы:	92
Первая страница:	64

Обратная связь:

Пользовательское соглашение

Регистрация посетителей портала

Логотипы