RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

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

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



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






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


Матем. сб., 2013, том 204, номер 4, страницы 49–78 (Mi msb7830)  

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

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

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

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

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

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

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

Автор для корреспонденции

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

Полный текст: PDF файл (732 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Sbornik: Mathematics, 2013, 204:4, 508–538

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

Тип публикации: Статья
УДК: 519.112.4+519.174+519.176
MSC: 05C15, 05C35, 05D10
Поступила в редакцию: 14.12.2010 и 09.12.2011

Образец цитирования: Е. Е. Демёхин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера”, Матем. сб., 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/msb7830}
\crossref{https://doi.org/10.4213/sm7830}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3097579}
\zmath{https://zbmath.org/?q=an:1268.05070}
\adsnasa{http://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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000320302700003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84888343984}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/msb7830
  • https://doi.org/10.4213/sm7830
  • http://mi.mathnet.ru/rus/msb/v204/i4/p49

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


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

    Эта публикация цитируется в следующих статьяx:
    1. А. Б. Купавский, А. М. Райгородский, “О препятствиях к реализации дистанционных графов с большим хроматическим числом на сферах малого радиуса”, Матем. сб., 204:10 (2013), 47–90  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. B. Kupavskii, A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii”, Sb. Math., 204:10 (2013), 1435–1479  crossref  isi  elib
    2. А. Б. Купавский, “Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами”, Изв. РАН. Сер. матем., 78:1 (2014), 65–98  mathnet  crossref  mathscinet  zmath  adsnasa  elib; 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  crossref  isi  elib
    3. С. Н. Попова, “Законы нуля или единицы для случайных дистанционных графов с вершинами в $\{0,1\}^n$”, Докл. РАН, 458:1 (2014), 18–21  crossref  zmath  elib; S. N. Popova, “Zero-one laws for random distance graphs with vertices in $\{0,1\}^n$”, Dokl. Math., 90:2 (2014), 535–538  crossref  zmath  isi  elib  scopus
    4. В. В. Уткин, “Гамильтоновы цепи в дистанционных графах”, Матем. заметки, 97:6 (2015), 904–916  mathnet  crossref  mathscinet  elib; V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929  crossref  isi
    5. М. М. Пядеркин, “Об устойчивости в теореме Эрдеша–Ко–Радо”, Докл. РАН, 462:2 (2015), 144–147  crossref  mathscinet  zmath  elib; M. M. Pyaderkin, “On the stability of the ErdH os-Ko-Rado theorem”, Dokl. Math., 91:3 (2015), 290–293  crossref  mathscinet  zmath  isi  elib  scopus
    6. Ф. А. Пушняков, “Новая оценка числа ребер в индуцированных подграфах специального дистанционного графа”, Пробл. передачи информ., 51:4 (2015), 71–77  mathnet; 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  crossref  isi  elib
    7. М. М. Пядёркин, “Числа независимости случайных подграфов некоторого дистанционного графа”, Матем. заметки, 99:2 (2016), 288–297  mathnet  crossref  mathscinet  elib; M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319  crossref  isi
    8. С. Н. Попова, “Закон нуля или единицы для случайных подграфов некоторых дистанционных графов с вершинами в $\mathbb Z^n$”, Матем. сб., 207:3 (2016), 153–174  mathnet  crossref  mathscinet  adsnasa  elib; 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  crossref  isi
    9. Ф. А. Пушняков, “О числе ребер в индуцированных подграфах специального дистанционного графа”, Матем. заметки, 99:4 (2016), 550–558  mathnet  crossref  mathscinet  elib; Ph. Pushnyakov, “On the Number of Edges in Induced Subgraphs of a Special Distance Graph”, Math. Notes, 99:4 (2016), 545–551  crossref  isi
    10. С. Н. Попова, “Законы нуля или единицы для случайных графов с вершинами в булевом кубе”, Матем. тр., 19:1 (2016), 106–177  mathnet  crossref  mathscinet  elib; S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75  crossref
    11. А. А. Сагдеев, “О нижних оценках хроматических чисел дистанционных графов с большим обхватом”, Матем. заметки, 101:3 (2017), 430–445  mathnet  crossref  mathscinet  elib; A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth”, Math. Notes, 101:3 (2017), 515–528  crossref  isi
    12. А. А. Сагдеев, “О хроматическом числе пространства с запрещенным правильным симплексом”, Матем. заметки, 102:4 (2017), 579–585  mathnet  crossref  mathscinet  elib; A. Sagdeev, “The Chromatic Number of Space with Forbidden Regular Simplex”, Math. Notes, 102:4 (2017), 541–546  crossref  isi
    13. А. А. Соколов, “О хроматических числах рациональных пространств”, Матем. заметки, 103:1 (2018), 120–128  mathnet  crossref  mathscinet  elib; A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103:1-2 (2018), 111–117  crossref  isi
    14. А. В. Бердников, “Хроматические числа графов расстояний с несколькими запрещенными расстояниями без клик заданного размера”, Пробл. передачи информ., 54:1 (2018), 78–92  mathnet  elib; 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  crossref  isi
    15. Ю. А. Демидович, “Дистанционные графы в рациональном пространстве с большим хроматическим числом и без клик заданного размера”, Матем. заметки, 106:1 (2019), 24–39  mathnet  crossref  elib; 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  crossref  isi
    16. А. А. Сагдеев, “Об одной теореме Франкла–Уилсона”, Пробл. передачи информ., 55:4 (2019), 86–106  mathnet  crossref  elib; A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395  crossref  isi
    17. Sagdeev A.A. Raigorodskii A.M., “On a Frankl-Wilson Theorem and Its Geometric Corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033  mathscinet  isi
    18. Ф. А. Пушняков, А. М. Райгородский, “Оценка числа ребер в особых подграфах некоторого дистанционного графа”, Матем. заметки, 107:2 (2020), 286–298  mathnet  crossref; 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  crossref  isi  elib
  • Математический сборник Sbornik: Mathematics (from 1967)
    Просмотров:
    Эта страница:519
    Полный текст:198
    Литература:60
    Первая стр.:64
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021