Статьи автора

О СТРУКТУРЕ МНОЖЕСТВА ПОЛНОЦВЕТНЫХ РАСКРАСОК СЛУЧАЙНОГО ГИПЕРГРАФА

Номер выпуска 1 от 01.07.2023

В работе исследуется структура множества полноцветных раскрасок в три цвета у случайного гиперграфа в равномерной модели \(H(n,k,m)\). Хорошо известно, что свойство наличия полноцветной раскраски в заданное число цветов r имеет точную пороговую функцию, такое пороговое значение \({{\hat {m}}_{r}} = {{\hat {m}}_{r}}(n)\), что для любого \(\varepsilon > 0\) при \(m\;\leqslant \;(1 - \varepsilon ){{\hat {m}}_{r}}\) случайный гиперграф \(H(n,k,m)\) с вероятностью, стремящейся к 1 при \(n \to \infty \), обладает подобной раскраской, а при \(m\; \geqslant \;(1 + \varepsilon ){{\hat {m}}_{r}}\) – наоборот, не обладает подобной раскраской с вероятностью, стремящейся к 1. Мы исследуем алгоритмическую границу для свойства полноцветной раскраски в три цвета и доказываем, что если параметр m принимает значения несколько меньше, чем \({{\hat {m}}_{3}}\), то множество трехцветных полноцветных раскрасок \(H(n,k,m)\) хоть и не пусто с вероятностью, стремящейся к 1, но при этом подчиняется эффекту шаттеринга, впервые описанного в работе Д. Аклиоптаса и А. Койя-Оглана 2008 г.

52 0