Forcing Generalized Quasirandom Graphs Efficiently

D 2023

Forcing Generalized Quasirandom Graphs Efficiently

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO

Základní údaje

Originální název

Forcing Generalized Quasirandom Graphs Efficiently

Autoři

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO

Vydání

Brno, European Conference on Combinatorics, Graph Theory and Applications, od s. 503-510, 8 s. 2023

Nakladatel

MUNI Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Česká republika

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/23:00133884

Organizační jednotka

Fakulta informatiky

ISSN

DOI

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-070

UT WoS

001448447300070

Klíčová slova anglicky

graph limits; quasirandomness; stochastic block model

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 13. 8. 2025 18:23, Mgr. Petra Trembecká, Ph.D.

Anotace

V originále

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.

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 Generalized Quasirandom Graphs Efficiently. Online. In European Conference on Combinatorics, Graph Theory and Applications. Brno: MUNI Press, 2023, s. 503-510. ISSN 2788-3116. Dostupné z: https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-070.

@inproceedings{2386889,
   author = {Grzesik, Andrzej and Kráľ, Daniel and Pikhurko, Oleg},
   address = {Brno},
   booktitle = {European Conference on Combinatorics, Graph Theory and Applications},
   doi = {https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-070},
   keywords = {graph limits; quasirandomness; stochastic block model},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Brno},
   pages = {503-510},
   publisher = {MUNI Press},
   title = {Forcing Generalized Quasirandom Graphs Efficiently},
   url = {https://journals.muni.cz/eurocomb/article/view/35604},
   year = {2023}
}

TY  - CONF
ID  - 2386889
AU  - Grzesik, Andrzej - Kráľ, Daniel - Pikhurko, Oleg
PY  - 2023
TI  - Forcing Generalized Quasirandom Graphs Efficiently
PB  - MUNI Press
CY  - Brno
KW  - graph limits
KW  - quasirandomness
KW  - stochastic block model
UR  - https://journals.muni.cz/eurocomb/article/view/35604
N2  - 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.
ER  -

GRZESIK, Andrzej; Daniel KRÁĽ a Oleg PIKHURKO. Forcing Generalized Quasirandom Graphs Efficiently. Online. In \textit{European Conference on Combinatorics, Graph Theory and Applications}. Brno: MUNI Press, 2023, s.~503-510. ISSN~2788-3116. Dostupné z: https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-070.

Přehled o publikaci