Extremal problems in hypergraph colourings

Standard

Extremal problems in hypergraph colourings. / Raigorodskii, A. M.; Cherkashin, D. D.

In: Russian Mathematical Surveys, Vol. 75, No. 1, 02.2020, p. 89-146.

Research output: Contribution to journal › Article › peer-review

Author

Raigorodskii, A. M. ; Cherkashin, D. D. / Extremal problems in hypergraph colourings. In: Russian Mathematical Surveys. 2020 ; Vol. 75, No. 1. pp. 89-146.

BibTeX

@article{ba4bac3a7faf4e4b8e980d2c4b00d0e4,

title = "Extremal problems in hypergraph colourings",

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 Erdos 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 Erdos-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, IMPROVED BOUNDS, PANCHROMATIC COLORINGS, COMBINATORIAL PROBLEM, KO-RADO THEOREM, INTERSECTION-THEOREMS, ERDOS, CHROMATIC NUMBER, UNIFORM HYPERGRAPHS, STEINER TRIPLE-SYSTEMS, INDEPENDENT SETS",

author = "Raigorodskii, {A. M.} and Cherkashin, {D. D.}",

year = "2020",

month = feb,

doi = "10.1070/RM9905",

language = "English",

volume = "75",

pages = "89--146",

journal = "Russian Mathematical Surveys",

issn = "0036-0279",

publisher = "IOP Publishing Ltd.",

number = "1",

}

RIS

TY - JOUR

T1 - Extremal problems in hypergraph colourings

AU - Raigorodskii, A. M.

AU - Cherkashin, D. D.

PY - 2020/2

Y1 - 2020/2

N2 - 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 Erdos 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 Erdos-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.

AB - 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 Erdos 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 Erdos-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.

KW - extremal combinatorics

KW - hypergraph colourings

KW - IMPROVED BOUNDS

KW - PANCHROMATIC COLORINGS

KW - COMBINATORIAL PROBLEM

KW - KO-RADO THEOREM

KW - INTERSECTION-THEOREMS

KW - ERDOS

KW - CHROMATIC NUMBER

KW - UNIFORM HYPERGRAPHS

KW - STEINER TRIPLE-SYSTEMS

KW - INDEPENDENT SETS

UR - http://www.scopus.com/inward/record.url?scp=85084989909&partnerID=8YFLogxK

UR - https://elibrary.ru/item.asp?id=43296662

UR - https://www.mendeley.com/catalogue/5b815e26-1377-3044-b350-013b258442e9/

U2 - 10.1070/RM9905

DO - 10.1070/RM9905

M3 - Article

AN - SCOPUS:85084989909

VL - 75

SP - 89

EP - 146

JO - Russian Mathematical Surveys

JF - Russian Mathematical Surveys

SN - 0036-0279

IS - 1

ER -

ID: 62101574