The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems

A. M. Raigorodskii   ; D. A. Shabanov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 66 (2011) no. 5, pp. 933-1002

Résumé

Extremal problems concerned with hypergraph colouring first arose in connection with classical investigations in the 1920-30s which gave rise to Ramsey theory. Since then, this area has assumed a central position in extremal combinatorics. This survey is devoted to one well-known problem of hypergraph colouring, the Erdős–Hajnal problem, initially posed in 1961. It opened a line of research in hypergraph theory whose methods and results are widely used in various domains of discrete mathematics. Bibliography: 109 titles.

Détail

Keywords: hypergraph, hypergraph colourings, chromatic numbers, extremal set theory.

Bibliographie

[1] A. A. Zykov, “Hypergraphs”, Russian Math. Surveys, 29:6 (1974), 89–156 | DOI | MR | Zbl | Zbl

[2] C. Berge, Graphes et hypergraphes, Monographies Universitaires de Mathématiques, 37, Dunod, Paris, 1970, xviii+502 pp. | MR | Zbl

[3] B. Bollobás, Combinatorics. Set systems, hypergraphs, families of vectors and combinatorial probability, Cambridge Univ. Press, Cambridge, 1986, xii+177 pp. | MR | Zbl

[4] J. L. Gross, J. Yellen (eds.), Handbook of graph theory, CRC Press, Boca Raton, FL, 2004, xiv+1167 pp. | MR | Zbl

[5] P. Erdős, A. Hajnal, “On a property of families of sets”, Acta Math. Acad. Sci. Hungar., 12:1-2 (1961), 87–123 | DOI | MR | Zbl

[6] P. Erdős, “On a combinatorial problem”, Nordisk Mat. Tidskr., 11 (1963), 5–10 | MR | Zbl

[7] P. Erdős, “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar., 15:3-4 (1964), 445–447 | DOI | MR | Zbl

[8] P. Erdős, J. Spencer, Probabilistic methods in combinatorics, Probab. Math. Statist., 17, Academic Press, New York–London, 1974, 106 pp. | MR | MR | Zbl

[9] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., Wiley-Interscience, New York, 2000, xviii+301 pp. | MR | Zbl

[10] W. M. Schmidt, “Ein kombinatorisches Problem von P. Erdős und A. Hajnal”, Acta Math. Acad. Sci. Hungar., 15 (1964), 373–374 | DOI | MR | Zbl

[11] P. Erdős, L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and finite sets (Colloq., Keszthely, 1973), Vol. II, Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam, 1975, 609–627 | MR | Zbl

[12] J. Beck, “On a combinatorial problem of P. Erdős and L. Lovász”, Discrete Math., 17:2 (1977), 127–131 | DOI | MR | Zbl

[13] J. Beck, “On 3-chromatic hypergraphs”, Discrete Math., 24:2 (1978), 127–137 | DOI | MR | Zbl

[14] J. Spencer, “Coloring $n$-sets red and blue”, J. Combin. Theory Ser. A, 30:1 (1981), 112–113 | DOI | MR | Zbl

[15] J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32 | 3.0.CO;2-2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[16] M. Herzog, J. Schönheim, “The $B_r$ property and chromatic numbers of generalized graphs”, J. Combin. Theory Ser. B, 12 (1972), 41–49 | DOI | MR | Zbl

[17] P. Erdős, “Some old and new problems in various branches of combinatorics”, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), Congr. Numer., 23–24, Utilitas Math. Publ., Winnipeg, Man., 1979, 19–37 | MR | Zbl

[18] A. V. Kostochka, “Color-critical graphs and hypergraphs with few edges: a survey”, More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15, eds. E. Győri, G. O. H. Katona, L. Lovász, Springer, Berlin, 2006, 175–197 ; http://www.springerlink.com/content/978-3-540-32377-8/#section=791726&page=1&locus=0 | MR | Zbl

[19] N. Alon, “Hypergraphs with high chromatic number”, Graphs Combin., 1 (1985), 387–389 | DOI | Zbl

[20] P. Frankl, V. Rödl, “Lower bounds for Turán's problem”, Graphs Combin., 1 (1985), 213–216 | DOI | MR | Zbl

[21] K. H. Kim, F. W. Roush, “On a problem of Turán”, Studies in pure mathematics, Birkhäuser, Basel, 1983, 423–425 | MR | Zbl

[22] A. V. Kostochka, “Coloring uniform hypergraphs with few colors”, Random Structures Algorithms, 24:1 (2004), 1–10 | DOI | MR | Zbl

[23] D. A. Shabanov, “On the chromatic number of finite systems of subsets”, Math. Notes, 85:6 (2009), 902–905 | DOI | MR | Zbl

[24] A. Pluhár, “Greedy colorings for uniform hypergraphs”, Random Structures Algorithms, 35:2 (2009), 216–221 | DOI | MR | Zbl

[25] D. A. Shabanov, “Improvement of the lower bound in the Erdös–Hajnal combinatorial problem”, Dokl. Math., 79:3 (2009), 349–350 | DOI | MR | Zbl

[26] D. A. Shabanov, “Lower bounds for the number of edges in hypergraphs of certain classes”, Dokl. Math., 82:2 (2010), 705–708 | DOI | MR | Zbl

[27] L. Lovász, “A generalization of König's theorem”, Acta Math. Acad. Sci. Hungar., 21 (1970), 443–446 | DOI | MR | Zbl

[28] L. Lovász, “Coverings and colorings of hypergraphs”, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1973), Utilitas Math. Publ., Winnipeg, Man., 1973, 3–12 | MR | Zbl

[29] P. D. Seymour, “On the two-coloring of hypergraphs”, Quart. J. Math. Oxford Ser. (2), 25 (1974), 303–312 | DOI | MR | Zbl

[30] D. R. Woodall, “Property $B$ and four-color problem”, Combinatorics, Proc. Conf. Combinatorial Math. (Math. Inst., Oxford, 1972), Inst. Math. Appl., Southend-on-Sea, England, 1972, 322–340 | MR

[31] M. Burshtein, “Kriticheskie gipergrafy s minimalnym chislom reber”, Soobsch. AN GSSR, 83:2 (1976), 285–288

[32] A. V. Kostochka, J. Nešetřil, “Properties of Decartes' construction of triangle-free graphs with high chromatic number”, Combin. Probab. Comput., 8:5 (1999), 467–472 | DOI | MR | Zbl

[33] A. V. Kostochka, M. Steibitz, “On the number of edges in colour-critical graphs and hypergraphs”, Combinatorica, 20:4 (2000), 521–530 | DOI | MR | Zbl

[34] H. L. Abbot, L. Moser, “On a combinatorial problem of Erdős and Hajnal”, Canad. Math. Bull., 7 (1964), 177–181 | DOI | MR | Zbl

[35] H. L. Abbot, D. Hanson, “On a combinatorial problem of Erdős”, Canad. Math. Bull., 12 (1969), 823–829 | DOI | MR | Zbl

[36] B. Toft, “On color-critical hypergraphs”, Infinite and finite sets (Colloq., Keszthely, 1973), Vol. III, Colloq. Math. Soc. János Bolyai, 10, eds. A. Hajnal et al., North-Holland, Amsterdam, 1975, 1445–1457 | MR

[37] T. R. Jensen, B. Toft, Graph coloring problems, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1995, xxii+295 pp. | MR | Zbl

[38] P. D. Seymour, “A note on a combinatorial problem of Erdős and Hajnal”, J. London Math. Soc. (2), 8:2 (1974), 681–682 | DOI | MR | Zbl

[39] P. Erdős, “On a combinatorial problem. III”, Canad. Math. Bull., 12 (1969), 413–416 | DOI | MR | Zbl

[40] H. L. Abbot, A. C. Liu, “On property B of families of sets”, Canad. Math. Bull., 23:4 (1980), 429–435 | DOI | MR | Zbl

[41] G. Exoo, “On constructing hypergraphs without Property B”, Ars Combin., 30 (1990), 3–12 | MR | Zbl

[42] M. K. Goldberg, H. C. Russell, “Toward computing $m(4)$”, Ars Combin., 39 (1995), 139–148 | MR | Zbl

[43] P. Aizley, J. L. Selfridge, “A lower bound for $m(4)$”, Abstract #747-05-18, Notices Amer. Math. Soc., 24:5 (1977), A-452

[44] G. M. Manning, “Some results on the $m(4)$ problem of Erdős and Hajnal”, Electron. Res. Announc. Amer. Math. Soc., 1:3 (1995), 112–113 | DOI | MR | Zbl

[45] P. Erdős, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38 | DOI | MR | Zbl

[46] D. A. Grable, K. T. Phelps, V. Rödl, “The minimum independence number for designs”, Combinatorica, 15:2 (1995), 175–185 | DOI | MR | Zbl

[47] A. Kostochka, D. Mubayi, V. Rödl, P. Tetali, “On the chromatic number of set systems”, Random Structures Algorithms, 19:2 (2001), 87–98 | DOI | MR | Zbl

[48] T. Bohman, A. Frieze, D. Mubayi, “Coloring $\mathscr H$-free hypergraphs”, Random Structures Algorithms, 36:1 (2010), 11–25 | DOI | MR | Zbl

[49] A. V. Kostochka, V. Rödl, “Constructions of sparse uniform hypergraphs with high chromatic number”, Random Structures Algorithms, 36:1 (2010), 46–56 | DOI | MR | Zbl

[50] Z. Szabó, “An application of Lovasz Local Lemma – a new lower bound for the van der Waerden number”, Random Structures Algorithms, 1:3 (1990), 343–360 | DOI | MR | Zbl

[51] A. V. Kostochka, M. Kumbhat, “Coloring uniform hypergraphs with few edges”, Random Structures Algorithms, 35:3 (2009), 348–368 | DOI | MR | Zbl

[52] A. P. Rozovskaya, D. A. Shabanov, “On proper colourings of hypergraphs using prescribed colours”, Discrete Math. Appl., 20:4 (2010), 391–409 | DOI | MR | Zbl

[53] D. A. Shabanov, “Lower bounds in the combinatorial problem of Erdös and Lovász”, Dokl. Math., 81:2 (2010), 286–288 | DOI | MR | Zbl

[54] J. Steiner, “Combinatorische Aufgabe”, J. Reine Angew. Math., 45 (1853), 181–182 | DOI | Zbl

[55] E. F. Assmus (Jr.), J. D. Key, “Steiner systems”, Designs and their codes, Cambridge Tracts in Math., 103, Cambridge Univ. Press, Cambridge, 1992, 295–316 | MR | Zbl

[56] T. Beth, D. Jungnickel, H. Lenz, Design theory, Cambridge Univ. Press, Cambridge, 1986, 688 pp. | MR | Zbl

[57] K. T. Phelps, V. Rödl, “Steiner triple systems with minimum independence number”, Ars Combin., 21 (1986), 167–172 | MR | Zbl

[58] V. Rödl, E. Šiňajová, “Note on independent sets in Steiner systems”, Proceedings of the Fifth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science (Poznań, 1991), Random Structures Algorithms, 5, no. 1, 1994, 183–190 | DOI | MR | Zbl

[59] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969, ix+274 pp. | MR | Zbl

[60] V. G. Vizing, “Raskraska vershin grafa v predpisannye tsveta”, Metody diskretnogo analiza v teorii kodov i skhem, Sbornik nauchnykh trudov, Diskretnyi analiz, 29, Institut matematiki SO AN SSSR, Novosibirsk, 1976, 3–10 | MR

[61] 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, Calif., 1979), Congr. Numer., 26, Utilitas Math. Publ., Winnipeg, Man., 1980, 125–157 | MR

[62] A. P. Rozovskaya, D. A. Shabanov, “On the problem of Erdős and Hajnal in the case of list colorings”, European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electron. Notes Discrete Math., 34, Elsevier, Amsterdam, 2009, 387–391 | DOI | MR

[63] A. V. Kostochka, D. R. Woodall, “Density conditions for panchromatic colourings of hypergraphs”, Combinatorics, 21:4 (2001), 515–541 | DOI | MR | Zbl

[64] A. Kostochka, “On a theorem by Erdős, Rubin and Taylor on choosability of complete bipartite graphs”, Electron. J. Combin., 9:1 (2002), Note 9, 4 pp. ; http://www.combinatorics.org/Volume_9/PDF/v9i1n9.pdf | MR | Zbl

[65] N. Alon, “Choice number of graphs: a probabilistic approach”, Combin. Probab. Comput., 1:2 (1992), 107–114 | DOI | MR | Zbl

[66] D. A. Shabanov, “On one combinatorial problem of Erdös”, Dokl. Math., 69:3 (2004), 359–362 | MR | Zbl

[67] D. A. Shabanov, “Extremal problems for colourings of uniform hypergraphs”, Izv. Math., 71:6 (2007), 1253–1290 | DOI | MR | Zbl

[68] D. A. Shabanov, “The existence of panchromatic colourings for uniform hypergraphs”, Sb. Math., 201:4 (2010), 607–630 | DOI | MR | Zbl

[69] D. A. Shabanov, “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234 | DOI | Zbl

[70] A. P. Rozovskaya, D. A. Shabanov, “Improvement of the lower bound in the Kostochka problem of panchromatic coloring of a hypergraph”, Math. Notes, 89:6 (2011), 903–906 | DOI

[71] N. N. Kuzyurin, “Asimptoticheskoe issledovanie zadachi o pokrytii”, Problemy kibernetiki, 37, 1980, 19–56 | MR | Zbl

[72] A. M. Raigorodskii, Sistemy obschikh predstavitelei v kombinatorike i ikh prilozheniya v geometrii, MTsNMO, M., 2009, 132 pp.

[73] P. Turán, “Research problems”, Magyar Tud. Akad. Mat. Kutató Internat. Közl., 6 (1961), 417–423 | MR

[74] A. Sidorenko, “What we know and what we do not know about Turán numbers”, Graphs Combin., 11:2 (1995), 179–199 | DOI | MR | Zbl

[75] Z. Füredi, “Turán's type problems”, Surveys in combinatorics, 1991, Proc. of the 13th British Combin. Conference (Guildford, 1991), London Math. Soc. Lecture Note Ser., 166, ed. A. D. Keedwell, Cambridge Univ. Press, Cambridge, 1991, 253–300 | MR | Zbl

[76] V. E. Tarakanov, Kombinatornye zadachi i $(0,1)$-matritsy, Nauka, M., 1985, 192 pp. | MR | Zbl

[77] D. A. Shabanov, “On the lower bound for van der Waerden functions”, Math. Notes, 87:6 (2010), 918–920 | DOI

[78] A. Frieze, D. Mubayi, Coloring simple hypergraphs, arXiv: 0809.2979v2

[79] A. Frieze, D. Mubayi, “On the chromatic number of simple triangle-free trimple systems”, Electron. J. Combin., 15:1 (2008), Research Paper 121, 27 pp. ; http://www.emis.de/journals/EJC/Volume_15/PDF/v15i1r59.pdf | MR | Zbl

[80] D. Shabanov, “On coloring uniform hypergraphs without 3-cycles”, Moscow J. Combin. Number Theory, 1:2 (2011) (to appear)

[81] A. V. Kostochka, N. P. Mazurova, “Neravenstvo v teorii raskrasok grafov”, Metody diskretnogo analiza v reshenii kombinatornykh zadach, Diskretnyi analiz, 30, 1977, 23–29 | MR | Zbl

[82] V. A. Tashkinov, “O nizhnei granitse dlya khromaticheskogo chisla grafov s zadannymi maksimalnoi stepenyu vershin i obkhvatom”, Sib. elektron. matem. izv., 1 (2004), 99–109 | MR | Zbl

[83] J. H. Kim, “On Brook's theorem for sparse graphs”, Combin. Probab. Comput., 4:2 (1995), 97–132 | DOI | MR | Zbl

[84] A. Johanssen, Asymptotic choice number for triangle free graphs, DIMACS Technical Report 91-95, 1996

[85] B. L. van der Waerden, “Beweis einer Baudetschen Vermutung”, Nieuw Archief voor Wiskunde, 15 (1927), 212–216 | Zbl

[86] A. Ya. Khinchin, Tri zhemchuzhiny teorii chisel, 2-e izd., URSS, M., 2004, 72 pp.

[87] R. L. Graham, Rudiments of Ramsey theory, CBMS Reg. Conf. Ser. Math., 45, Amer. Math. Soc., Providence, R.I., 1981, v+65 pp. | MR | MR | Zbl | Zbl

[88] R. L. Graham, B. L. Rotshild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math., Wiley, New York, 1980, ix+174 pp. | MR | Zbl

[89] A. M. Raigorodskii, Veroyatnost i algebra v kombinatorike, MTsNMO, M., 2008, 48 pp.

[90] V. A. Uspenskii, Lektsii o vychislimykh funktsiyakh, Fitmatlit, M., 1960, 492 pp. | MR

[91] S. Shelah, “Primitive recursive bounds for van der Waerden numbers”, J. Amer. Math. Soc., 1:3 (1988), 683–697 | DOI | MR | Zbl

[92] I. D. Shkredov, “Szemerédi's theorem and problems on arithmetic progressions”, Russian Math. Surveys, 61:6 (2006), 1101–1166 | DOI | MR | Zbl

[93] J. Bourgain, “Roth's theorem on progressions revisited”, J. Anal. Math., 104:1 (2008), 155–192 | DOI | MR | Zbl

[94] W. T. Gowers, “A new proof of Szemerédi theorem”, Geom. Funct. Anal., 11:3 (2001), 465–588 | DOI | MR | Zbl

[95] V. Chvátal, “Some unknown van der Waerden numbers”, Combinatorial structures and their applications, Proc. Calgary Internat. Conf. (Calgary, Alta., 1969), Gordon and Breach, New York, 1970, 31–33 | MR | Zbl

[96] R. S. Stevens, R. Shantaram, “Computer-generated van der Waerden partitions”, Math. Comp., 32:142 (1978), 635–636 | DOI | MR | Zbl

[97] M. D. Beeler, P. E. O'Neil, “Some new van der Waerden numbers”, Discrete Math., 28:2 (1979), 135–146 | DOI | MR | Zbl

[98] P. R. Herwig, M. J. H. Heule, P. M. van Lambalgen, H. van Maaren, “A new method to contruct lower bounds for van der Warden numbers”, Electron. J. Combin., 14:1 (2007), Research Paper 6, 18 pp. ; http://www.emis.de/journals/EJC/Volume_14/PDF/v14i1r6.pdf | MR | Zbl

[99] P. Erdős, R. Rado, “Combinatorial theorems on classifications of subsets of a given set”, Proc. London Math. Soc. (3), 2:1 (1952), 417–439 | DOI | MR | Zbl

[100] L. Moser, “Notes on number theory. II. On a theorem of van der Waerden”, Canad. Math. Bull., 3 (1960), 23–25 | DOI | MR | Zbl

[101] W. M. Schmidt, “Two combinatorial theorems on arithmetic progressions”, Duke Math. J., 29:1 (1962), 129–140 | DOI | MR | Zbl

[102] E. R. Berlekamp, “A construction for partitions which avoide long arithmetic progressions”, Canad. Math. Bull., 11 (1968), 409–414 | DOI | MR | Zbl

[103] T. Tao, V. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006, xviii+512 pp. | MR | Zbl

[104] D. A. Shabanov, “Funktsiya Van der Vardena i raskraski gipergrafov”, Izv. RAN. Ser. matem., 75:5 (2011), 195-224

[105] R. L. Graham, “Recent developments in Ramsey theory”, Proceedings of the International Congress of Mathematicians (Warsaw, 1983), v. 1, 2, PWN, Warsaw, 1984, 1555–1567 | MR | Zbl

[106] P. Erdős, “Some of my favorite problems and results”, The mathematics of Paul Erdős, v. I, Algorithms Combin., 13, Springer, Berlin, 1997, 47–67 | MR | Zbl

[107] R. Graham, “Some of my favorite problems in Ramsey theory”, Combinatorial number theory, Proceedings of the 2nd Integers Conference 2005 in celebration of the 70th birthday of Ronald Graham (Carrollton, GA, USA, 2005), de Gruyter, Berlin, 2007, 229–236 | MR | Zbl

[108] R. Graham, “Old and new problems and results in Ramsey theory”, Horizons of combinatorics, Bolyai Soc. Math. Stud., 17, eds. E. Győri, G. O. H. Katona, L. Lovász, Springer, Berlin, 2008, 105–118 ; http://www.springerlink.com/content/978-3-540-77199-9/#section=153712&page=1&locus=0 | MR | Zbl

[109] G. P. Gavrilov, A. A. Sapozhenko, Problems and exercises in discrete mathematics, Kluwer Texts Math. Sci., 14, Kluwer Acad. Publ., Dordrecht, 1996, xi+422 pp. | Zbl