О сильных раскрасках 4-однородных случайных гиперграфов
Автор: Хузиева А.Э.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 2 (42) т.11, 2019 года.
Бесплатный доступ
В работе рассматривается проблема о поиске пороговой вероятности сильной раскрашиваемости случайного 4-однородного гиперграфа в биномиальной модели H(n, 4, p). Раскраска множества вершин гиперграфа называется сильной, если любым двум вершинам u ̸= v, лежащим в одном ребре, присвоены различные цвета. Оценивается точная пороговая вероятность существования сильной раскраски H(n, 4, p) в r-цветов. Этому порогу отвечает так называемый разреженный случай, когда p = cn/(︀n4)︀ для фиксированного c > 0. Доказано, что при c r lnr/6 - 13/36 lnr - 1/6 - r-1/9 случайный гиперграф H(n, 4, cn/(︀n4)︀) является сильно раскрашиваемым в r цветов с вероятностью, стремящейся к 1 при n → ∞.
Случайные гиперграфы, раскраска гиперграфов, сильная раскраска, сильное хроматическое число, метод второго момента
Короткий адрес: https://sciup.org/142220493
IDR: 142220493
Список литературы О сильных раскрасках 4-однородных случайных гиперграфов
- 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. P. 381-403.
- Achlioptas D., Kim J.H., Krivelevich M.,Tetali P. Two-colorings random hypergraphs//Random Structures and Algorithms. 2002. V. 20. P. 249-259.
- Achlioptas D., Moore C. Random k-SAT: two moments suffice to cross a sharp threshold//SIAM Journal on Computing. 2005. V. 36, I. 3. P. 740-762.
- Coja-Oghlan A., Zdeborov´a L. The condensation transition in random hypergraph 2-coloring//Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. 2012. P. 241-250.
- Dyer M., Frieze A., Greenhill C. On the chromatic number of a random hypergraph//Journal of Combinatorial Theory. 2015. V. 113, Series B. P. 68-122.
- Ayre P., Coja-Oghlan A., Greenhill C. Hypergraph coloring up to condensation//Random Struct. Algorithms. early view. https://doi.org/10.1002/rsa.20824.
- Шабанов Д.А. О концентрации хроматического числа случайного гиперграфа//Доклады Академии Наук. 2017. Т. 475, № 1. C. 24-28.
- Balobanov A.E., Shabanov D.A. On the strong chromatic number of a random 3-uniform hypergraph: препринт. http://ru.discrete-mathematics.org/preprints/2018/20181117_shabanov.pdf
