Оценки пороговых вероятностей для свойств дробной раскрашиваемости случайных гиперграфов
Автор: Шабанов Д.А., Шайхеева Т.М.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 3 (63) т.16, 2024 года.
Бесплатный доступ
В работе исследуется известная задача о поиске пороговых вероятностей для свойств раскрасок случайных гиперграфов. Рассматривается биномиальная модель случайного k-однородного гиперграфа Н(n, k, p) в разреженном режиме, когда среднее число ребер гиперграфа линейно по числу вершин. В качестве основного результата получены оценки точной пороговой вероятности для свойства правильной (5 : 2)-дробной раскрашиваемости Н(n, k, p).
Случайные гиперграфы, дробные раскраски, метод второго момента
Короткий адрес: https://sciup.org/142243261
IDR: 142243261
Список литературы Оценки пороговых вероятностей для свойств дробной раскрашиваемости случайных гиперграфов
- Bollobas В. Random graphs. Cambridge University Press, 2001.
- Jansen S., Luczak Т., Rucinski A. Random graphs. Wiley-Interscience. New York, 2000.
- Frieze A., Karonski M. Introduction to random graphs. Cambridge University Press, 2015.
- Scheinerman E.R., Ullman D.H. Fractional Graph Theory. John Wiley and Sons, 2013.
- Hatami H., Molloy M. Sharp thresholds for constraint satisfaction problems and homomorphisms // Random Structures and Algorithms. 2008. V. 33. P. 310-332.
- Alon N., Spencer J. A note on coloring random k-sets. Unpublished manuscript. http://cs.tau.ac.il/ nogaa/PDFS/kset2.pdf
- Achlioptas D., Kim J.H., Krivelevich M., Tetali P. Two-colorings random hvpergraphs // Random Structures and Algorithms. 2002. V. 20, N 2. P. 249-259.
- Achlioptas D., Moore C. On the 2-colorabilitv of random hvpergraphs // Lecture Notes in Computer Science. 2002. V. 2483. P. 78-90. *
- Coja-Oghlan A., Zdeborova L. The condensation transition in random hvpergraph 2-coloring // Proc. 23rd Annual ACM SIAM Symposium on Discrete Algorithms. SIAM, 2012. P. 241-250.
- Coja-Oghlan A., Panagiotou K. Catching the k-NAESAT threshold // Proc. 44th STOC. 2012. P. 899-908.
- Dyer M., Frieze A., Greenhill C. On the chromatic number of a random hvpergraph // Journal of Combinatorial Theory, Series B. 2015. V. 113. P. 68-122.
- Shabanov D.A. Estimating the r-colorabilitv threshold for a random hvpergraph // Discrete Applied Mathematics. 2020. V. 282. P. 168-183.
- Kravtsov D.A., Krokhmal N.E., Shabanov D.A. Panchromatic 3-colorings of random hvpergraphs // European Journal of Combinatorics. 2019. V. 78. P. 28-43.
- Кравцов Д.А., Крахмаль H.E., Шаба,нов Д.А. Полноцветные раскраски случайных гиперграфов // Дискретная математика. 2019. Т. 31, № 2. С. 84-113.
- Захаров П.А., Шабанов Д.А. Дробные раскраски случайных гиперграфов // Успехи математических наук. 2023. Т. 78, № 6. С. 183-184.
Статья научная
