On the strong chromatic number of random hypergraphs. (English. Russian original) Zbl 1491.05172
Dokl. Math. 105, No. 1, 31-34 (2022); translation from Dokl. Ross. Akad. Nauk, Mat. Inform. Protsessy Upr. 502, 37-41 (2022).
Summary: We study the probability threshold for the property of strong colorability with a given number of colors of a random \(k\)-uniform hypergraph in the binomial model \(H(n,k,p)\). A vertex coloring of a hypergraph is said to be strong if any edge does not have two vertices of the same color under it. The problem of finding a sharp probability threshold for the existence of a strong coloring with \(q\) colors for \(H(n,k,p)\) is studied. By using the second moment method, we obtain fairly tight bounds for this quantity, provided that \(q\) is large enough in comparison with \(k\).
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C65 | Hypergraphs |
| 05C15 | Coloring of graphs and hypergraphs |
| 60C05 | Combinatorial probability |
Keywords:
random hypergraph; colorings of hypergraphs; probability thresholds; strong chromatic number; second moment methodReferences:
| [1] | Schmidt, J., Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number, Discrete Math., 66, 258-277 (1987) · Zbl 0624.05049 · doi:10.1016/0012-365X(87)90101-4 |
| [2] | Shamir, E., Chromatic number of random hypergraphs and associated graphs, Adv. Comput. Res, 5, 127-142 (1989) |
| [3] | Krivelevich, M.; Sudakov, B., The chromatic numbers of random hypergraphs, Random Struct. Algorithms, 12, 381-403 (1998) · Zbl 0959.05110 · doi:10.1002/(SICI)1098-2418(199807)12:4<381::AID-RSA5>3.0.CO;2-P |
| [4] | Łuczak, T., The chromatic number of random graphs, Combinatorica, 11, 45-54 (1991) · Zbl 0771.05090 · doi:10.1007/BF01375472 |
| [5] | Hatami, H.; Molloy, M., Sharp thresholds for constraint satisfaction problems and homomorphisms, Random Struct. Algorithms, 33, 310-332 (2008) · Zbl 1182.05110 · doi:10.1002/rsa.20225 |
| [6] | Achlioptas, D.; Naor, A., The two possible values of the chromatic number of a random graph, Ann. Math., 162, 1335-1351 (2005) · Zbl 1094.05048 · doi:10.4007/annals.2005.162.1335 |
| [7] | A. Coja-Oghlan, “Upper-bounding the k-colorability threshold by counting cover,” Electron. J. Combinatorics 20 (3), Research Paper No. 32 (2013). · Zbl 1298.05285 |
| [8] | Coja-Oghlan, A.; Vilenchik, D., The chromatic number of random graphs for most average degrees, Int. Math. Res. Notices, 2016, 5801-5859 (2015) · Zbl 1404.05189 · doi:10.1093/imrn/rnv333 |
| [9] | A. E. Balobanov and D. A. Shabanov, “On the strong chromatic number of a random 3-uniform hypergraph,” Discrete Math. 344 (3), 112231 (2021). · Zbl 1456.05053 |
| [10] | Khuzieva, A. E., “On strong colorings of 4-uniform random hypergraphs,” Trudy Mosk. Fiz.-, Tekh. Inst., 11, 91-107 (2019) |
| [11] | Dyer, M.; Frieze, A.; Greenhill, C., On the chromatic number of a random hypergraph, J. Combinatorial Theory, Ser. B, 113, 68-122 (2015) · Zbl 1315.05051 · doi:10.1016/j.jctb.2015.01.002 |
| [12] | Ayre, P.; Coja-Oghlan, A.; Greenhill, C., Hypergraph coloring up to condensation, Random Struct. Algorithms, 54, 615-652 (2019) · Zbl 1417.05057 · doi:10.1002/rsa.20824 |
| [13] | Shabanov, D. A., Estimating the r-colorability threshold for a random hypergraph, Discrete Appl. Math., 282, 168-183 (2020) · Zbl 1442.05070 · doi:10.1016/j.dam.2019.10.031 |
| [14] | Semenov, A.; Shabanov, D., On the weak chromatic number of random hypergraphs, Discrete Appl. Math., 276, 134-154 (2020) · Zbl 1435.05182 · doi:10.1016/j.dam.2019.03.025 |
| [15] | Semenov, A. S., Two-colorings of a random hypergraph, Theory Probab. Appl., 64, 59-77 (2019) · Zbl 1481.05053 · doi:10.1137/S0040585X97T989398 |
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.
