RUS  ENG
Full version
VIDEO LIBRARY

À.A.Karatsuba's 80th Birthday Conference in Number Theory and Applications
May 27, 2017 12:10, Moscow, Department of Mechanics and Mathematics, Lomonosov Moscow State University


On the chromatic numbers of random graphs

A. M. Raigorodskii

Department of Innovations and High Technology, Moscow Institute of Physics and Technology



Abstract: In my talk, I suppose to speak about the chromatic numbers of random subgraphs in some graph sequences. First, I will present some classical results on the chromatic numbers of Erdős–Rényi graphs. Then, I will proceed to the discussion of new questions. For example, I will consider a sequence of graphs $G(n,r,s)$, where $n\to\infty $ and $r = r(n)$, $s = s(n)$. The set of vertices of $G(n,r,s)$ consists of all $r$ -subsets of the set $\{1, \dots, n\}$. Any two vertices are joined by an edge, if the corresponding sets intersect in exactly $s$ elements. Such graphs are related to coding theory, Ramsey theory and combinatorial geometry. I will define random subgraphs $G_{p}(n,r,s)$ of $G(n,r,s)$, where $p = p(n)\in [0,1]$ is the probability of keeping any edge in $G(n,r,s)$ independently of each other. I will discuss recent results concerning the chromatic numbers of such random graphs.

Language: English


© Steklov Math. Inst. of RAS, 2024