This article is cited in 1 paper

Large Systems

Bounds on threshold probabilities for coloring properties of random hypergraphs

A. S. Semenov^a, D. A. Shabanov<sup>bac

a</sup> Moscow Institute of Physics and Technology (State University), Moscow, Russia
^b Department of Probability Theory, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
^c Faculty of Computer Science, Higher School of Economics—National Research University, Moscow, Russia

Abstract: We study the threshold probability for the property of existence of a special-form $r$-coloring for a random $k$-uniform hypergraph in the $H(n,k,p)$ binomial model. A parametric set of $j$-chromatic numbers of a random hypergraph is considered. A coloring of hypergraph vertices is said to be $j$-proper if every edge in it contains no more than $j$ vertices of each color. We analyze the question of finding the sharp threshold probability of existence of a $j$-proper $r$-coloring for $H(n,k,p)$. Using the second moment method, we obtain rather tight bounds for this probability provided that $k$ and $j$ are large as compared to $r$.

Keywords: random hypergraph, hypergraph colorings, $j$-chromatic number, second moment method.

UDC: 621.391 : 519.174 : 519.179.1

Received: 09.03.2020
Revised: 18.02.2022
Accepted: 18.02.2022

DOI: 10.31857/S0555292322010053

 English version: Problems of Information Transmission, 2022, 58:1, 72–101

Bibliographic databases:

• 
•