Raigorodskiĭ, Andreĭ M.; Cherkashin, Danila D. Extremal problems in hypergraph colourings. (English. Russian original) Zbl 1440.05096 Russ. Math. Surv. 75, No. 1, 89-146 (2020); translation from Usp. Mat. Nauk 75, No. 1, 95-154 (2020). Summary: Extremal problems in hypergraph colouring originate implicitly from D. Hilbert’s theorem on monochromatic affine cubes [J. Reine Angew. Math. 110, 104–129 (1892; JFM 24.0398.05)] and B. L. van der Waerden’s theorem on monochromatic arithmetic progressions [Nieuw Arch. Wiskd., II. Ser. 15, 212–216 (1927; JFM 53.0073.12)]. 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 P. Erdős and A. Hajnal [Acta Math. Acad. Sci. Hung. 12, 87–123 (1961; Zbl 0201.32801)] and P. Erdős et al. [Lect. Notes Math. 337, 531–538 (1973; Zbl 0289.04002)]. 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. Cited in 10 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C65 Hypergraphs 05C35 Extremal problems in graph theory 60C05 Combinatorial probability Keywords:extremal combinatorics; hypergraph colourings Citations:Zbl 0201.32801; Zbl 0289.04002; JFM 24.0398.05; JFM 53.0073.12 PDFBibTeX XMLCite \textit{A. M. Raigorodskiĭ} and \textit{D. D. Cherkashin}, Russ. Math. Surv. 75, No. 1, 89--146 (2020; Zbl 1440.05096); translation from Usp. Mat. Nauk 75, No. 1, 95--154 (2020) Full Text: DOI References: [1] H. L. Abbott and D. Hanson 1969 On a combinatorial problem of Erdős Canad. Math. Bull.12 6 823-829 · Zbl 0192.33203 [2] H. L. Abbott and L. Moser 1964 On a combinatorial problem of Erdős and Hajnal Canad. Math. Bull.7 2 177-181 · Zbl 0131.01302 [3] S. Aglave, V. A. Amarnath, S. Shannigrahi, and S. Singh 2020 Improved bounds for uniform hypergraphs without property B Australas. J. Combin.76 1 73-86 · Zbl 1439.05168 [4] M. Ajtai, J. Komlós, J. Pintz, J. Spencer, and E. Szemerédi 1982 Extremal uncrowded hypergraphs J. Combin. Theory Ser. A32 3 321-335 · Zbl 0485.05049 [5] M. Akhmejanova and D. Shabanov 2017 Colorings of \(b\)-simple hypergraphs The European conference on combinatorics, graph theory and applications, EuroComb 2017Vienna 2017 Electron. Notes Discrete Math. 61 Elsevier Science B.V., Amsterdam 29-35 · Zbl 1378.05040 [6] M. Akhmejanova and D. Shabanov Publ. online 2019 Coloring hypergraphs with bounded cardinalities of edge intersections Discrete Math. 111692 11 pp. · Zbl 1433.05109 [7] M. B. Akhmejanova and D. A. Shabanov Publ. online 2019 Equitable colorings of hypergraphs with few edges Discrete Appl. Math. 1-11 · Zbl 1444.05050 [8] И. А. Акользин 2018 О раскрасках 3-однородных гиперграфов в три цвета Геометрия и механика Итоги науки и техн. Сер. Соврем. матем. и ее прил. Темат. обз. 150 ВИНИТИ РАН, М. 26-39 [9] I. A. Akolzin 2018 On 3-homogeneous hypergraph colourings in 3 colours Geometry and mechanics Itogi Nauki Tekh. Ser. Sovrem. Mat. Prilozh. Temat. Obz. 150 VINITI, Moscow 26-39 [10] I. Akolzin and D. Shabanov 2016 Colorings of hypergraphs with large number of colors Discrete Math.339 12 3020-3031 · Zbl 1343.05057 [11] N. Alon 1985 Hypergraphs with high chromatic number Graphs Combin.1 387-389 · Zbl 0609.05054 [12] N. Alon 1992 Choice numbers of graphs: a probabilistic approach Combin. Probab. Comput.1 2 107-114 · Zbl 0793.05076 [13] N. Alon 1993 Restricted colorings of graphs Surveys in combinatorics, 1993Keele London Math. Soc. Lecture Note Ser. 187 Cambridge Univ. Press, Cambridge 1-33 · Zbl 0791.05034 [14] N. Alon, D. J. Kleitman, C. Pomerance, M. Saks, and P. Seymour 1987 The smallest \(n\)-uniform hypergraph with positive discrepancy Combinatorica7 2 151-160 · Zbl 0629.05053 [15] N. Alon and A. Kostochka 2011 Hypergraph list coloring and Euclidean Ramsey theory Random Structures Algorithms39 3 377-390 · Zbl 1232.05146 [16] N. Alon and J. H. Spencer 2016 The probabilistic method Wiley Ser. Discrete Math. Optim. John Wiley & Sons, Inc., Hoboken, NJ 4th ed., xiv+375 pp. [17] N. Alon and V. H. Vũ 1997 Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs J. Combin. Theory Ser. A79 1 133-160 · Zbl 0890.05011 [18] A. Arman and T. Retter 2017 An upper bound for the size of a \(k\)-uniform intersecting family with covering number \(k\) J. Combin. Theory Ser. A147 18-26 · Zbl 1352.05136 [19] J. Balogh, D. Cherkashin, and S. Kiselev 2019 Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs European J. Combin.79 228-236 · Zbl 1414.05107 [20] J. Balogh, S. Eberhard, B. Narayanan, A. Treglown, and A. Z. Wagner 2017 An improved lower bound for Folkman’s theorem Bull. Lond. Math. Soc.49 4 745-747 · Zbl 1375.05263 [21] J. Balogh, M. Lavrov, G. Shakan, and A. Z. Wagner 2019 Monochromatic Hilbert cubes and arithmetic progressions Electron. J. Combin.26 2 2.22 15 pp. [22] J. Balogh, R. Morris, and W. Samotij 2015 Independent sets in hypergraphs J. Amer. Math. Soc.28 3 669-709 · Zbl 1310.05154 [23] J. Balogh, R. Morris, and W. Samotij 2018 The method of hypergraph containers Proceedings of the 2018 International Congress of MathematiciansRio de Janeiro IV World Sci. Publ., Hackensack, NJ 3059-3092 · Zbl 1448.05147 [24] J. Beck 1977 On a combinatorial problem of P. Erdős and L. Lovász Discrete Math.17 2 127-131 · Zbl 0366.05042 [25] J. Beck 1978 On 3-chromatic hypergraphs Discrete Math.24 2 127-137 · Zbl 0429.05055 [26] J. Beck 1980 A remark concerning arithmetic progressions J. Combin. Theory Ser. A29 3 376-379 · Zbl 0461.10045 [27] J. Beck and T. Fiala 1981 “Integer-making” theorems Discrete Appl. Math.3 1 1-8 · Zbl 0473.05046 [28] D. Bednarchak and M. Helm 1997 A note on the Beck-Fiala theorem Combinatorica17 1 147-149 · Zbl 0880.05002 [29] C. Berge 1989 Hypergraphs. Combinatorics of finite sets North-Holland Math. Library 45 North-Holland Publishing Co., Amsterdam x+255 pp. [30] C. Berge and F. Sterboul 1977 Equipartite colorings in graphs and hypergraphs J. Combin. Theory Ser. B22 2 97-113 · Zbl 0353.05035 [31] E. R. Berlekamp 1968 A construction for partitions which avoid long arithmetic progressions Canad. Math. Bull.11 3 409-414 · Zbl 0169.31905 [32] A. Bernshteyn 2019 Measurable versions of the Lovász Local Lemma and measurable graph colorings Adv. Math.353 153-223 · Zbl 1436.05110 [33] A. Bernshteyn, M. Delcourt, H. Towsner, and A. Tserunyan 2019 A short nonalgorithmic proof of the containers theorem for hypergraphs Proc. Amer. Math. Soc.147 4 1739-1749 · Zbl 07020584 [34] F. Bernstein 1907 Zur Theorie der trigonometrischen Reihe J. Reine Angew. Math.1907 132 270-278 · JFM 38.0440.01 [35] T. Blankenship, J. Cummings, and V. Taranchuk 2018 A new lower bound for van der Waerden numbers European J. Combin.69 163-168 · Zbl 1376.05158 [36] T. F. Bloom 2016 A quantitative improvement for Roth’s theorem on arithmetic progressions J. Lond. Math. Soc. (2)93 3 643-663 · Zbl 1364.11024 [37] А. В. Бобу, А. Э. Куприянов 2016 О хроматических числах дистанционных графов, близких к кнезеровским Пробл. передачи информ.52 4 64-83 [38] English transl. A. V. Bobu and A. E. Kupriyanov 2016 On chromatic numbers of close-to-Kneser distance graphs Problems Inform. Transmission52 4 373-390 · Zbl 1367.05065 [39] T. Bohman, A. Frieze, and D. Mubayi 2010 Coloring \(H\)-free hypergraphs Random Structures Algorithms36 1 11-25 · Zbl 1205.05082 [40] B. Bollobás 1978 Chromatic number, girth and maximal degree Discrete Math.24 3 311-314 · Zbl 0395.05034 [41] B. Bollobás and A. D. Scott 2002 Problems and results on judicious partitions Random Structures Algorithms21 3-4 414-430 · Zbl 1013.05059 [42] A. Bretto 2013 Hypergraph theory. An introduction Math. Eng. Springer, Cham xiv+119 pp. · Zbl 1269.05082 [43] T. C. Brown, P. Erdös, F. R. K. Chung, and R. L. Graham 1985 Quantitative forms of a theorem of Hilbert J. Combin. Theory Ser. A38 2 210-216 · Zbl 0577.05007 [44] B. Bukh 2016 An improvement of the Beck-Fiala theorem Combin. Probab. Comput.25 3 380-398 · Zbl 1372.05225 [45] М. И. Бурштейн 1976 Критические гиперграфы с минимальным числом ребер Сообщ. АН ГССР83 2 285-288 [46] M. I. Burshtein 1976 Critical hypergraphs with the minimal number of edges Sakharth. SSR Mecn. Akad. Moambe83 2 285-288 [47] Y. Caro and Z. Tuza 1991 Improved lower bounds on \(k\)-independence J. Graph Theory15 1 99-107 · Zbl 0753.68079 [48] W. Chen, A. Srivastav, and G. Travaglini (eds.) 2014 A panorama of discrepancy theory Lecture Notes in Math. 2107 Springer, Cham xvi+695 pp. · Zbl 1300.11003 [49] D. Cherkashin 2011 On hypergraph cliques with chromatic number 3 Mosc. J. Comb. Number Theory1 3 3-11 · Zbl 1255.05101 [50] D. Cherkashin 2018 Coloring cross-intersecting families Electron. J. Combin.25 1 1.47 9 pp. [51] D. Cherkashin 2018 A note on panchromatic colorings Discrete Math.341 3 652-657 · Zbl 1378.05052 [52] Д. Д. Черкашин 2019 Задача Эрдёша-Хайнала для 3-графов Комбинаторика и теория графов. XI Зап. науч. сем. ПОМИ 488 ПОМИ, СПб. 168-176 [53] English transl. D. Cherkashin 2019 On the Erdős-Hajnal problem in the case of 3-graphs 1905.02893 6 pp. [54] D. D. Cherkashin and J. Kozik 2015 A note on random greedy coloring of uniform hypergraphs Random Structures Algorithms47 3 407-413 · Zbl 1325.05121 [55] D. D. Cherkashin, A. B. Kulikov, and A. M. Raigorodskii 2012 On hypergraph cliques with chromatic number 3 and a given number of vertices Труды МФТИ4 1 151-156 [56] D. Cherkashin and F. Petrov 2019 (v1, 2018) Regular behaviour of the maximal hypergraph chromatic number 1808.01482 8 pp. [57] D. Cherkashin and F. Petrov 2019 On small \(n\)-uniform hypergraphs with positive discrepancy J. Combin. Theory Ser. B139 353-359 · Zbl 1428.05224 [58] C. J. Colbourn and J. H. Dinitz (eds.) 2007 Handbook of combinatorial designs Discrete Math. Appl. (Boca Raton) Chapman & Hall/CRC, Boca Raton, FL 2nd ed., xxii+984 pp. [59] C. J. Colbourn, A. D. Forbes, M. J. Grannell, T. S. Griggs, P. Kaski, P. R. J. Östergård, D. A. Pike, and O. Pottonen 2010 Properties of the Steiner triple systems of order 19 Electron. J. Combin.17 1 98 30 pp. [60] D. Conlon, J. Fox, and B. Sudakov 2014 Short proofs of some extremal results Combin. Probab. Comput.23 1 8-28 · Zbl 1290.05089 [61] Yu. A. Demidovich 2019 On some generalizations of the property \(B\)-problem of an \(n\)-uniform hypergraph 1903.11708 28 pp. [62] M. Deza 1974 Solution d’un problème de Erdős-Lovász J. Combin. Theory Ser. B16 2 166-167 · Zbl 0263.05007 [63] I. Dinur, O. Regev, and C. Smyth 2005 The hardness of 3-uniform hypergraph coloring Combinatorica25 5 519-535 · Zbl 1106.68080 [64] R. A. Duke, H. Lefmann, and V. Rödl 1995 On uncrowded hypergraphs Random Structures Algorithms6 2-3 209-212 · Zbl 0822.05051 [65] L. Duraj, G. Gutowski, and J. Kozik 2018 A note on two-colorability of nonuniform hypergraphs 45th international colloquium on automata, languages, and programming LIPIcs. Leibniz Int. Proc. Inform. 107 Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern 46 13 pp. · Zbl 1504.05202 [66] P. Erdős 1959 Graph theory and probability Canad. J. Math.11 34-38 · Zbl 0084.39602 [67] P. Erdős 1963 On a combinatorial problem Nordisk Mat. Tidskr.11 5-10 · Zbl 0116.01104 [68] P. Erdős 1964 On a combinatorial problem. II Acta Math. Acad. Sci. Hungar.15 445-447 · Zbl 0201.33704 [69] P. Erdős 1969 On a combinatorial problem. III Canad. Math. Bull.12 4 413-416 · Zbl 0199.31801 [70] P. Erdős 1979 Some old and new problems in various branches of combinatorics Proceedings of the 10th southeastern conference on combinatorics, graph theory and computingFlorida Atlantic Univ., Boca Raton, FL 1979 Congress. Numer. XXIII-XXIV Utilitas Math., Winnipeg, MB 19-37 [71] P. Erdős and A. Hajnal 1961 On a property of families of sets Acta Math. Acad. Sci. Hungar.12 87-123 · Zbl 0201.32801 [72] P. Erdős and A. Hajnal 1966 On chromatic number of graphs and set-systems Acta Math. Acad. Sci. Hungar.17 61-99 · Zbl 0151.33701 [73] P. Erdős, C. Ko, and R. Rado 1961 Intersection theorems for systems of finite sets Quart. J. Math. Oxford Ser. (2)12 313-320 · Zbl 0100.01902 [74] P. Erdős and L. Lovász 1975 Problems and results on 3-chromatic hypergraphs and some related questions Infinite and finite setsKeszthely 1973 Colloq. Math. Soc. János Bolyai 10, 2 North-Holland, Amsterdam 609-627 [75] P. Erdős, A. L. Rubin, and H. Taylor 1980 Choosability in graphs Proceedings of the west coast conference on combinatorics, graph theory and computingHumboldt State Univ., Arcata, CA 1979 Congress. Numer. 26 Utilitas Math., Winnipeg, MB 125-157 [76] P. Erdős and J. H. Spencer 1989 Monochromatic sumsets J. Combin. Theory Ser. A50 1 162-163 · Zbl 0666.10036 [77] A. Ferber and A. Shapira 2019 A quantitative Lovász criterion for Property \(B 1903.04968 4\) pp. [78] P. Frankl 1985 On the chromatic number of the general Kneser-graph J. Graph Theory9 2 217-220 · Zbl 0574.05022 [79] P. Frankl 1987 Erdős-Ko-Rado theorem with conditions on the maximal degree J. Combin. Theory Ser. A46 2 252-263 · Zbl 0661.05002 [80] P. Frankl 2019 A near-exponential improvement of a bound of Erdős and Lovász on maximal intersecting families Combin. Probab. Comput.28 5 733-739 · Zbl 1436.05081 [81] P. Frankl and Z. Füredi 1986 Extremal problems concerning Kneser graphs J. Combin. Theory Ser. B40 3 270-284 · Zbl 0564.05002 [82] P. Frankl, K. Ota, and N. Tokushige 1996 Covers in uniform intersecting families and a counterexample to a conjecture of Lovász J. Combin. Theory Ser. A74 1 33-42 · Zbl 0846.05094 [83] P. Frankl and N. Tokushige 2016 Invitation to intersection problems for finite sets J. Combin. Theory Ser. A144 157-211 · Zbl 1343.05153 [84] A. Frieze and D. Mubayi 2013 Coloring simple hypergraphs J. Combin. Theory Ser. B103 6 767-794 [85] H. Gebauer 2013 On the construction of 3-chromatic hypergraphs with few edges J. Combin. Theory Ser. A120 7 1483-1490 · Zbl 1314.05064 [86] J. Gimbel and C. Thomassen 2000 Coloring triangle-free graphs with fixed size Discrete Math.219 1-3 275-277 · Zbl 0948.05027 [87] W. T. Gowers 2001 A new proof of Szemerédi’s theorem Geom. Funct. Anal.11 3 465-588 · Zbl 1028.11005 [88] D. A. Grable, K. T. Phelps, and V. Rödl 1995 The minimum independence number for designs Combinatorica15 2 175-185 · Zbl 0824.05005 [89] D. S. Gunderson and V. Rödl 1998 Extremal problems for affine cubes of integers Combin. Probab. Comput.7 1 65-79 · Zbl 0892.05050 [90] D. S. Gunderson, V. Rödl, and A. Sidorenko 1999 Extremal problems for sets forming Boolean algebras and complete partite hypergraphs J. Combin. Theory Ser. A88 2 342-367 · Zbl 0939.05079 [91] A. Gyárfás and J. Lehel 2011 Trees in greedy colorings of hypergraphs Discrete Math.311 2-3 208-209 · Zbl 1225.05097 [92] A. Hajnal and E. Szemerédi 1970 Proof of a conjecture of P. Erdős Combinatorial theory and its applicationsBalatonfüred 1969 2 North-Holland, Amsterdam 601-623 [93] J. Håstad, S. Jukna, and P. Pudlák 1995 Top-down lower bounds for depth-three circuits Comput. Complexity5 2 99-112 · Zbl 0838.68056 [94] P. Haxell and J. Verstraete 2010 List coloring hypergraphs Electron. J. Combin.17 1 129 12 pp. [95] N. Hegyvári 1999 On the dimension of the Hilbert cubes J. Number Theory77 2 326-330 · Zbl 0989.11012 [96] M. Helm 1999 On the Beck-Fiala theorem Discrete Math.207 1-3 73-87 · Zbl 0934.05013 [97] M. Herzog and J. Schönheim 1972 The \(B_r\) property and chromatic numbers of generalized graphs J. Combin. Theory Ser. B12 1 41-49 · Zbl 0236.05123 [98] D. Hilbert 1892 Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten J. Reine Angew. Math.1892 110 104-129 · JFM 24.0087.03 [99] A. J. W. Hilton and E. C. Milner 1967 Some intersection theorems for systems of finite sets Quart. J. Math. Oxford Ser. (2)18 1 369-384 · Zbl 0168.26205 [100] P. Horak 2005 On the chromatic number of Steiner triple systems of order 25 Discrete Math.299 1-3 120-128 · Zbl 1073.05011 [101] P. Keevash 2011 Hypergraph Turán problems Surveys in combinatorics 2011Exeter, UK London Math. Soc. Lecture Note Ser. 392 Cambridge Univ. Press, Cambridge 83-139 · Zbl 1244.05159 [102] H. A. Kierstead and A. V. Kostochka 2008 An Ore-type theorem on equitable coloring J. Combin. Theory Ser. B98 1 226-234 · Zbl 1127.05039 [103] H. A. Kierstead and A. V. Kostochka 2008 A short proof of the Hajnal-Szemerédi theorem on equitable colouring Combin. Probab. Comput.17 2 265-270 · Zbl 1163.05015 [104] J. H. Kim 1995 On Brooks’ theorem for sparse graphs Combin. Probab. Comput.4 2 97-132 · Zbl 0833.05030 [105] D. J. Kleitman and K. J. Winston 1980 The asymptotic number of lattices Combinatorical mathematics, optimal designs and their applications Ann. Discrete Math. 6 North-Holland Publishing Co., Amsterdam 243-249 · Zbl 0446.06005 [106] D. J. Kleitman and K. J. Winston 1982 On the number of graphs without 4-cycles Discrete Math.41 2 167-172 · Zbl 0491.05035 [107] A. Kostochka 2002 On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs Electron. J. Combin.9 1 9 4 pp. · Zbl 1005.05018 [108] A. Kostochka 2004 Coloring uniform hypergraphs with few colors Random Structures Algorithms24 1 1-10 · Zbl 1031.05051 [109] A. Kostochka 2006 Color-critical graphs and hypergraphs with few edges: a survey More sets, graphs and numbers Bolyai Soc. Math. Stud. 15 Springer, Berlin 175-197 · Zbl 1094.05025 [110] A. V. Kostochka and M. Kumbhat 2009 Coloring uniform hypergraphs with few edges Random Structures Algorithms35 3 348-368 · Zbl 1205.05092 [111] А. В. Косточка, Н. П. Мазурова 1977 Одна оценка в теории раскраски графов Методы дискретного анализа в решении комбинаторных задач 30 Ин-т матем. СО АН СССР, Новосибирск 23-29 [112] A. V. Kostochka and N. P. Mazurova 1977 An estimate in the theory of graph colouring Metody Diskretn. Anal. 30 Institute of Mathematics, Siberian Branch of the Academy of Sciences of the USSR, Novosibirsk 23-29 · Zbl 0424.05027 [113] A. Kostochka, D. Mubayi, V. Rödl, and P. Tetali 2001 On the chromatic number of set systems Random Structures Algorithms19 2 87-98 · Zbl 0984.05073 [114] A. V. Kostochka and V. Rödl 1998 Partial Steiner systems and matchings in hypergraphs Random Structures Algorithms13 3-4 335-347 · Zbl 0959.05079 [115] A. V. Kostochka and V. Rödl 2010 Constructions of sparse uniform hypergraphs with high chromatic number Random Structures Algorithms36 1 46-56 · Zbl 1208.05094 [116] A. V. Kostochka, V. Rödl, and M. Kumbhat 2010 Coloring uniform hypergraphs with small edge degrees Fete of combinatorics and computer science Bolyai Soc. Math. Stud. 20 János Bolyai Math. Soc., Budapest 213-238 · Zbl 1222.05067 [117] A. V. Kostochka and D. R. Woodall 2001 Density conditions for panchromatic colourings of hypergraphs Combinatorica21 4 515-541 · Zbl 0989.05037 [118] J. Kozik 2016 Multipass greedy coloring of simple uniform hypergraphs Random Structures Algorithms48 1 125-146 · Zbl 1330.05071 [119] J. Kozik and D. Shabanov 2016 Improved algorithms for colorings of simple hypergraphs and applications J. Combin. Theory Ser. B116 312-332 · Zbl 1327.05113 [120] A. Kupavskii and D. Shabanov 2018 Colourings of uniform hypergraphs with large girth and applications Combin. Probab. Comput.27 2 245-273 · Zbl 1387.05093 [121] A. Kupavskii and D. Zakharov 2018 Regular bipartite graphs and intersecting families J. Combin. Theory Ser. A155 180-189 · Zbl 1377.05190 [122] H. Levinson and R. Silverman 1979 Generalizations of property \(B 2\) nd international conference on combinatorial mathematicsNew York 1978 Ann. New York Acad. Sci. 319 1 349-353 [123] P.-S. Loh 2009 A note on embedding hypertrees Electron. J. Combin.16 1 18 4 pp. [124] L. Lovász 1970 A generalization of Kónig’s theorem Acta Math. Acad. Sci. Hungar.21 3-4 443-446 · Zbl 0209.55202 [125] L. Lovász 1975 On minimax theorems of combinatorics Mat. Lapok26 3-4 209-264 · Zbl 0397.05040 [126] L. Lu 2008 On a problem of Erdős and Lovász on coloring non-uniform hypergraphs www.people.math.sc.edu/lu/papers/propertyB.pdf 15 pp. [127] K. Majumder and S. Mukherjee 2018 A note on a series of families constructed over the cyclic graph J. Combin. Theory Ser. A157 41-48 · Zbl 1385.05059 [128] J. Mathews, M. K. Panda, and S. Shannigrahi 2015 On the construction of non-2-colorable uniform hypergraphs Discrete Appl. Math.180 181-187 · Zbl 1303.05132 [129] J. Matoušek 1999 Geometric discrepancy. An illustrated guide Algorithms Combin. 18 Springer-Verlag, Berlin xii+288 pp. · Zbl 1197.11092 [130] M. Matsumoto and N. Tokushige 1989 The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families J. Combin. Theory Ser. A52 1 90-97 · Zbl 0734.05085 [131] E. W. Miller 1937 On a property of families of sets C. R. Soc. Sci. Varsovie30 31-38 · JFM 63.0832.01 [132] P. R. J. Östergård 2014 On the minimum size of 4-uniform hypergraphs without property \(B\) Discrete Appl. Math.163 199-204 · Zbl 1282.05173 [133] K. T. Phelps and V. Rödl 1986 Steiner triple systems with minimum independence number Ars Combin.21 167-172 · Zbl 0625.05012 [134] N. Pippenger and M. C. Golumbic 1975 The inducibility of graphs J. Combin. Theory Ser. B19 3 189-203 · Zbl 0332.05119 [135] A. Pluhár 2009 Greedy colorings of uniform hypergraphs Random Structures Algorithms35 2 216-221 · Zbl 1209.05097 [136] J. Radhakrishnan and A. Srinivasan 2000 Improved bounds and algorithms for hypergraph 2-coloring Random Structures Algorithms16 1 4-32 · Zbl 0942.05024 [137] А. М. Райгородский, Д. А. Шабанов 2011 Задача Эрдеша-Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы УМН66 5(401) 109-182 [138] English transl. A. M. Raigorodskii and D. A. Shabanov 2011 The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems Russian Math. Surveys66 5 933-1002 · Zbl 1251.05063 [139] V. Rödl and E. Šinajová 1994 Note on independent sets in Steiner systems Random Structures Algorithms5 1 183-190 · Zbl 0793.05020 [140] А. П. Розовская 2009 О двухцветных раскрасках общего вида для равномерных гиперграфов Докл. РАН429 3 309-311 [141] English transl. A. P. Rozovskaya 2009 On general two-colorings of uniform hypergraphs Dokl. Math.80 3 837-839 · Zbl 1285.05068 [142] А. П. Розовская, Д. А. Шабанов 2010 О правильных раскрасках гиперграфов в предписанные цвета Дискрет. матем.22 3 94-109 [143] English transl. A. P. Rozovskaya and D. A. Shabanov 2010 On proper colourings of hypergraphs using prescribed colours Discrete Math. Appl.20 4 391-409 · Zbl 1216.05037 [144] W. Samotij 2015 Counting independent sets in graphs European J. Combin.48 5-18 · Zbl 1314.05097 [145] D. Saxton and A. Thomason 2012 List colourings of regular hypergraphs Combin. Probab. Comput.21 1-2 315-322 · Zbl 1241.05103 [146] D. Saxton and A. Thomason 2015 Hypergraph containers Invent. Math.201 3 925-992 · Zbl 1320.05085 [147] D. Saxton and A. Thomason 2016 Online containers for hypergraphs, with applications to linear equations J. Combin. Theory Ser. B121 248-283 · Zbl 1348.05142 [148] D. Saxton and A. Thomason 2016 Simple containers for simple hypergraphs Combin. Probab. Comput.25 3 448-459 · Zbl 1372.05151 [149] W. M. Schmidt 1964 Ein kombinatorisches Problem von P. Erdős und A. Hajnal Acta Math. Acad. Sci. Hungar.15 3 373-374 · Zbl 0143.02501 [150] P. D. Seymour 1974 A note on a combinatorial problem of Erdős and Hajnal J. Lond. Math. Soc. (2)8 4 681-682 · Zbl 0288.05001 [151] P. D. Seymour 1974 On the two-colouring of hypergraphs Quart. J. Math. Oxford Ser. (2)25 1 303-311 · Zbl 0299.05122 [152] Д. А. Шабанов 2004 Об одной комбинаторной задаче Эрдёша Докл. РАН396 2 166-169 [153] English transl. Д. А. Шабанов 2004 On one combinatorial problem of Erdős D. A. Shabanov69 3 359-362 [154] Д. А. Шабанов 2007 Экстремальные задачи для раскрасок равномерных гиперграфов Изв. РАН. Сер. матем.71 6 183-222 [155] English transl. D. A. Shabanov 2007 Extremal problems for colourings of uniform hypergraphs Izv. Math.71 6 1253-1290 · Zbl 1247.05116 [156] Д. А. Шабанов 2008 Рандомизированные алгоритмы раскрасок гиперграфов Матем. сб.199 7 139-160 [157] English transl. D. A. Shabanov 2008 Randomized algorithms for colourings of hypergraphs Sb. Math.199 7 1089-1110 · Zbl 1257.05046 [158] Д. А. Шабанов 2009 О хроматическом числе конечных систем подмножеств Матем. заметки85 6 951-954 [159] English transl. D. A. Shabanov 2009 On the chromatic number of finite systems of subsets Math. Notes85 6 902-905 · Zbl 1191.05044 [160] Д. А. Шабанов 2009 Об улучшении нижней оценки в комбинаторной задаче Эрдёша-Хайнала Докл. РАН426 2 177-178 [161] English transl. D. A. Shabanov 2009 Improvement of the lower bound in the Erdős-Hajnal combinatorial problem Dokl. Math.79 3 349-350 · Zbl 1281.05099 [162] Д. А. Шабанов 2010 О существовании полноцветных раскрасок для равномерных гиперграфов Матем. сб.201 4 137-160 [163] English transl. D. A. Shabanov 2010 The existence of panchromatic colourings for uniform hypergraphs Sb. Math.201 4 607-630 · Zbl 1221.05163 [164] D. A. Shabanov 2011 On a generalization of Rubin’s theorem J. Graph Theory67 3 226-234 · Zbl 1232.05081 [165] D. A. Shabanov 2012 On \(r\)-chromatic hypergraphs Discrete Math.312 2 441-458 · Zbl 1238.05187 [166] D. A. Shabanov 2012 Random coloring method in the combinatorial problem of Erdős and Lovász Random Structures Algorithms40 2 227-253 · Zbl 1241.05104 [167] D. A. Shabanov 2014 Coloring non-uniform hypergraphs without short cycles Graphs Combin.30 5 1249-1260 · Zbl 1298.05134 [168] D. A. Shabanov 2015 Around Erdős-Lovász problem on colorings of non-uniform hypergraphs Discrete Math.338 11 1976-1981 · Zbl 1314.05144 [169] D. A. Shabanov 2015 Equitable two-colorings of uniform hypergraphs European J. Combin.43 185-203 · Zbl 1301.05244 [170] I. Shirgazina 2015 Equitable colorings of non-uniform simple hypergraphs The eight European conference on combinatorics, graph theory and applications, EuroComb 2015Bergen 2015 Electron. Notes Discrete Math. 49 Elsevier Science B.V., Amsterdam 699-703 · Zbl 1346.05084 [171] И. Р. Ширгазина 2016 Справедливые раскраски неоднородных гиперграфов Матем. заметки99 3 441-456 [172] English transl. I. R. Shirgazina 2016 Equitable colorings of nonuniform hypergraphs Math. Notes99 3 444-456 · Zbl 1347.05080 [173] A. Sidorenko 1995 What we know and what we do not know about Turán numbers Graphs Combin.11 2 179-199 · Zbl 0839.05050 [174] A. Sidorenko 1997 Upper bounds for Turán numbers J. Combin. Theory Ser. A77 1 134-147 · Zbl 0873.05003 [175] J. Spencer 1981 Coloring \(n\)-sets red and blue J. Combin. Theory Ser. A30 1 112-113 · Zbl 0448.05032 [176] F. Sterboul 1977 An extremal problem in hypergraph coloring J. Combin. Theory Ser. B22 2 159-164 · Zbl 0352.05034 [177] Z. Szabó 1990 An application of Lovász’ local lemma — a new lower bound for the van der Waerden number Random Structures Algorithms1 3 343-360 · Zbl 0723.05115 [178] В. А. Ташкинов 2004 О нижней границе для хроматического числа графов с заданными максимальной степенью вершин и обхватом Сиб. электрон. матем. изв.1 99-109 [179] V. A. Tashkinov 2004 On the lower bound for the chromatic number of graphs with given maximal degree and girth Sib.Èlektron. Mat. Izv.1 99-109 · Zbl 1076.05038 [180] A. D. Taylor 1981 Bounds for the disjoint unions theorem J. Combin. Theory Ser. A30 3 339-344 · Zbl 0468.05058 [181] B. Toft 1975 On color-critical hypergraphs Infinite and finite setsKeszthely 1973 Colloq. Math. Soc. János Bolyai 10, III North Holland, Amsterdam 1445-1457 [182] B. L. van der Waerden 1927 Beweis einer Baudetschen Vermutung Nieuw Arch. Wisk.15 212-216 · JFM 53.0073.12 [183] В. Г. Визинг 1976 Раскраска вершин графа в предписанные цвета Методы дискретного анализа в теории кодов и схем 29 Ин-т матем. СО АН СССР, Новосибирск 3-10 [184] V. G. Vizing 1976 Colouring the vertices of a graph in prescribed colors Metody Diskretn. Anal. 29 Institute of Mathematics, Siberian Branch of the Academy of Sciences of the USSR, Novosibirsk 3-10 [185] D. R. Woodall 1972 Property B and the four-color problem CombinatoricsMath. Inst., Oxford 1972 Inst. Math. Appl., Southend-on-Sea 322-340 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.