Colorings of partial Steiner systems and their applications

A. B. Kupavskii ; D. A. Shabanov

Fundamentalʹnaâ i prikladnaâ matematika, Tome 18 (2013) no. 3, pp. 77-115.

Résumé

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for $r$-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for $r$-colorability of a random hypergraph in a binomial model.

Bibliographie

[1] Alon N., Spenser Dzh., Veroyatnostnyi metod, Binom, M., 2007

[2] Vizing V. G., “Raskraska vershin grafa v predpisannye tsveta”, Metody diskretnogo analiza v teorii kodov i skhem: sb. nauch. tr., 29, In-t mat. SO AN SSSR, Novosibirsk, 1976, 3–10 | MR

[3] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2000 | MR | Zbl

[4] Achlioptas D., Friedgut E., “A sharp threshold for $k$-colorability”, Random Structures Algorithms, 14:1 (1999), 63–70 | 3.0.CO;2-7 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] Achlioptas D., Kim J. H., Krivelevich M., Tetali P., “Two-coloring random hypergraphs”, Random Structures Algorithms, 20:2 (2002), 249–259 | DOI | MR | Zbl

[6] Achlioptas D., Moore C., “On the $2$-colorability of random hypergraphs”, Random, Springer, Berlin, 2002, 78–90 | MR | Zbl

[7] Alon N., Spencer J., A note on coloring random $k$-sets, Unpublished manuscript

[8] Assmus E. F. (Jr.), Key J. D., Steiner Systems, Designs and Their Codes, Cambridge Univ. Press, Cambridge, 1994, 295–316

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

[10] Beth T., Jungnickel D., Lenz H., Design Theory, Cambridge Univ. Press, Cambridge, 1986 | MR | Zbl

[11] Bollobás B., “The chromatic number of random graphs”, Combinatorica, 8:1 (1988), 49–56 | DOI | MR

[12] Bollobás B., Random Graphs, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[13] Bollobás B., Thomason A., “Thresholds functions”, Combinatorica, 7 (1987), 35–38 | DOI | MR | Zbl

[14] Coja-Oghlan A., Zdeborová L., “The condensation transition in random hypergraph $2$-coloring”, Proc. 23rd SODA, 2012, 241–250

[15] Erdős P., Lovász L., “Problems and results on $3$-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, Coll. Math. Soc. Jänos Bolyai, 10, North Holland, Amsterdam, 1973, 609–627 | MR

[16] Erdős P., Rényi A., “On random graphs. I”, Publ. Math. Debrecen, 6 (1959), 290–297 | MR | Zbl

[17] Erdős P., Rényi A., “On the evolution of random graphs”, Publ. Math. Inst. Hungar. Acad. Sci., 5:1–2 (1960), 17–61 | MR | Zbl

[18] Erdős P., Rubin A. L., Taylor H., “Choosability in graphs”, Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congress. Numer., 26, 1980, 125–157 | MR

[19] Friedgut E., “Necessary and sufficient conditions for sharp thresholds of graph properties”, J. Amer. Math. Soc., 12 (1999), 1017–1054 | DOI | MR | Zbl

[20] Jansen S., Łuczak T., Rucinski A., Random Graphs, Wiley-Interscience, New York, 2000 | MR

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

[22] Kostochka A. V., Kumbhat M., Rödl V., “Coloring uniform hypergraphs with small edge degrees”, Fete of Combinatorics and Computer Science, Bolyai Soc. Math. Stud., 20, Springer, Berlin, 2010, 213–238 | DOI | MR

[23] Krivelevich M., Sudakov B., “The chromatic numbers of random hypergraphs”, Random Structures Algorithms, 12 (1998), 381–403 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[24] Krivelevich M., Vu V., “Choosability in random hypergraphs”, J. Combin. Theory Ser. B, 83:2 (2001), 241–257 | DOI | MR | Zbl

[25] Łuczak T., “The chromatic number of random graphs”, Combinatorica, 11:1 (1991), 45–54 | DOI | MR | Zbl

[26] Radhakrishnan J., Srinivasan A., “Improved bounds and algorithms for hypergraph two-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

[27] Shabanov D. A., “On $r$-chromatic hypergraphs”, Discrete Math., 312:2 (2012), 441–458 | DOI | MR | Zbl

[28] Shabanov D. A., “Random coloring method in the combinatorial problem of Erdős and Lovász”, Random Structures Algorithms, 40:2 (2012), 227–253 | DOI | MR | Zbl

[29] Shamir E., “Chromatic number of random hypergraphs and associated graphs”, Adv. Comput. Res., 5 (1989), 127–142

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

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

[32] Szabó Z., “An application of Lovász' local lemma – a new lower bound for the van der Waerden number”, Random Structures Algorithms, 1:3 (1990), 343–360 | DOI | MR | Zbl