The existence of panchromatic colourings for uniform hypergraphs

D. A. Shabanov

Sbornik. Mathematics, Tome 201 (2010) no. 4, pp. 607-630

Résumé

The well-known extremal problem concerning panchromatic colouring of hypergraphs is investigated. An $r$-colouring of the set of vertices of a hypergraph is said to be panchromatic if each link of the hypergraph is incident to vertices of all colours. The quantity $p(n,r)$ defined as the minimum number of links in an $n$-uniform hypergraph which admits no panchromatic $r$-colourings is studied. New lower and upper bounds for $p(n,r)$ are obtained, which improve earlier results for many of the relations between the parameters $n$ and $r$. In addition, a sufficient condition for the existence of a panchromatic $r$-colouring of an $n$-uniform hypergraph is obtained. Bibliography: 18 items.

Détail

Keywords: hypergraph, panchromatic colouring, the method of random colouring.

Bibliographie

[1] A. Kostochka, “On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs”, Electron. J. Combin., 9:1 (2002) | MR | Zbl

[2] A. Kostochka, “Color-critical graphs and hypergraphs with few edges: a survey”, More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15, Springer-Verlag, Berlin, 2006, 175–197 | MR | Zbl

[3] P. Erdős, L. Lovász, “Problems and results on $3$-chromatic hypergraphs and some related questions”, Infinite and finite sets (Keszthely, 1973), North Holland, Amsterdam, 1975, 609–627 | MR | Zbl

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

[5] 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

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

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

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

[9] V. G. Vizing, “Raskraska vershin grafa v predpisannye tsveta”, Metody diskretnogo analiza v teorii kodov i skhem: sbornik nauchnykh trudov, 29, In-t matem. SO AN SSSR, Novosibirsk, 1976, 3–10 | MR | Zbl

[10] P. Erdős, A. L. Rubin, H. Taylor, “Choosability in graphs”, Proceedings of the West Coast Conference on Combinatorics (Humboldt State Univ., Arcata, CA, 1979), Congress. Numer., 26, Utilitas Math., Winnipeg, MA, 1980, 125–157 | MR | Zbl

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

[12] P. Erdős, J. Spencer, Probabilistic methods in combinatorics, Academic Press, New York–London, 1974 | MR | Zbl

[13] G. P. Gavrilov, A. A. Sapozhenko, Zadachi i uprazhneniya po diskretnoi matematike, Fizmatlit, M., 2004

[14] A. M. Raigorodskii, “Sistemy obschikh predstavitelei”, Fundament. i prikl. matem., 5:3 (1999), 851–860 | MR | Zbl

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

[16] A. N. Shiryaev, Probability, Grad. Texts in Math., 95, Springer-Verlag, New York, 1996 | MR | MR | Zbl | Zbl

[17] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 2000 | MR | Zbl

[18] T. Tao, V. H. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006 | MR | Zbl