On the weak chromatic number of random hypergraphs. (English) Zbl 1435.05182
Summary: The paper deals with weak chromatic numbers of random hypergraphs. Recall that a vertex coloring is said to be \(j\)-proper for a hypergraph if every \(j + 1\) vertices of any edge do not share a common color. The \(j\)-chromatic number of a hypergraph is the minimum number of colors required for a \(j\)-proper coloring. We study the \(j\)-chromatic number of a random hypergraph in the binomial model \(H (n, k, p)\) in the case \(j = k - 2\) and investigate, for fixed \(r\), the threshold for the property that \(( k - 2)\)-chromatic number of \(H (n, k, p)\) does not exceed \(r\). This threshold corresponds to the sparse case, when \(p = c n / \begin{pmatrix} n \\ k\end{pmatrix}\) for a fixed parameter \(c > 0\) and the main result gives the tight bounds for it.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C65 | Hypergraphs |
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | P. Ayre, A. Coja-Oghlan, C. Greenhill, Hypergraph coloring up to condensation, Random Structures Algorithms, early view. · Zbl 1417.05057 |
| [2] | A.E. Balobanov, D.A. Shabanov, On the strong chromatic number of a random 3-uniform hypergraph, preprint. · Zbl 1390.05156 |
| [3] | Balobanov, A. E.; Shabanov, D. A., On the number of independent sets in simple hypergraphs, Math. Notes, 103, 1-2, 33-41 (2018) · Zbl 1390.05156 |
| [4] | Cutler, J.; Radcliffe, A. J., Hypergraph independent sets, combinatorics, Probab. Comput., 22, 1, 9-20 (2013) · Zbl 1257.05104 |
| [5] | Dyer, M.; Frieze, A.; Greenhill, C., On the chromatic number of a random hypergraph, J. Combin. Theory Ser. B, 113, 68-122 (2015) · Zbl 1315.05051 |
| [6] | Hatami, H.; Molloy, M., Sharp thresholds for constraint satisfaction problems and homomorphisms, Random Struct. Algorithms, 33, 3, 310-332 (2008) · Zbl 1182.05110 |
| [7] | Heckel, A., The chromatic number of dense random graphs, Random Struct. Algorithms, 53, 140-182 (2018) · Zbl 1401.05115 |
| [8] | Kravtsov, D. A.; Krokhmal, N. E.; Shabanov, D. A., Panchromatic 3-colorings of random hypergraphs, Eur. J. Combin., 78, 28-43 (2019) · Zbl 1414.05119 |
| [9] | Krivelevich, M.; Sudakov, B., The chromatic numbers of random hypergraphs, Random Structures Algorithms, 12, 381-403 (1998) · Zbl 0959.05110 |
| [10] | Ordentlich, E.; Roth, R., Independent sets in regular hypergraphs and multidimensional runlength-limited constraints, SIAM J. Discrete Math., 17, 4, 615-623 (2004) · Zbl 1055.05108 |
| [11] | Schmidt, J. P., Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number, Discrete Math., 66, 259-277 (1987) · Zbl 0624.05049 |
| [12] | Schmidt-Pruzan, J.; Shamir, E.; Upfal, E., Random hypergraph coloring algorithms and the weak chromatic number, J. Graph Theory, 8, 347-362 (1985) · Zbl 0584.05049 |
| [13] | A.S. Semenov, Two-colorings of random hypergraphs, Theory of Probability and its Applications, accepted. |
| [14] | Semenov, A. S.; Shabanov, D. A., General independence sets in random strongly sparse hypergraphs, Probl. Inf. Transm., 54, 1, 56-69 (2018) · Zbl 1457.05082 |
| [15] | Shabanov, D. A., On the concentration of the chromatic number of a random hypergraph, Dokl. Math., 96, 1, 321-325 (2017) · Zbl 1373.05069 |
| [16] | Shamir, E., Chromatic number of random hypergraphs and associated graphs, Adv. Comput. Res., 5, 127-142 (1989) |
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.
