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

О концентрации значений  <i>j</i>-хроматических чисел случайных гиперграфов

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

Работа посвящена изучению предельного поведения \(j\)-хроматических чисел случайного k-однородного гиперграфа в биномиальной модели \(H(n,k,p)\). Рассматривается разреженный случай, когда среднее число ребер является линейной функцией от числа вершин \(n\), т.е. равно \(cn\), где \(c > 0\) не зависит от \(n\). Доказано, что при всех достаточно больших значениях \(c\) величина \(j\)-хроматического числа \(H(n,k,p)\) с вероятностью, стремящейся к 1, концентрируется в одном или двух соседних значениях.

55 0

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

Номер выпуска 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