Session I.3 - Graph Theory and Combinatorics
Tuesday, June 13, 15:30 ~ 16:00
Forcing Generalized Quasirandom Graphs Efficiently
Andrzej Grzesik
Jagiellonian University, Poland - Andrzej.Grzesik@uj.edu.pl
The classical result on quasirandom graphs states that a sequence of graphs is quasirandom with density p if and only if the homomorphism densities of the edge and the 4-cycle in this sequence converge to their expected densities in the random graph with density p. Shortly speaking, the structure of quasirandom graphs is forced by homomorphism densities of graphs with at most 4 vertices. We will consider analogous concept for generalized quasirandom graphs whose vertex set consists of q parts (of not necessarily the same sizes) with edges within each part and between each pair of parts distributed quasirandomly. Such graphs correspond to the stochastic block model studied in statistics and network science.
We will show that the structure of generalized quasirandom graphs with q≥2 parts is forced by homomorphism densities of graphs with at most 4q2−q vertices. This improves earlier bounds of orders qq by Lovász and Sós and q8 by Lovász. Additionally, we will show that if vertices in distinct parts have distinct degrees, then 2q+1 vertices suffice, which improves the bound of 8q−4 due to Spencer.
Joint work with Daniel Král’ (Masaryk University, Czech Republic) and Oleg Pikhurko (University of Warwick, United Kingdom).