| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Краткие сообщения Дробные раскраски случайных гиперграфов П. А. Захаровab, Д. А. Шабановab a Московский физико-технический институт (национальный исследовательский университет) b Национальный исследовательский университет "Высшая школа экономики"
Англоязычная версия:
Russian Mathematical Surveys, 2023, Volume 78, Issue 6, Pages DOI: https://doi.org/10.4213/rm10151e 
Реферативные базы данных:
     Работа посвящена исследованию пороговых вероятностей в случайных гиперграфах. Напомним, что гиперграф $H = (V, E)$ – это пара конечных множеств, где $V$ – множество вершин гиперграфа, а $E$ – множество ребер, которые являются подмножествами множества вершин $V$. Гиперграф называется $k$-однородным, если все его ребра состоят ровно из $k$ вершин. В работе изучаются дробные раскраски гиперграфов. Пусть $a>b\geqslant 1$ – натуральные числа. Дробной $(a\,{:}\,b)$-раскраской гиперграфа $H = (V,E)$ называется сопоставление каждой вершине гиперграфа набора из $b$ различных цветов, выбранных из заданного множества $a$ цветов. Ребро гиперграфа считается корректно покрашенным в $(a\,{:}\,b)$-раскраске, если нет общего цвета, присвоенного каждой из вершин ребра. Соответственно, гиперграф называется $(a\,{:}\,b)$-раскрашиваемым, если существует дробная $(a\,{:}\,b)$-раскраска, при которой все его ребра покрашены корректно. При $b=1$ свойство $(a\,{:}\,1)$-раскрашиваемости означает обычную правильную раскрашиваемость гиперграфа в $a$ цветов. Мы будем работать с биномиальной моделью случайного гиперграфа $H(n,k,p)$, которую можно описать как схему Бернулли на ребрах полного $k$-однородного гиперграфа на $n$ вершинах, т. е. каждое ребро включается в гиперграф независимо от других с вероятностью $p = p(n)$. В этой модели для исследуемого нами свойства $(a\,{:}\,b)$-раскрашиваемости существует так называемая точная пороговая вероятность (см. [1]). А именно, для любых фиксированных $k \in \mathbb{N}$, $k \geqslant 3$, $a>b\geqslant 1$ существует такая функция $\widehat{p}_{k,a,b} = \widehat{p}_{k,a,b}(n)$, что для любого $\varepsilon > 0$ при $n \to +\infty$
$$
\begin{equation*}
\mathsf{P}\bigl(H(n,k,p)\text{ является } (a\,{:}\,b)\text{-раскрашиваемым}\bigr) \to \begin{cases} 1, & p \leqslant (1-\varepsilon) \cdot\widehat{p}_{k,a,b}; \\ 0, & p \geqslant (1+\varepsilon) \cdot\widehat{p}_{k,a,b}. \end{cases}
\end{equation*}
\notag
$$
Поиск пороговых вероятностей для различных свойств – это фундаментальное направление исследований в теории случайных графов и гиперграфов. Проблема нахождения пороговой вероятности для правильной 2-раскрашиваемости случайного гиперграфа $H(n,k,p)$ была впервые поднята Алоном и Спенсером [2]. Ими было показано, что данной пороговой вероятности отвечает ситуация, когда параметр $p$ представим в виде $p=cn / \binom{n}{k}$, где $c = c(k) > 0$ не зависит от $n$. Соответственно, удобно искать оценки самой пороговой вероятности в виде оценок величины $c$, что и было сделано, например, в [3] и [4]. Наиболее сильный результат, хорошо локализующий искомое критическое значение, был получен Коджа-Огланом и Панайоту [5]. Они показали, что существует такая функция $\varepsilon(k)$ порядка $\varepsilon(k)=2^{-k(1+o(1))}$, что
$$
\begin{equation*}
\mathsf{P}\bigl(H(n,k,p)\text{ является 2-раскрашиваемым}\bigr) \to \begin{cases} 1, & c < 2^{k-1}\ln 2-\dfrac{\ln 2}{2}-\dfrac{1}{4}-\varepsilon(k); \\ 0, & c > 2^{k-1}\ln 2-\dfrac{\ln 2}{2}-\dfrac{1}{4}+\varepsilon(k). \end{cases}
\end{equation*}
\notag
$$
Отметим, что это единственный известный результат, который дает столь сильную точность оценок пороговой вероятности для свойства правильной $a$-раскрашиваемости случайного гиперграфа. При $a>2$ на сегодняшний день имеется зазор (см. [6]) порядка константы, не зависящей от $k$.
Цель настоящей работы – изучение пороговой вероятности для свойства $(4\,{:}\,2)$-раскрашиваемости случайного гиперграфа. Основной результат – следующая теорема. Теорема 1. Существуют такие экспоненциально быстро стремящиеся к нулю положительные функции $g_1(k)$ и $g_2(k)$, что для всех достаточно больших $k$ Из теоремы 1 следует, что пороговая вероятность для свойства $(4\,{:}\,2)$-раскрашиваемости строго больше пороговой вероятности для более сильного свойства правильной 2-раскрашиваемости. При этом теорема также дает высокую точность локализации искомого значения. Доказательство теоремы 1 опирается на метод второго момента, детальный план применения которого можно найти в [6]. Содержательная часть работы состоит в решении нескольких оптимизационных задач на множестве матриц с положительными слагаемыми, представляющих и самостоятельный интерес. Для формулировки одной из них введем множество $S$ – множество неупорядоченных пар чисел $(i,j)$ из множества $\{1,2,3,4\}$. Рассмотрим множество $\mathcal{M}$, элементами которого являются векторы $m=(m_{(i,j)},(i,j)\in S)$, удовлетворяющие условиям $m_{(i,j)}\geqslant 0$ для любых $(i,j)\in S$ и $\sum_{(i,j)\in S}m_{(i,j)}=1$. Определим на $\mathcal{M}$ следующие функции: для $m\in\mathcal{M}$
$$
\begin{equation*}
H(m)=-\sum_{(i,j)\in S}m_{(i,j)}\ln m_{(i,j)},\qquad G(m)=\sum_{i=1}^4\biggl(\,\sum_{j\ne i}m_{(i,j)}\biggr)^k- \sum_{(i,j)\in S}m^k_{(i,j)}.
\end{equation*}
\notag
$$
Тогда справедливо следующее утверждение.
Теорема 2. Существует такая экспоненциально быстро стремящаяся к нулю положительная функция $g_2(k)$, что для всех достаточно больших $k$ выполнено следующее: если $c > 2^{k-2}\ln 6-(\ln 6)/2+g_2(k)$, то для любого $m\in \mathcal{M}$ верно неравенство $H(m)+c\ln(1-G(m))<0$.
Цитирование в формате AMSBIB
\RBibitem{ZakSha23} |
|
|||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|