RUS  ENG
Full version
SEMINARS

Principle Seminar of the Department of Probability Theory, Moscow State University
September 19, 2018 16:45, Moscow, MSU, auditorium 12-24


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

D. A. Shabanovab

a Moscow Institute of Physics and Technology
b Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.


© Steklov Math. Inst. of RAS, 2024