Videolibrary
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 Video Library Archive Most viewed videos Search RSS New in collection

À.A.Karatsuba's 80th Birthday Conference in Number Theory and Applications
May 27, 2017 12:10–12:40, 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
 Video records: MP4 216.1 Mb

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 Erdős–Ré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, …, 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.