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

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

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



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






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


УМН, 2011, том 66, выпуск 5(401), страницы 109–182 (Mi umn9443)  

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

Задача Эрдеша–Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы

А. М. Райгородскийab, Д. А. Шабановab

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

Аннотация: Экстремальные задачи, посвященные раскраскам гиперграфов, впервые возникли в связи с классическими работами 20–30-х годов XX века, положившими начало теории Рамсея. С тех пор данная область исследований занимает одно из центральных мест в экстремальной комбинаторике. Настоящий обзор посвящен одной известной задаче о раскраске гиперграфа – задаче Эрдеша–Хайнала, впервые поставленной в 1961 г. Из этой проблемы выросло целое направление в теории гиперграфов, результаты и методы которого находят широкое применение в различных областях дискретной математики.
Библиография: 109 названий.

Ключевые слова: гиперграф, раскраски гиперграфов, хроматическое число, экстремальная теория множеств.

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

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

Англоязычная версия:
Russian Mathematical Surveys, 2011, 66:5, 933–1002

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

Тип публикации: Статья
УДК: 519.112.7+519.174+519.179.1
MSC: 05C15, 05C35, 05C65
Поступила в редакцию: 01.11.2010

Образец цитирования: А. М. Райгородский, Д. А. Шабанов, “Задача Эрдеша–Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы”, УМН, 66:5(401) (2011), 109–182; Russian Math. Surveys, 66:5 (2011), 933–1002

Цитирование в формате AMSBIB
\RBibitem{RaiSha11}
\by А.~М.~Райгородский, Д.~А.~Шабанов
\paper Задача Эрдеша--Хайнала о~раскрасках~гиперграфов, ее обобщения и~смежные проблемы
\jour УМН
\yr 2011
\vol 66
\issue 5(401)
\pages 109--182
\mathnet{http://mi.mathnet.ru/umn9443}
\crossref{https://doi.org/10.4213/rm9443}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2919273}
\zmath{https://zbmath.org/?q=an:1251.05063}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2011RuMaS..66..933R}
\elib{http://elibrary.ru/item.asp?id=20423298}
\transl
\jour Russian Math. Surveys
\yr 2011
\vol 66
\issue 5
\pages 933--1002
\crossref{https://doi.org/10.1070/RM2011v066n05ABEH004764}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000298661300003}
\elib{http://elibrary.ru/item.asp?id=18033912}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84855925923}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn9443
  • https://doi.org/10.4213/rm9443
  • http://mi.mathnet.ru/rus/umn/v66/i5/p109

    ОТПРАВИТЬ: 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. Райгородский А.М., “Избранные задачи комбинаторной геометрии и теории графов”, Тр. Московского физико-технического института, 3:4 (2011), 127–139  elib
    2. Шабанов Д.А., “Об одном обобщении задачи Эрдеша-Ловаса”, Тр. Московского физико-технического института, 4:1(13) (2012), 131–140  elib
    3. Тепляков С.М., “Рекуррентные верхние оценки в задаче Эрдеша-Хайнала о раскраске гиперграфа и в ее обобщениях”, Тр. Московского физико-технического института, 4:1(13) (2012), 141–150  elib
    4. Райгородский А.М., “Предисловие редактора номера”, Тр. Московского физико-технического института, 4:1(13) (2012), 4–11  elib
    5. С. М. Тепляков, “Верхняя оценка в задаче Эрдеша–Хайнала о раскраске гиперграфа”, Матем. заметки, 93:1 (2013), 148–151  mathnet  crossref  mathscinet  zmath  elib; S. M. Teplyakov, “Upper Bound in the Erdős–Hajnal Problem of Hypergraph Coloring”, Math. Notes, 93:1 (2013), 191–195  crossref  isi  elib
    6. Д. А. Шабанов, “Функция Ван-дер-Вардена и раскраски гиперграфов с большим обхватом”, Докл. РАН, 451:6 (2013), 620–624  crossref  mathscinet  zmath  elib; D. A. Shabanov, “Van der Waerden function and colorings of hypergraphs with large girth”, Dokl. Math., 88:1 (2013), 473–477  crossref  mathscinet  zmath  isi  elib  scopus
    7. И. А. Акользин, “О задаче Эрдеша–Хайнала для $3$-однородных гиперграфов”, Матем. заметки, 94:6 (2013), 933–935  mathnet  crossref  mathscinet  zmath  elib; I. A. Akolzin, “On the Erdős–Hajnal Problem for $3$-Uniform Hypergraphs”, Math. Notes, 94:6 (2013), 951–953  crossref  isi  elib
    8. Л. И. Боголюбский, А. С. Гусев, М. М. Пядеркин, А. М. Райгородский, “Числа независимости и хроматические числа случайных подграфов в некоторых последовательностях графов”, Докл. РАН, 457:4 (2014), 383–387  crossref  mathscinet  zmath  elib; L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs”, Dokl. Math., 90:1 (2014), 462–465  crossref  mathscinet  zmath  isi  elib  scopus
    9. А. В. Лебедева, “Об алгоритмических методах исследования двухцветных раскрасок гиперграфов”, Фундамент. и прикл. матем., 19:2 (2014), 125–149  mathnet  mathscinet; A. V. Lebedeva, “On algorithmic methods of analysis of two-colorings of hypergraphs”, J. Math. Sci., 213:2 (2016), 211–229  crossref
    10. Д. А. Шабанов, “Об обобщении теоремы Хайнала–Семереди для однородных гиперграфов”, Докл. РАН, 459:1 (2014), 22–26  crossref  mathscinet  zmath  elib; D. A. Shabanov, “A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs”, Dokl. Math., 90:3 (2014), 671  crossref  mathscinet  zmath  isi  elib  scopus
    11. D. A. Shabanov, “Around Erdős–Lovász problem on colorings of non-uniform hypergraphs”, Discrete Math., 338:11 (2015), 1976–1981  crossref  mathscinet  zmath  isi  elib  scopus
    12. А. Э. Хузиева, Д. А. Шабанов, “Об однородных гиперграфах с большим обхватом и большим хроматическим числом”, Дискрет. матем., 27:2 (2015), 112–133  mathnet  crossref  mathscinet  elib; A. E. Khuzieva, D. A. Shabanov, “On regular hypergraphs with high girth and high chromatic number”, Discrete Math. Appl., 25:5 (2015), 277–294  crossref  isi
    13. А. Э. Хузиева, Д. А. Шабанов, “Количественные оценки характеристик в гиперграфах с большим обхватом и большим хроматическим числом”, Матем. заметки, 98:6 (2015), 948–951  mathnet  crossref  mathscinet  elib; A. E. Khuzieva, D. A. Shabanov, “Quantitative Estimates of Characteristics for Hypergraphs of Large Girth and Large Chromatic Number”, Math. Notes, 98:6 (2015), 995–998  crossref  isi
    14. Cherkashin D.D., Kozik J., “a Note on Random Greedy Coloring of Uniform Hypergraphs”, 47, no. 3, 2015, 407–413  crossref  mathscinet  zmath  isi
    15. И. Р. Ширгазина, “Справедливые раскраски неоднородных гиперграфов”, Матем. заметки, 99:3 (2016), 441–456  mathnet  crossref  mathscinet  elib; I. R. Shirgazina, “Equitable Colorings of Nonuniform Hypergraphs”, Math. Notes, 99:3 (2016), 444–456  crossref  isi
    16. Kozik J., “Multipass Greedy Coloring of Simple Uniform Hypergraphs”, 48, no. 1, 2016, 125–146  crossref  mathscinet  zmath  isi
    17. Kozik J., Shabanov D., “Improved Algorithms For Colorings of Simple Hypergraphs and Applications”, 116, 2016, 312–332  crossref  mathscinet  zmath  isi
    18. Ю. А. Демидович, А. М. Райгородский, “Двухцветные раскраски однородных гиперграфов”, Матем. заметки, 100:4 (2016), 623–626  mathnet  crossref  mathscinet  elib; Yu. A. Demidovich, A. M. Raigorodskii, “2-Colorings of Uniform Hypergraphs”, Math. Notes, 100:4 (2016), 629–632  crossref  isi
    19. Akolzin I., Shabanov D., “Colorings of hypergraphs with large number of colors”, Discrete Math., 339:12 (2016), 3020–3031  crossref  mathscinet  zmath  isi  elib  scopus
    20. Wang L., Egorova E.K., Mokryakov A.V., “Development of Hypergraph Theory”, J. Comput. Syst. Sci. Int., 57:1 (2018), 109–114  crossref  zmath  isi
  • Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:1261
    Полный текст:438
    Литература:49
    Первая стр.:52

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019