On the limit distribution of the chromatic number of a random graph

A random graph in the binomial model $G(n,p)$ (a random graph in the Erdős–Renyi model) has been the main object of study in the probabilistic combinatorics since the end of the 50-s of the past century. One of first question posed by P. Erdős was a question concerning the asymptotic behavior of the chromatic number of the random graph $G(n,1/2)$, i.e. of the “typical” chromatic number of a graph on $n$ vertices. This problem attracted the attention of all the world's leading researchers in the probabilistic combinatorics, but the law of the large numbers for the chromatic number of $G(n,1/2)$ was established by B. Bollobás only in 1998. His approach based on the application of the large deviation inequalities for martingales turned out to be very flexible and allowed to study the chromatic number of $G(n,p)$ for different relations between the parameters $p=p(n)$ and $n$. For not fast growing product $np$, it turns out to be concentrated in two consecutive numbers, which however were unknown. We present our recent results where these values have been found for almost all functions $p=p(n)$ up to $o(n^{-3/4})$. Moreover, we discuss similar questions for the RANDOM $k$-SAT problem concerning the feasibility of a random Boolean function and some its natural generalizations concerning panchromatic colorings of hypergraphs.