О предельной концентрации значений хроматических чисел случайных гиперграфов

Автор: Денисов И. О.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 2 (58) т.15, 2023 года.

Бесплатный доступ

В работе исследуется асимптотическое поведение j-хроматических чисел случайных k-однородных гиперграфов в равномерной модели. Рассматривается так называемый «неразреженный» случай, когда число ребер гиперграфа растет быстрее числа вершин. Доказано, что в определенной области изменения параметров имеет место предельная концентрация значений j-хроматических чисел в некотором ограниченном множестве.

Случайный гиперграф, раскраски гиперграфов, j-хроматическое число

Короткий адрес: https://sciup.org/142238157

IDR: 142238157

Список литературы О предельной концентрации значений хроматических чисел случайных гиперграфов

Jansen S., Luczak T., Rucinski A. Random Graphs. New York: Wiley–Interscience, 2000.
Bollob´as B. The chromatic number of random graphs // Combinatorica. 1988. V. 8. P. 49–56.
Shamir E., Spencer J. Sharp concentration of the chromatic number on random graphs G(n,p) // Combinatorica. 1987. V. 7. P. 124–129.
Luczak T. A note on the sharp concentration of the chromatic number of random graphs // Combinatorica. 1991. V. 11, N 3. P. 295–297.
Alon N., Krivelevich M. The concentration of the chromatic number of random graphs // Combinatorica. 1997. V. 17, N 3. P. 303–313.
Achlioptas D., Naor A. The two possible values of the chromatic number of a random graph // Annals of Mathematics. 2005. V. 162, N 3. P. 1335–1351.
Coja-Oghlan A., Panagiotou K., Steger A. On the chromatic number of random graphs // Journal of Combinatorial Theory Series B. 2008. V. 98. P. 980–993.
Kargaltsev S.A., Shabanov D.A., Shaikheeva T.M. Two values of the chromatic number of a sparse random graph // Acta Mathematica Universitatis Comenianae. 2019. V. 88, N 3. P. 849–854.
Schmidt-Pruzan J., Shamir E., Upfal E. Random hypergraph coloring algorithms and the weak chromatic number // J. Graph Theory. 1985. V. 8. P. 347–362.
Schmidt J. Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number // Discrete Mathematics. 1987. V. 66. P. 258–277.
Shamir E. Chromatic number of random hypergraphs and associated graphs // Adv. Comput. Res. 1989. V. 5. P. 127–142.
Krivelevich M., Sudakov B. The chromatic numbers of random hypergraphs // Random Structures and Algorithms. 1998. V. 12, N 4. P. 381–403.
Dyer M., Frieze A., Greenhill C. On the chromatic number of a random hypergraph // Journal of Combinatorial Theory, Series B. 2015. V. 113. P. 68–122.
Ayre P., Coja-Oghlan A., Greenhill C. Hypergraph coloring up to condensation // Random Structures and Algorithms. 2019. V. 54, N 4. P. 615–652.
Shabanov D.A. Estimating the r-colorability threshold for a random hypergraph // Discrete Applied Mathematics. 2020. V. 282. P. 168–183.
Semenov A., Shabanov D. On the weak chromatic number of random hypergraphs // Discrete Applied Mathematics. 2020. V. 276. P. 134–154.
Денисов И.О., Шабанов Д.А. О концентрации значений 𝑗-хроматических чисел случайных гиперграфов // Доклады Российской академии наук. Математика, информатика, процессы управления. 2023. Т. 509. С. 28–35.
Balobanov A.E., Shabanov D.A. On the strong chromatic number of a random 3-uniform hypergraph // Discrete Mathematics. 2021. V. 344, N 3. 112231.
Матвеева Т.Г., Хузиева А.Э., Шабанов Д.А. О сильном хроматическом числе случайных гиперграфов // Доклады Российской академии наук. Математика, информатика, процессы управления. 2022. Т. 502. С. 37–41.
Демидович Ю.А., Шабанов Д.А. О двух предельных значениях хроматического числа случайного гиперграфа // Теория вероятностей и ее применения. 2022. Т. 67, № 2. С. 223–246.

Еще

Статья научная