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

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

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


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




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

Успехи математических наук, 2025, том 80, выпуск 3(483), страницы 113–176
DOI: https://doi.org/10.4213/rm10233 (Mi rm10233) 		 
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Графы Джонсона, их случайные подграфы и некоторые их экстремальные характеристики

А. М. Райгородскийabcd , П. С. Синельников-Мурылевe

a Московский физико-технический институт (национальный исследовательский университет), кафедра дискретной математики и лаборатория продвинутой комбинаторики и сетевых приложений
b Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
c Кавказский математический центр Адыгейского государственного университета
d Бурятский государственный университет, Институт математики и информатики
e Московский физико-технический институт (национальный исследовательский университет), кафедра дискретной математики
PDF полного текста (1117 kB) Первая страница PDF английской версии (1082 kB) Список цитирования (3)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/rm10233
Аннотация: Одним из очень важных объектов современной теории графов является так называемый граф Джонсона $G(n,r,s)$. Его вершинами служат все $C_n^r$ подмножеств мощности $r$ множества $\{1,\dots,n\}$, а ребром две вершины соединяются тогда и только тогда, когда пересечение соответствующих подмножеств имеет мощность $s$. Такие графы играют огромную роль в теории кодирования, в экстремальной комбинаторике и теории Рамсея, в комбинаторной геометрии и др. В обзоре рассказывается о применениях этих графов и о нескольких их характеристиках, среди которых число независимости, кликовое число и хроматическое число. Также мы уделяем внимание большому и активно развивающемуся в последнее время разделу теории, связанному с рассмотрением случайных подграфов графов Джонсона.
Библиография: 135 названий.
Ключевые слова: графы Джонсона, случайные подграфы, кнезеровские графы, кликовые числа, числа независимости, хроматические числа, числа Рамсея.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации FSMG-2024-0025
Исследование выполнено при поддержке Министерства науки и высшего образования Российской Федерации (госзадание), номер проекта FSMG-2024-0025.
Поступила в редакцию: 06.01.2025
Дата публикации: 05.06.2025
Англоязычная версия:
Russian Mathematical Surveys, 2025, Volume 80, Issue 3, Pages 471–530
DOI: https://doi.org/10.4213/rm10233e
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.1+519.154
MSC: 51M15, 54E35, 51M20, 05C15, 52A20, 52C10
Образец цитирования: А. М. Райгородский, П. С. Синельников-Мурылев, “Графы Джонсона, их случайные подграфы и некоторые их экстремальные характеристики”, УМН, 80:3(483) (2025), 113–176; Russian Math. Surveys, 80:3 (2025), 471–530
Цитирование в формате AMSBIB
\RBibitem{RaiSin25}
\by А.~М.~Райгородский, П.~С.~Синельников-Мурылев
\paper Графы Джонсона, их случайные подграфы и~некоторые их экстремальные характеристики
\jour УМН
\yr 2025
\vol 80
\issue 3(483)
\pages 113--176
\mathnet{http://mi.mathnet.ru/rm10233}
\crossref{https://doi.org/10.4213/rm10233}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2025RuMaS..80..471R}
\transl
\jour Russian Math. Surveys
\yr 2025
\vol 80
\issue 3
\pages 471--530
\crossref{https://doi.org/10.4213/rm10233e}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-105016002777}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm10233
  • https://doi.org/10.4213/rm10233
  • https://www.mathnet.ru/rus/rm/v80/i3/p113
    • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:349
    PDF русской версии:19
    PDF английской версии:361
    HTML русской версии:52
    HTML английской версии:67
    Список литературы:45
    Первая страница:27
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025