Forcing generalised quasirandom graphs efficiently

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00138601" target="_blank" >RIV/00216224:14330/24:00138601 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1017/S0963548323000263" target="_blank" >https://doi.org/10.1017/S0963548323000263</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1017/S0963548323000263" target="_blank" >10.1017/S0963548323000263</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Forcing generalised quasirandom graphs efficiently

Popis výsledku v původním jazyce

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)&lt;^&gt;q+q$ vertices; subsequently, Lovasz refined the argument to show that graphs with $4(2q+3)&lt;^&gt;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&lt;^&gt;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ázev v anglickém jazyce

Forcing generalised quasirandom graphs efficiently

Popis výsledku anglicky

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)&lt;^&gt;q+q$ vertices; subsequently, Lovasz refined the argument to show that graphs with $4(2q+3)&lt;^&gt;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&lt;^&gt;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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

COMBINATORICS PROBABILITY &amp; COMPUTING

ISSN

0963-5483

e-ISSN

—

Svazek periodika

33

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

16

Strana od-do

16-31

Kód UT WoS článku

001119147100001

EID výsledku v databázi Scopus

2-s2.0-85170671972