Session I.3 - Graph Theory and Combinatorics
Tuesday, June 13, 15:30 ~ 16:00
Forcing Generalized Quasirandom Graphs Efficiently
Andrzej Grzesik
Jagiellonian University, Poland - This email address is being protected from spambots. You need JavaScript enabled to view it.
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\ge 2$ parts is forced by homomorphism densities of graphs with at most $4q^2-q$ vertices. This improves earlier bounds of orders $q^q$ by Lovász and Sós and $q^8$ 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).