| Russian Mathematical Surveys |
|
|
|
|
|
Brief communications Fractional colourings of random hypergraphs P. A. Zakharovab, D. A. Shabanovab a Moscow Institute of Physics and Technology b HSE University
Russian version:
Uspekhi Matematicheskikh Nauk, 2023, Volume 78, Issue 6(474), DOI: https://doi.org/10.4213/rm10151 
Bibliographic databases:
    The work is devoted to the study of threshold probabilities in random hypergraphs. Recall that a hypergraph $H = (V, E)$ is a pair of finite sets, where $V$ is the set of hypergraph vertices and $E$ is the set of edges, which are subsets of the vertex set $V$. A hypergraph is said to be $k$-uniform if each of its edges consists precisely of $k$ vertices. The paper focuses on fractional colourings of hypergraphs. Let $a>b\geqslant 1$ be natural numbers. A fractional $(a\,{:}\,b)$-colouring of a hypergraph $H = (V,E)$ is an assignment of $b$ distinct colours chosen from a prescribed set of $a$ colours to each vertex of the hypergraph. An edge of the hypergraph is said to be properly coloured under the $(a\,{:}\,b)$-colouring if there is no common colour assigned to each vertex of the edge. Correspondingly, a hypergraph is called $(a\,{:}\,b)$-colourable if there exists a fractional $(a\,{:}\,b)$-colouring under which all of its edges are properly coloured. For $b=1$ the property of $(a\,{:}\,1)$-colourability coincides with the usual proper colouring of the hypergraph with $a$ colours. We deal with the binomial model of a random hypergraph $H(n,k,p)$, which can be described as the Bernoulli scheme on the edges of a complete $k$-uniform hypergraph on $n$ vertices, so that every edge is included in the hypergraph independently of the others with probability $p = p(n)$. In this model, for the property of $(a\,{:}\,b)$-colourability under consideration there exists a so-called sharp probability threshold (see [1]). Namely, for any fixed $k \in \mathbb{N}$, $k \geqslant 3$, and natural numbers $a>b\geqslant 1$, there exists a function $\widehat{p}_{k,a,b} = \widehat{p}_{k,a,b}(n)$ such that for any $\varepsilon > 0$
$$
\begin{equation*}
\mathsf{P}\bigl(H(n,k,p)\text{ is } (a\,{:}\,b)\text{-colourable}\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
$$
as $n \to +\infty$.
The search for probability thresholds for various properties is a fundamental research area in the theory of random graphs and hypergraphs. The problem of finding the probability threshold for 2-colourability of a random hypergraph $H(n,k,p)$ was raised for the first time by Alon and Spencer [2]. They showed that this probability threshold corresponds to the case when the parameter $p$ can be expressed as $p=cn / \binom{n}{k}$, where $c = c(k) > 0$ does not depend on $n$. Therefore, it is convenient to look for estimates of the probability threshold itself in the form of estimates for the quantity $c$, as it was done, for example, in [3] and [4]. The strongest result, which localizes the required critical value well, was obtained by Coja-Oghlan and Panagiotou [5]. They showed that there exists a function $\varepsilon(k)$ of order $\varepsilon(k)=2^{-k(1+o(1))}$ such that
$$
\begin{equation*}
\mathsf{P}\bigl(H(n,k,p)\text{ is 2-colourable}\bigr) \to \begin{cases} 1, & c < 2^{k-1}\log 2-\dfrac{\log 2}{2}-\dfrac{1}{4}-\varepsilon(k); \\ 0, & c > 2^{k-1}\log 2-\dfrac{\log 2}{2}-\dfrac{1}{4}+\varepsilon(k). \end{cases}
\end{equation*}
\notag
$$
It is worth noting that this is the only known result providing such a strong accuracy in estimating the probability threshold for the property of $a$-colourability of a random hypergraph. For $a>2$ there is currently a gap (see [6]) on the order of the constant, which is independent of $k$.
The purpose of this work is to study the probability threshold for the $(4\,{:}\,2)$- colourability property of a random hypergraph. The main result is formulated in the following theorem. Theorem 1. There are exponentially fast zero-tending positive functions $g_1(k)$ and $g_2(k)$ such that for all sufficiently large $k$, It follows from Theorem 1 that the probability threshold for the property of $(4\,{:}\,2)$-colourability is strictly greater than the probability threshold for the stronger property of proper 2-colourability. At the same time the theorem also provides a high accuracy of the localization of the required value. The proof of Theorem 1 is based on the second moment method, whose detailed application plan can be found in [6]. The substantive part of the work involves solving several optimization problems on the set of matrices with positive entries, which are of independent interest. To formulate one of them we introduce $S$ as the set of unordered pairs $(i,j)$ from the set $\{1,2,3,4\}$. Consider the set $\mathcal{M}$ whose elements are vectors $m=(m_{(i,j)},(i,j)\in S)$ satisfying the following conditions: $m_{(i,j)}\geqslant 0$ for any $(i,j)\in S$ and $\sum_{(i,j)\in S}m_{(i,j)}=1$. We define the following functions on $\mathcal{M}$: for $m\in\mathcal{M}$,
$$
\begin{equation*}
H(m)=-\sum_{(i,j)\in S}m_{(i,j)}\log m_{(i,j)}\quad\text{and}\quad 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
$$
Then the following theorem holds.
Theorem 2. There is an exponentially fast zero-tending positive function $g_2(k)$ such that the following holds for all sufficiently large $k$: if $c > 2^{k-2}\log 6-(\log 6)/2+g_2(k)$, then $H(m)+c\log(1-G(m))<0$ for any $m\in \mathcal{M}$.
Citation in format AMSBIB
\Bibitem{ZakSha23} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|