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

Number of views:
This page:345
Video files:83

A. M. Raigorodskii



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
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024