Uspekhi Matematicheskikh Nauk
General information
Latest issue
Impact factor
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Uspekhi Mat. Nauk:

Personal entry:
Save password
Forgotten password?

Uspekhi Mat. Nauk, 2020, Volume 75, Issue 1(451), Pages 95–154 (Mi umn9905)  

This article is cited in 5 scientific papers (total in 5 papers)

Extremal problems in hypergraph colourings

A. M. Raigorodskiiabcd, D. D. Cherkashinefg

a Moscow Institute of Physics and Technology (National Research University)
b Lomonosov Moscow State University
c Caucasus Mathematical Center, Adyghe State University
d Banzarov Buryat State University, Institute of Mathematics and Computer Science
e Chebyshev Laboratory, St. Petersburg State University
f Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (National Research University)
g National Research University Higher School of Economics (St. Petersburg campus)

Abstract: Extremal problems in hypergraph colouring originate implicitly from Hilbert's theorem on monochromatic affine cubes (1892) and van der Waerden's theorem on monochromatic arithmetic progressions (1927). Later, with the advent and elaboration of Ramsey theory, the variety of problems related to colouring of explicitly specified hypergraphs widened rapidly. However, a systematic study of extremal problems on hypergraph colouring was initiated only in the works of Erdős and Hajnal in the 1960s. This paper is devoted to problems of finding edge-minimum hypergraphs belonging to particular classes of hypergraphs, variations of these problems, and their applications. The central problem of this kind is the Erdős–Hajnal problem of finding the minimum number of edges in an $n$-uniform hypergraph with chromatic number at least three. The main purpose of this survey is to spotlight the progress in this area over the last several years.
Bibliography: 168 titles.

Keywords: extremal combinatorics, hypergraph colourings.

Funding Agency Grant Number
Russian Science Foundation 16-11-10014
This work was supported by the Russian Science Foundation (project no. 16-11-10014).


Full text: PDF file (1027 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 2020, 75:1, 89–146

Bibliographic databases:

UDC: 519.17+519.212.2
MSC: 05C15, 05C35, 60C05
Received: 24.07.2019

Citation: A. M. Raigorodskii, D. D. Cherkashin, “Extremal problems in hypergraph colourings”, Uspekhi Mat. Nauk, 75:1(451) (2020), 95–154; Russian Math. Surveys, 75:1 (2020), 89–146

Citation in format AMSBIB
\by A.~M.~Raigorodskii, D.~D.~Cherkashin
\paper Extremal problems in hypergraph colourings
\jour Uspekhi Mat. Nauk
\yr 2020
\vol 75
\issue 1(451)
\pages 95--154
\jour Russian Math. Surveys
\yr 2020
\vol 75
\issue 1
\pages 89--146

Linking options:

    SHARE: FaceBook Twitter Livejournal

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

    This publication is cited in the following articles:
    1. A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “A Generalization of Kneser Graphs”, Math. Notes, 107:3 (2020), 392–403  mathnet  crossref  crossref  mathscinet  isi
    2. Yu. A. Demidovich, “2-Colorings of Hypergraphs with Large Girth”, Math. Notes, 108:2 (2020), 188–200  mathnet  crossref  crossref  mathscinet  isi  elib
    3. Yu. A. Demidovich, “Novaya nizhnyaya otsenka naimenshego chisla reber prostogo odnorodnogo gipergrafa bez svoistva $B_k$”, Diskret. matem., 32:4 (2020), 10–37  mathnet  crossref  mathscinet
    4. Cherkashin D. Petrov F., “Regular Behavior of the Maximal Hypergraph Chromatic Number”, SIAM Discret. Math., 34:2 (2020), 1326–1333  crossref  mathscinet  zmath  isi
    5. P. A. Ogarok, A. M. Raigorodskii, “Ob ustoichivosti chisla nezavisimosti nekotorogo distantsionnogo grafa”, Probl. peredachi inform., 56:4 (2020), 50–63  mathnet  crossref
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:368
    First page:57

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021