Extremal problems in hypergraph colourings

Cover Page
  • Authors: Raigorodskii A.M.1,2,3,4, Cherkashin D.D.5,6,7
  • Affiliations:
    1. Moscow Institute of Physics and Technology (National Research University)
    2. Lomonosov Moscow State University
    3. Caucasus Mathematical Center, Adyghe State University
    4. Buryat State University, Institute for Mathematics and Informatics
    5. Chebyshev Laboratory, St. Petersburg State University, Department of Mathematics and Mechanics
    6. Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University)
    7. National Research University "Higher School of Economics", St. Petersburg Branch
  • Issue: Vol 75, No 1 (2020)
  • Pages: 95-154
  • Section: Articles
  • URL: https://journals.rcsi.science/0042-1316/article/view/133589
  • DOI: https://doi.org/10.4213/rm9905
  • ID: 133589

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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.

About the authors

Andrei Mikhailovich Raigorodskii

Moscow Institute of Physics and Technology (National Research University); Lomonosov Moscow State University; Caucasus Mathematical Center, Adyghe State University; Buryat State University, Institute for Mathematics and Informatics

Email: mraigor@yandex.ru
Doctor of physico-mathematical sciences

Danila Dmitrievich Cherkashin

Chebyshev Laboratory, St. Petersburg State University, Department of Mathematics and Mechanics; Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University); National Research University "Higher School of Economics", St. Petersburg Branch

Email: matelk@mail.ru
without scientific degree, no status

References

  1. H. L. Abbott, D. Hanson, “On a combinatorial problem of Erdős”, Canad. Math. Bull., 12:6 (1969), 823–829
  2. H. L. Abbott, L. Moser, “On a combinatorial problem of Erdős and Hajnal”, Canad. Math. Bull., 7:2 (1964), 177–181
  3. S. Aglave, V. A. Amarnath, S. Shannigrahi, S. Singh, “Improved bounds for uniform hypergraphs without property B”, Australas. J. Combin., 76:1 (2020), 73–86
  4. M. Ajtai, J. Komlos, J. Pintz, J. Spencer, E. Szemeredi, “Extremal uncrowded hypergraphs”, J. Combin. Theory Ser. A, 32:3 (1982), 321–335
  5. M. Akhmejanova, D. Shabanov, “Colorings of $b$-simple hypergraphs”, The European conference on combinatorics, graph theory and applications, EuroComb 2017 (Vienna, 2017), Electron. Notes Discrete Math., 61, Elsevier Science B.V., Amsterdam, 2017, 29–35
  6. M. Akhmejanova, D. Shabanov, “Coloring hypergraphs with bounded cardinalities of edge intersections”, Discrete Math., Publ. online 2019, 111692, 11 pp.
  7. M. B. Akhmejanova, D. A. Shabanov, “Equitable colorings of hypergraphs with few edges”, Discrete Appl. Math., Publ. online 2019, 1–11
  8. И. А. Акользин, “О раскрасках 3-однородных гиперграфов в три цвета”, Геометрия и механика, Итоги науки и техн. Сер. Соврем. матем. и ее прил. Темат. обз., 150, ВИНИТИ РАН, М., 2018, 26–39
  9. I. Akolzin, D. Shabanov, “Colorings of hypergraphs with large number of colors”, Discrete Math., 339:12 (2016), 3020–3031
  10. N. Alon, “Hypergraphs with high chromatic number”, Graphs Combin., 1 (1985), 387–389
  11. N. Alon, “Choice numbers of graphs: a probabilistic approach”, Combin. Probab. Comput., 1:2 (1992), 107–114
  12. N. Alon, “Restricted colorings of graphs”, Surveys in combinatorics, 1993 (Keele), London Math. Soc. Lecture Note Ser., 187, Cambridge Univ. Press, Cambridge, 1993, 1–33
  13. N. Alon, D. J. Kleitman, C. Pomerance, M. Saks, P. Seymour, “The smallest $n$-uniform hypergraph with positive discrepancy”, Combinatorica, 7:2 (1987), 151–160
  14. N. Alon, A. Kostochka, “Hypergraph list coloring and Euclidean Ramsey theory”, Random Structures Algorithms, 39:3 (2011), 377–390
  15. N. Alon, J. H. Spencer, The probabilistic method, Wiley Ser. Discrete Math. Optim., 4th ed., John Wiley & Sons, Inc., Hoboken, NJ, 2016, xiv+375 pp.
  16. N. Alon, V. H. Vũ, “Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs”, J. Combin. Theory Ser. A, 79:1 (1997), 133–160
  17. A. Arman, T. Retter, “An upper bound for the size of a $k$-uniform intersecting family with covering number $k$”, J. Combin. Theory Ser. A, 147 (2017), 18–26
  18. J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236
  19. J. Balogh, S. Eberhard, B. Narayanan, A. Treglown, A. Z. Wagner, “An improved lower bound for Folkman's theorem”, Bull. Lond. Math. Soc., 49:4 (2017), 745–747
  20. J. Balogh, M. Lavrov, G. Shakan, A. Z. Wagner, “Monochromatic Hilbert cubes and arithmetic progressions”, Electron. J. Combin., 26:2 (2019), 2.22, 15 pp.
  21. J. Balogh, R. Morris, W. Samotij, “Independent sets in hypergraphs”, J. Amer. Math. Soc., 28:3 (2015), 669–709
  22. J. Balogh, R. Morris, W. Samotij, “The method of hypergraph containers”, Proceedings of the International Congress of Mathematicians – 2018 (Rio de Janeiro), v. IV, World Sci. Publ., Hackensack, NJ, 2018, 3059–3092
  23. J. Beck, “On a combinatorial problem of P. Erdős and L. Lovasz”, Discrete Math., 17:2 (1977), 127–131
  24. J. Beck, “On 3-chromatic hypergraphs”, Discrete Math., 24:2 (1978), 127–137
  25. J. Beck, “A remark concerning arithmetic progressions”, J. Combin. Theory Ser. A, 29:3 (1980), 376–379
  26. J. Beck, T. Fiala, “ ‘Integer-making’ theorems”, Discrete Appl. Math., 3:1 (1981), 1–8
  27. D. Bednarchak, M. Helm, “A note on the Beck–Fiala theorem”, Combinatorica, 17:1 (1997), 147–149
  28. C. Berge, Hypergraphs. Combinatorics of finite sets, North-Holland Math. Library, 45, North-Holland Publishing Co., Amsterdam, 1989, x+255 pp.
  29. C. Berge, F. Sterboul, “Equipartite colorings in graphs and hypergraphs”, J. Combin. Theory Ser. B, 22:2 (1977), 97–113
  30. E. R. Berlekamp, “A construction for partitions which avoid long arithmetic progressions”, Canad. Math. Bull., 11:3 (1968), 409–414
  31. A. Bernshteyn, “Measurable versions of the Lovasz Local Lemma and measurable graph colorings”, Adv. Math., 353 (2019), 153–223
  32. A. Bernshteyn, M. Delcourt, H. Towsner, A. Tserunyan, “A short nonalgorithmic proof of the containers theorem for hypergraphs”, Proc. Amer. Math. Soc., 147:4 (2019), 1739–1749
  33. F. Bernstein, “Zur Theorie der trigonometrischen Reihe”, J. Reine Angew. Math., 1907:132 (1907), 270–278
  34. T. Blankenship, J. Cummings, V. Taranchuk, “A new lower bound for van der Waerden numbers”, European J. Combin., 69 (2018), 163–168
  35. T. F. Bloom, “A quantitative improvement for {R}oth's theorem on arithmetic progressions”, J. Lond. Math. Soc. (2), 93:3 (2016), 643–663
  36. А. В. Бобу, А. Э. Куприянов, “О хроматических числах дистанционных графов, близких к кнезеровским”, Пробл. передачи информ., 52:4 (2016), 64–83
  37. T. Bohman, A. Frieze, D. Mubayi, “Coloring $H$-free hypergraphs”, Random Structures Algorithms, 36:1 (2010), 11–25
  38. B. Bollobas, “Chromatic number, girth and maximal degree”, Discrete Math., 24:3 (1978), 311–314
  39. B. Bollobas, A. D. Scott, “Problems and results on judicious partitions”, Random Structures Algorithms, 21:3-4 (2002), 414–430
  40. A. Bretto, Hypergraph theory. An introduction, Math. Eng., Springer, Cham, 2013, xiv+119 pp.
  41. T. C. Brown, P. Erdös, F. R. K. Chung, R. L. Graham, “Quantitative forms of a theorem of Hilbert”, J. Combin. Theory Ser. A, 38:2 (1985), 210–216
  42. B. Bukh, “An improvement of the Beck–Fiala theorem”, Combin. Probab. Comput., 25:3 (2016), 380–398
  43. М. И. Бурштейн, “Критические гиперграфы с минимальным числом ребер”, Сообщ. АН ГССР, 83:2 (1976), 285–288
  44. Y. Caro, Z. Tuza, “Improved lower bounds on $k$-independence”, J. Graph Theory, 15:1 (1991), 99–107
  45. W. Chen, A. Srivastav, G. Travaglini (eds.), A panorama of discrepancy theory, Lecture Notes in Math., 2107, Springer, Cham, 2014, xvi+695 pp.
  46. D. Cherkashin, “On hypergraph cliques with chromatic number 3”, Mosc. J. Comb. Number Theory, 1:3 (2011), 3–11
  47. D. Cherkashin, “Coloring cross-intersecting families”, Electron. J. Combin., 25:1 (2018), 1.47, 9 pp.
  48. D. Cherkashin, “A note on panchromatic colorings”, Discrete Math., 341:3 (2018), 652–657
  49. Д. Д. Черкашин, “Задача Эрдeша–Хайнала для 3-графов”, Комбинаторика и теория графов. XI, Зап. науч. сем. ПОМИ, 488, ПОМИ, СПб., 2019, 168–176
  50. D. D. Cherkashin, J. Kozik, “A note on random greedy coloring of uniform hypergraphs”, Random Structures Algorithms, 47:3 (2015), 407–413
  51. D. D. Cherkashin, A. B. Kulikov, A. M. Raigorodskii, “On hypergraph cliques with chromatic number 3 and a given number of vertices”, Труды МФТИ, 4:1 (2012), 151–156
  52. D. Cherkashin, F. Petrov, Regular behaviour of the maximal hypergraph chromatic number, 2019 (v1 – 2018), 8 pp.
  53. D. Cherkashin, F. Petrov, “On small $n$-uniform hypergraphs with positive discrepancy”, J. Combin. Theory Ser. B, 139 (2019), 353–359
  54. C. J. Colbourn, J. H. Dinitz (eds.), Handbook of combinatorial designs, Discrete Math. Appl. (Boca Raton), 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2007, xxii+984 pp.
  55. C. J. Colbourn, A. D. Forbes, M. J. Grannell, T. S. Griggs, P. Kaski, P. R. J. Östergard, D. A. Pike, O. Pottonen, “Properties of the Steiner triple systems of order 19”, Electron. J. Combin., 17:1 (2010), 98, 30 pp.
  56. D. Conlon, J. Fox, B. Sudakov, “Short proofs of some extremal results”, Combin. Probab. Comput., 23:1 (2014), 8–28
  57. Yu. A. Demidovich, On some generalizations of the property $B$-problem of an $n$-uniform hypergraph, 2019, 28 pp.
  58. M. Deza, “Solution d'un problème de Erdős–Lovasz”, J. Combin. Theory Ser. B, 16:2 (1974), 166–167
  59. I. Dinur, O. Regev, C. Smyth, “The hardness of 3-uniform hypergraph coloring”, Combinatorica, 25:5 (2005), 519–535
  60. R. A. Duke, H. Lefmann, V. Rödl, “On uncrowded hypergraphs”, Random Structures Algorithms, 6:2-3 (1995), 209–212
  61. L. Duraj, G. Gutowski, J. Kozik, “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, 2018, 46, 13 pp.
  62. P. Erdős, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38
  63. P. Erdős, “On a combinatorial problem”, Nordisk Mat. Tidskr., 11 (1963), 5–10
  64. P. Erdős, “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar., 15 (1964), 445–447
  65. P. Erd{ő}s, “On a combinatorial problem. III”, Canad. Math. Bull., 12:4 (1969), 413–416
  66. P. Erdős, “Some old and new problems in various branches of combinatorics”, Proceedings of the 10th southeastern conference on combinatorics, graph theory and computing (Florida Atlantic Univ., Boca Raton, FL, 1979), Congress. Numer., XXIII–XXIV, Utilitas Math., Winnipeg, MB, 1979, 19–37
  67. P. Erdős, A. Hajnal, “On a property of families of sets”, Acta Math. Acad. Sci. Hungar., 12 (1961), 87–123
  68. P. Erdős, A. Hajnal, “On chromatic number of graphs and set-systems”, Acta Math. Acad. Sci. Hungar., 17 (1966), 61–99
  69. P. Erdős, C. Ko, R. Rado, “Intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 12 (1961), 313–320
  70. P. Erdős, L. Lovasz, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and finite sets (Keszthely, 1973), v. 2, Colloq. Math. Soc. Janos Bolyai, 10, North-Holland, Amsterdam, 1975, 609–627
  71. P. Erdős, A. L. Rubin, H. Taylor, “Choosability in graphs”, Proceedings of the west coast conference on combinatorics, graph theory and computing (Humboldt State Univ., Arcata, CA, 1979), Congress. Numer., 26, Utilitas Math., Winnipeg, MB, 1980, 125–157
  72. P. Erdős, J. H. Spencer, “Monochromatic sumsets”, J. Combin. Theory Ser. A, 50:1 (1989), 162–163
  73. A. Ferber, A. Shapira, A quantitative Lovasz criterion for Property $B$, 2019, 4 pp.
  74. P. Frankl, “On the chromatic number of the general Kneser-graph”, J. Graph Theory, 9:2 (1985), 217–220
  75. P. Frankl, “Erdős–Ko–Rado theorem with conditions on the maximal degree”, J. Combin. Theory Ser. A, 46:2 (1987), 252–263
  76. P. Frankl, “A near-exponential improvement of a bound of Erdős and Lovasz on maximal intersecting families”, Combin. Probab. Comput., 28:5 (2019), 733–739
  77. P. Frankl, Z. Füredi, “Extremal problems concerning Kneser graphs”, J. Combin. Theory Ser. B, 40:3 (1986), 270–284
  78. P. Frankl, K. Ota, N. Tokushige, “Covers in uniform intersecting families and a counterexample to a conjecture of Lovasz”, J. Combin. Theory Ser. A, 74:1 (1996), 33–42
  79. P. Frankl, N. Tokushige, “Invitation to intersection problems for finite sets”, J. Combin. Theory Ser. A, 144 (2016), 157–211
  80. A. Frieze, D. Mubayi, “Coloring simple hypergraphs”, J. Combin. Theory Ser. B, 103:6 (2013), 767–794
  81. H. Gebauer, “On the construction of 3-chromatic hypergraphs with few edges”, J. Combin. Theory Ser. A, 120:7 (2013), 1483–1490
  82. J. Gimbel, C. Thomassen, “Coloring triangle-free graphs with fixed size”, Discrete Math., 219:1-3 (2000), 275–277
  83. W. T. Gowers, “A new proof of Szemeredi's theorem”, Geom. Funct. Anal., 11:3 (2001), 465–588
  84. D. A. Grable, K. T. Phelps, V. Rödl, “The minimum independence number for designs”, Combinatorica, 15:2 (1995), 175–185
  85. D. S. Gunderson, V. Rödl, “Extremal problems for affine cubes of integers”, Combin. Probab. Comput., 7:1 (1998), 65–79
  86. D. S. Gunderson, V. Rödl, A. Sidorenko, “Extremal problems for sets forming Boolean algebras and complete partite hypergraphs”, J. Combin. Theory Ser. A, 88:2 (1999), 342–367
  87. A. Gyarfas, J. Lehel, “Trees in greedy colorings of hypergraphs”, Discrete Math., 311:2-3 (2011), 208–209
  88. A. Hajnal, E. Szemeredi, “Proof of a conjecture of P. Erdős”, Combinatorial theory and its applications (Balatonfüred, 1969), v. 2, North-Holland, Amsterdam, 1970, 601–623
  89. J. Hastad, S. Jukna, P. Pudlak, “Top-down lower bounds for depth-three circuits”, Comput. Complexity, 5:2 (1995), 99–112
  90. P. Haxell, J. Verstraete, “List coloring hypergraphs”, Electron. J. Combin., 17:1 (2010), 129, 12 pp.
  91. N. Hegyvari, “On the dimension of the Hilbert cubes”, J. Number Theory, 77:2 (1999), 326–330
  92. M. Helm, “On the Beck–Fiala theorem”, Discrete Math., 207:1-3 (1999), 73–87
  93. M. Herzog, J. Schönheim, “The $B_r$ property and chromatic numbers of generalized graphs”, J. Combin. Theory Ser. B, 12:1 (1972), 41–49
  94. D. Hilbert, “Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten”, J. Reine Angew. Math., 1892:110 (1892), 104–129
  95. A. J. W. Hilton, E. C. Milner, “Some intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 18:1 (1967), 369–384
  96. P. Horak, “On the chromatic number of Steiner triple systems of order 25”, Discrete Math., 299:1-3 (2005), 120–128
  97. P. Keevash, “Hypergraph Turan problems”, Surveys in combinatorics 2011 (Exeter, UK), London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011, 83–139
  98. H. A. Kierstead, A. V. Kostochka, “An Ore-type theorem on equitable coloring”, J. Combin. Theory Ser. B, 98:1 (2008), 226–234
  99. H. A. Kierstead, A. V. Kostochka, “A short proof of the Hajnal–Szemeredi theorem on equitable colouring”, Combin. Probab. Comput., 17:2 (2008), 265–270
  100. J. H. Kim, “On Brooks' theorem for sparse graphs”, Combin. Probab. Comput., 4:2 (1995), 97–132
  101. D. J. Kleitman, K. J. Winston, “The asymptotic number of lattices”, Combinatorical mathematics, optimal designs and their applications, Ann. Discrete Math., 6, North-Holland Publishing Co., Amsterdam, 1980, 243–249
  102. D. J. Kleitman, K. J. Winston, “On the number of graphs without 4-cycles”, Discrete Math., 41:2 (1982), 167–172
  103. A. Kostochka, “On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs”, Electron. J. Combin., 9:1 (2002), 9, 4 pp.
  104. A. Kostochka, “Coloring uniform hypergraphs with few colors”, Random Structures Algorithms, 24:1 (2004), 1–10
  105. A. Kostochka, “Color-critical graphs and hypergraphs with few edges: a survey”, More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006, 175–197
  106. A. V. Kostochka, M. Kumbhat, “Coloring uniform hypergraphs with few edges”, Random Structures Algorithms, 35:3 (2009), 348–368
  107. А. В. Косточка, Н. П. Мазурова, “Одна оценка в теории раскраски графов”, Методы дискретного анализа в решении комбинаторных задач, 30, Ин-т матем. СО АН СССР, Новосибирск, 1977, 23–29
  108. A. Kostochka, D. Mubayi, V. Rödl, P. Tetali, “On the chromatic number of set systems”, Random Structures Algorithms, 19:2 (2001), 87–98
  109. A. V. Kostochka, V. Rödl, “Partial Steiner systems and matchings in hypergraphs”, Random Structures Algorithms, 13:3-4 (1998), 335–347
  110. A. V. Kostochka, V. Rödl, “Constructions of sparse uniform hypergraphs with high chromatic number”, Random Structures Algorithms, 36:1 (2010), 46–56
  111. A. V. Kostochka, V. Rödl, M. Kumbhat, “Coloring uniform hypergraphs with small edge degrees”, Fete of combinatorics and computer science, Bolyai Soc. Math. Stud., 20, Janos Bolyai Math. Soc., Budapest, 2010, 213–238
  112. A. V. Kostochka, D. R. Woodall, “Density conditions for panchromatic colourings of hypergraphs”, Combinatorica, 21:4 (2001), 515–541
  113. J. Kozik, “Multipass greedy coloring of simple uniform hypergraphs”, Random Structures Algorithms, 48:1 (2016), 125–146
  114. J. Kozik, D. Shabanov, “Improved algorithms for colorings of simple hypergraphs and applications”, J. Combin. Theory Ser. B, 116 (2016), 312–332
  115. A. Kupavskii, D. Shabanov, “Colourings of uniform hypergraphs with large girth and applications”, Combin. Probab. Comput., 27:2 (2018), 245–273
  116. A. Kupavskii, D. Zakharov, “Regular bipartite graphs and intersecting families”, J. Combin. Theory Ser. A, 155 (2018), 180–189
  117. H. Levinson, R. Silverman, “Generalizations of property $B$”, 2nd international conference on combinatorial mathematics (New York, 1978), Ann. New York Acad. Sci., 319, no. 1, 1979, 349–353
  118. P.-S. Loh, “A note on embedding hypertrees”, Electron. J. Combin., 16:1 (2009), 18, 4 pp.
  119. L. Lovasz, “A generalization of Konig's theorem”, Acta Math. Acad. Sci. Hungar., 21:3-4 (1970), 443–446
  120. L. Lovasz, “On minimax theorems of combinatorics”, Mat. Lapok, 26:3-4 (1975), 209–264
  121. L. Lu, On a problem of Erdős and Lovasz on coloring non-uniform hypergraphs, 2008, 15 pp.
  122. K. Majumder, S. Mukherjee, “A note on a series of families constructed over the cyclic graph”, J. Combin. Theory Ser. A, 157 (2018), 41–48
  123. J. Mathews, M. K. Panda, S. Shannigrahi, “On the construction of non-2-colorable uniform hypergraphs”, Discrete Appl. Math., 180 (2015), 181–187
  124. J. Matoušek, Geometric discrepancy. An illustrated guide, Algorithms Combin., 18, Springer-Verlag, Berlin, 1999, xii+288 pp.
  125. M. Matsumoto, N. Tokushige, “The exact bound in the Erd{ő}s–Ko–Rado theorem for cross-intersecting families”, J. Combin. Theory Ser. A, 52:1 (1989), 90–97
  126. E. W. Miller, “On a property of families of sets”, C. R. Soc. Sci. Varsovie, 30 (1937), 31–38
  127. P. R. J. Östergard, “On the minimum size of 4-uniform hypergraphs without property $B$”, Discrete Appl. Math., 163, Part 2 (2014), 199–204
  128. K. T. Phelps, V. Rödl, “Steiner triple systems with minimum independence number”, Ars Combin., 21 (1986), 167–172
  129. N. Pippenger, M. C. Golumbic, “The inducibility of graphs”, J. Combin. Theory Ser. B, 19:3 (1975), 189–203
  130. A. Pluhar, “Greedy colorings of uniform hypergraphs”, Random Structures Algorithms, 35:2 (2009), 216–221
  131. J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32
  132. А. М. Райгородский, Д. А. Шабанов, “Задача Эрдеша–Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы”, УМН, 66:5(401) (2011), 109–182
  133. V. Rödl, E. Šinajova, “Note on independent sets in {S}teiner systems”, Random Structures Algorithms, 5:1 (1994), 183–190
  134. А. П. Розовская, “О двухцветных раскрасках общего вида для равномерных гиперграфов”, Докл. РАН, 429:3 (2009), 309–311
  135. А. П. Розовская, Д. А. Шабанов, “О правильных раскрасках гиперграфов в предписанные цвета”, Дискрет. матем., 22:3 (2010), 94–109
  136. W. Samotij, “Counting independent sets in graphs”, European J. Combin., 48 (2015), 5–18
  137. D. Saxton, A. Thomason, “List colourings of regular hypergraphs”, Combin. Probab. Comput., 21:1-2 (2012), 315–322
  138. D. Saxton, A. Thomason, “Hypergraph containers”, Invent. Math., 201:3 (2015), 925–992
  139. D. Saxton, A. Thomason, “Online containers for hypergraphs, with applications to linear equations”, J. Combin. Theory Ser. B, 121 (2016), 248–283
  140. D. Saxton, A. Thomason, “Simple containers for simple hypergraphs”, Combin. Probab. Comput., 25:3 (2016), 448–459
  141. W. M. Schmidt, “Ein kombinatorisches Problem von P. Erdős und A. Hajnal”, Acta Math. Acad. Sci. Hungar., 15:3 (1964), 373–374
  142. P. D. Seymour, “A note on a combinatorial problem of Erdős and Hajnal”, J. Lond. Math. Soc. (2), 8:4 (1974), 681–682
  143. P. D. Seymour, “On the two-colouring of hypergraphs”, Quart. J. Math. Oxford Ser. (2), 25:1 (1974), 303–311
  144. Д. А. Шабанов, “Об одной комбинаторной задаче Эрдeша”, Докл. РАН, 396:2 (2004), 166–169
  145. Д. А. Шабанов, “Экстремальные задачи для раскрасок равномерных гиперграфов”, Изв. РАН. Сер. матем., 71:6 (2007), 183–222
  146. Д. А. Шабанов, “Рандомизированные алгоритмы раскрасок гиперграфов”, Матем. сб., 199:7 (2008), 139–160
  147. Д. А. Шабанов, “О хроматическом числе конечных систем подмножеств”, Матем. заметки, 85:6 (2009), 951–954
  148. Д. А. Шабанов, “Об улучшении нижней оценки в комбинаторной задаче Эрдeша–Хайнала”, Докл. РАН, 426:2 (2009), 177–178
  149. Д. А. Шабанов, “О существовании полноцветных раскрасок для равномерных гиперграфов”, Матем. сб., 201:4 (2010), 137–160
  150. D. A. Shabanov, “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234
  151. D. A. Shabanov, “On $r$-chromatic hypergraphs”, Discrete Math., 312:2 (2012), 441–458
  152. D. A. Shabanov, “Random coloring method in the combinatorial problem of Erdős and Lovasz”, Random Structures Algorithms, 40:2 (2012), 227–253
  153. D. A. Shabanov, “Coloring non-uniform hypergraphs without short cycles”, Graphs Combin., 30:5 (2014), 1249–1260
  154. D. A. Shabanov, “Around Erdős–Lovasz problem on colorings of non-uniform hypergraphs”, Discrete Math., 338:11 (2015), 1976–1981
  155. D. A. Shabanov, “Equitable two-colorings of uniform hypergraphs”, European J. Combin., 43 (2015), 185–203
  156. I. Shirgazina, “Equitable colorings of non-uniform simple hypergraphs”, The eight European conference on combinatorics, graph theory and applications, EuroComb 2015 (Bergen, 2015), Electron. Notes Discrete Math., 49, Elsevier Science B.V., Amsterdam, 2015, 699–703
  157. И. Р. Ширгазина, “Справедливые раскраски неоднородных гиперграфов”, Матем. заметки, 99:3 (2016), 441–456
  158. A. Sidorenko, “What we know and what we do not know about Turan numbers”, Graphs Combin., 11:2 (1995), 179–199
  159. A. Sidorenko, “Upper bounds for Turan numbers”, J. Combin. Theory Ser. A, 77:1 (1997), 134–147
  160. J. Spencer, “Coloring $n$-sets red and blue”, J. Combin. Theory Ser. A, 30:1 (1981), 112–113
  161. F. Sterboul, “An extremal problem in hypergraph coloring”, J. Combin. Theory Ser. B, 22:2 (1977), 159–164
  162. Z. Szabo, “An application of Lovasz' local lemma – a new lower bound for the van der Waerden number”, Random Structures Algorithms, 1:3 (1990), 343–360
  163. В. А. Ташкинов, “О нижней границе для хроматического числа графов с заданными максимальной степенью вершин и обхватом”, Сиб. электрон. матем. изв., 1 (2004), 99–109
  164. A. D. Taylor, “Bounds for the disjoint unions theorem”, J. Combin. Theory Ser. A, 30:3 (1981), 339–344
  165. B. Toft, “On color-critical hypergraphs”, Infinite and finite sets (Keszthely, 1973), v. III, Colloq. Math. Soc. Janos Bolyai, 10, North Holland, Amsterdam, 1975, 1445–1457
  166. B. L. van der Waerden, “Beweis einer {B}audetschen {V}ermutung”, Nieuw Arch. Wisk., 15 (1927), 212–216
  167. В. Г. Визинг, “Раскраска вершин графа в предписанные цвета”, Методы дискретного анализа в теории кодов и схем, 29, Ин-т матем. СО АН СССР, Новосибирск, 1976, 3–10
  168. D. R. Woodall, “Property B and the four-color problem”, Combinatorics (Math. Inst., Oxford, 1972), Inst. Math. Appl., Southend-on-Sea, 1972, 322–340

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2020 Raigorodskii A.M., Cherkashin D.D.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».