Forcing generalised quasirandom graphs efficiently

J 2024

Forcing generalised quasirandom graphs efficiently

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO

Základní údaje

Originální název

Forcing generalised quasirandom graphs efficiently

Autoři

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO

Vydání

COMBINATORICS PROBABILITY & COMPUTING, NEW YORK, CAMBRIDGE UNIV PRESS, 2024, 0963-5483

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10100 1.1 Mathematics

Stát vydavatele

Velká Británie a Severní Irsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.800

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/24:00138601

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Graph limits; Graphons; Homomorphism density; Quasirandomness

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 4. 4. 2025 12:39, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We study generalised 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. Lovasz and Sos showed that the structure of such graphs is forced by homomorphism densities of graphs with at most $(10q)<^>q+q$ vertices; subsequently, Lovasz refined the argument to show that graphs with $4(2q+3)<^>8$ vertices suffice. Our results imply that the structure of generalised quasirandom graphs with $qge 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.

Návaznosti

MUNI/I/1677/2018, interní kód MU

Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)

Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities

Citovat

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO. Forcing generalised quasirandom graphs efficiently. COMBINATORICS PROBABILITY & COMPUTING. NEW YORK: CAMBRIDGE UNIV PRESS, 2024, roč. 33, č. 1, s. 16-31. ISSN 0963-5483. Dostupné z: https://doi.org/10.1017/S0963548323000263.

@article{2470563,
   author = {Grzesik, Andrzej and Kráľ, Daniel and Pikhurko, Oleg},
   article_location = {NEW YORK},
   article_number = {1},
   doi = {https://doi.org/10.1017/S0963548323000263},
   keywords = {Graph limits; Graphons; Homomorphism density; Quasirandomness},
   language = {eng},
   issn = {0963-5483},
   journal = {COMBINATORICS PROBABILITY & COMPUTING},
   title = {Forcing generalised quasirandom graphs efficiently},
   url = {https://doi.org/10.1017/S0963548323000263},
   volume = {33},
   year = {2024}
}

TY  - JOUR
ID  - 2470563
AU  - Grzesik, Andrzej - Kráľ, Daniel - Pikhurko, Oleg
PY  - 2024
TI  - Forcing generalised quasirandom graphs efficiently
JF  - COMBINATORICS PROBABILITY & COMPUTING
VL  - 33
IS  - 1
SP  - 16-31
EP  - 16-31
PB  - CAMBRIDGE UNIV PRESS
SN  - 09635483
KW  - Graph limits
KW  - Graphons
KW  - Homomorphism density
KW  - Quasirandomness
UR  - https://doi.org/10.1017/S0963548323000263
N2  - We study generalised 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. Lovasz and Sos showed that the structure of such graphs is forced by homomorphism densities of graphs with at most $(10q)<^>q+q$ vertices; subsequently, Lovasz refined the argument to show that graphs with $4(2q+3)<^>8$ vertices suffice. Our results imply that the structure of generalised quasirandom graphs with $qge 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.
ER  -

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO. Forcing generalised quasirandom graphs efficiently. \textit{COMBINATORICS PROBABILITY \&{}amp; COMPUTING}. NEW YORK: CAMBRIDGE UNIV PRESS, 2024, roč.~33, č.~1, s.~16-31. ISSN~0963-5483. Dostupné z: https://doi.org/10.1017/S0963548323000263.

Přehled o publikaci