Abstract

The talk deals with estimating the probability threshold for r-colorability of a random hypergraph. Let H(n,k,p) denote the classical binomial model of a random k-uniform hypergraph: every edge of a complete k-uniform hypergraph on n vertices is included into H(n,k,p) independently with probability p.

We study the question of estimating the probability threshold for the r-colorability property of H(n,k,p). It is well known that for fixed r>=2 and $k>=2, this threshold appears in the sparse case when the expected number of edges is a linear function cn for some fixed c>0.

We will present a new lower bound for the r-colorability threshold which improves previous result of Dyer, Frieze and Greenhill (2015) and provides a bounded gap with the known upper bound. For the case r>>k, a slightly better result was recently obtained by Ayre, Coja-Oghlan and Greenhill (2015+).

The proof of the main result is based on a new approach to the second moment method. We will also discuss the applications of the used technique to the non-classical colorings of random hypergraphs.