| Russian Mathematical Surveys |
|
|
|
|
|
Brief communications Threshold probabilities for colourings of random hypergraphs M. M. Koshelevab, D. A. Shabanovac, T. M. Shaikheevaa a Moscow Institute of Physics and Technology (National Research University) b Lomonosov Moscow State University c HSE University
Bibliographic databases:
    We consider threshold probabilities in the theory of random graphs and hypergraphs. Recall that in discrete mathematics, by a hypergraph we usually mean a structure $H = (V, E)$, where $V$ is a finite set whose elements are called vertices of the hypergraph, and $E$ is a family of subsets of $V$, called edges of the hypergraph. The hypergraph $H$ is said to be $k$-homogeneous if all of its edges are $k$-subsets. In this note we are concerned with the properties of a random hypergraph in the binomial model $H(n, k, p)$, which is the Bernoulli scheme on the $k$-subsets of some vertex set of cardinality $n$, so that a $k$-subset is taken as an edge in $H(n, k, p)$ with probability $p$, independently of other subsets. Throughout the note $k\geqslant 3$ is fixed, $n$ is increasing, and $p=p(n)$ is a function of $n$. We look at threshold probabilities for some properties of colourings in the model $H(n,k,p)$ of a random hypergraph. Recall that for an integer $r\geqslant 2$ a hypergraph $H=(V,E)$ is said to be $r$-colourable if there exists a map $f\colon V\to\{1,\dots,r\}$ such that $\{f(v)\colon v\in A\}|>1$ for each edge $A\in E$, so that no edge of the hypergraph is monochrome. As is well known (see [1]), for any fixed $k,r \in \mathbb{N}$, $k \geqslant 3$ and $r\geqslant 2$, in the model $H(n,k,p)$ the property of $r$-colourability has a precise threshold probability. Namely, there exists a function $\widehat{p}_{k,r} = \widehat{p}_{k,r}(n)$ such that for each $\varepsilon > 0$, as $n \to \infty$,
$$
\begin{equation*}
\mathsf{P}\bigl(H(n,k,p) \text{ is $r$-colourable}\bigr) \to \begin{cases} 1, & p \leqslant (1-\varepsilon) \widehat{p}_{k,r}, \\ 0, & p \geqslant (1+\varepsilon) \widehat{p}_{k,r}. \end{cases}
\end{equation*}
\notag
$$
The problem of finding $\widehat{p}_{k,r}(n)$ was stated by Alon and Spencer in the 1990s and has extensively been investigated since then. The sharpest estimates were obtained by Coja-Oghlan and Panagiotou [2] for $r=2$ and sufficiently large $k$. To state their result, setting $cn=p{n\choose k}$, in place of $p$ we introduce the new parameter $c$ that is, in fact, in control of the average number of edges of the hypergraph. The authors of [2] showed that the threshold probability corresponds to the case when the quantity $c=c(n)$ is bounded and managed to estimate its threshold value quite accurately. Namely, they showed that there exists a function $\varepsilon(k)$ of order $\varepsilon(k)=2^{-k(1+o(1))}$ such that for all sufficiently large $k$, as $n \to \infty$,
$$
\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), \vphantom{\biggl\}} \\ 0, & c > 2^{k-1} \log 2 - \dfrac{\log 2}2-\dfrac{1}{4}+\varepsilon(k). \end{cases}
\end{equation*}
\notag
$$
Apart from 2-colourability, the sharpest results can be obtained for fractional colourings. Recall that for two integers $r>s\geqslant 1$ a hypergraph $H=(V,E)$ is said to be $({r:s})$-colourable if there exists a map $f\colon V\to{\{1,\dots,r\}\choose s}$ (a fractional colouring) such that $\bigcap_{v\in A}f(v)=\varnothing$ for each edge $A\in E$, so that to each vertex we assign a whole set of $s$ colours, and the condition is that for no edge do these sets contain a common colour. It follows from the general results of Hatami and Molloy [1] that for fixed $r>s\geqslant 1$ and $k\geqslant 3$ the property of $(r:s)$-colourability also has a precise threshold probability. Note that for $s=1$ we obtain the above problem of $r$-colourability. Another extreme case, $s=r-1$, was considered in [3], where the authors were also able to localize the threshold value of the parameter up to a function decreasing exponentially with respect to $k$. In [4] and [5] estimates with this accuracy for the threshold probability were found for $r=4,5$ and $s=2$. The aim of our note is to investigate the threshold probability for the property of $(r:2)$-colourability of a random hypergraph. We split the main result into two theorems, which give an upper and a lower bound for the quantity in question. In both statements we assume that $p=cn/{n\choose k}$, where $c$ is independent of $n$. Theorem 1. Let $r \leqslant 53$. Then there is a function $f(k) = O(0.99999999^k)$ such that for sufficiently large $k$ and the probability $\mathsf{P}\bigl(H(n,k,p)$ is $(r:2)$-colourable$\bigr)$ tends to $ 0$ as $n\to\infty$. Theorem 2. Let $r \leqslant 10$. Then there is a function $f(k) = O(0.99^k)$, such that for sufficiently large $k$ and the probability $\mathsf{P}\bigl(H(n,k,p)$ is $(r:2)$-colourable$\bigr)$ tends to $ 1$ as $n\to\infty$. Combining Theorems 1 and 2 we see that for $r\leqslant 10$ the threshold value is localized again to within a function decreasing exponentially rapidly with respect to $k$. The proofs of Theorems 1 and 2 are based on the methods of the first and second moments and on the solution of a number of extremal problems for stochastic matrices arising in a natural way in the calculation of the first two moments for the number of suitable fractional colourings of a random hypergraph $H(n,k,p)$. 
Citation in format AMSBIB
\Bibitem{KosShaSha25} |
|
||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|