Forcing Generalized Quasirandom Graphs Efficiently

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GRZESIK Andrzej KRÁĽ Daniel PIKHURKO Oleg

Rok publikování 2023
Druh Článek ve sborníku
Konference European Conference on Combinatorics, Graph Theory and Applications
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://journals.muni.cz/eurocomb/article/view/35604
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-070
Klíčová slova graph limits; quasirandomness; stochastic block model
Popis We study 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. Lovász and Sós showed that the structure of such graphs is forced by homomorphism densities of graphs with at most (10q)^q+q vertices; subsequently, Lovász refined the argument to show that graphs with 4(2q+3)^8 vertices suffice. Our results imply that the structure of generalized quasirandom graphs with q>=2 parts is forced by homomorphism densities of graphs with at most 4q^2-q vertices, and, if vertices in distinct parts have distinct degrees, then 2q+1 vertices suffice. The latter improves the bound of 8q-4 due to Spencer.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.