Graphon - Graphon

Realizace vyměnitelného náhodného grafu definovaného a grafon. Grafon je zobrazen jako purpurová teplotní mapa (vpravo dole). Náhodný graf velikosti ${ displaystyle n}$ je generováno samostatným přiřazením ke každému vrcholu ${ displaystyle k in {1, dotsc, n }}$ latentní náhodná proměnná ${ displaystyle U_ {k} sim mathrm {U} (0,1)}$ (hodnoty podél svislé osy) a včetně každé hrany ${ displaystyle (k, l)}$ nezávisle s pravděpodobností ${ displaystyle f (U_ {k}, U_ {l})}$. Například hrana ${ displaystyle (3,5)}$ (zelená, tečkovaná) je přítomna s pravděpodobností ${ displaystyle f (0,72,0,9)}$; zelené políčka na pravém čtverci představují hodnoty ${ displaystyle (u_ {3}, u_ {5})}$ a ${ displaystyle (u_ {5}, u_ {3})}$. Levý horní panel zobrazuje realizaci grafu jako matici sousedství.

v teorie grafů a statistika, a grafon (také známý jako limit grafu) je symetrický měřitelný funkce ${ displaystyle W: [0,1] ^ {2} až [0,1]}$, to je důležité při studiu husté grafy. Grafony vznikají jednak jako přirozený pojem pro limit posloupnosti hustých grafů, jednak jako základní definující objekty vyměnitelné náhodné modely grafů. Grafony jsou spojeny s hustými grafy pomocí následující dvojice pozorování: náhodné modely grafů definované grafony dávají vzniknout hustým grafům téměř jistě a lemma pravidelnosti, grafony zachycují strukturu libovolných velkých hustých grafů.

Statistická formulace

Grafon je symetrická měřitelná funkce ${ displaystyle W: [0,1] ^ {2} až [0,1]}$. Grafonem se obvykle rozumí definování vyměnitelného náhodného modelu grafu podle následujícího schématu:

1. Každý vrchol ${ displaystyle j}$ grafu je přiřazena nezávislá náhodná hodnota ${ displaystyle u_ {j} sim U [0,1]}$
2. Okraj ${ displaystyle (i, j)}$ je do grafu nezávisle zahrnuta s pravděpodobností ${ displaystyle W (u_ {i}, u_ {j})}$.

Model náhodného grafu je vyměnitelný model náhodného grafu právě tehdy, pokud jej lze takto definovat z hlediska (případně náhodného) grafu. Model založený na pevném grafu ${ displaystyle W}$ je někdy označován ${ displaystyle mathbb {G} (n, W)}$, analogicky s Erdős – Rényi model náhodných grafů. Graf vygenerovaný grafem ${ displaystyle W}$ tímto způsobem se nazývá a ${ displaystyle W}$- náhodný graf.

Z této definice a zákona velkého počtu vyplývá, že pokud ${ displaystyle W neq 0}$, vyměnitelné náhodné modely grafů jsou husté téměř jistě.^[1]

Příklady

Nejjednodušší příklad grafonu je ${ displaystyle W (x, y) equiv p}$ pro nějakou konstantu ${ displaystyle p v [0,1]}$. V tomto případě je přidružený vyměnitelný model náhodného grafu Erdős – Rényi Modelka ${ displaystyle G (n, p)}$ který zahrnuje každou hranu samostatně s pravděpodobností ${ displaystyle p}$.

Pokud místo toho začneme s grafonem, který je po částech konstantní pomocí:

1. dělení čtverce jednotek na ${ displaystyle k krát k}$ bloky a
2. nastavení ${ displaystyle W}$ rovnat se ${ displaystyle p_ {lm}}$ na ${ displaystyle (l, m) ^ { text {th}}}$ blok,

výsledný vyměnitelný model náhodného grafu je ${ displaystyle k}$ společenství stochastický model bloku, zobecnění Erdős – Rényiho modelu. Můžeme to interpretovat jako náhodný grafový model skládající se z ${ displaystyle k}$ odlišné Erdős – Rényiho grafy s parametry ${ displaystyle p_ {ll}}$ respektive s bigrafy mezi nimi, kde každý možný okraj mezi bloky ${ displaystyle (l, l)}$ a ${ displaystyle (m, m)}$ je zahrnut samostatně s pravděpodobností ${ displaystyle p_ {lm}}$.

Mnoho dalších populárních modelů náhodných grafů lze chápat jako vyměnitelné modely náhodných grafů definované nějakým grafonem, podrobný průzkum je zahrnut v Orbanz a Roy.^[1]

Společně vyměnitelné matice sousedství

Náhodný graf velikosti ${ displaystyle n}$ může být reprezentován jako náhodný ${ displaystyle n krát n}$ matice sousedství. Za účelem zavedení konzistence (ve smyslu projektivita ) mezi náhodnými grafy různých velikostí je přirozené studovat posloupnost sousedních matic vznikající jako levý horní ${ displaystyle n krát n}$ dílčí matice nějaké nekonečné řady náhodných proměnných; to nám umožňuje generovat ${ displaystyle G_ {n}}$ přidáním uzlu do ${ displaystyle G_ {n-1}}$ a vzorkování hran ${ displaystyle (j, n)}$ pro ${ displaystyle j$. S touto perspektivou jsou náhodné grafy definovány jako náhodná nekonečná symetrická pole ${ displaystyle (X_ {ij})}$.

V návaznosti na zásadní význam vyměnitelné sekvence v klasické pravděpodobnosti je přirozené hledat analogický pojem v nastavení náhodného grafu. Jedna taková představa je dána společně vyměnitelnými maticemi; tj. náhodné matice vyhovující

${ displaystyle (X_ {ij}) { přesahující {d} {=}} , (X _ { sigma (i) sigma (j)})}$

pro všechny obměny ${ displaystyle sigma}$ přirozených čísel, kde ${ displaystyle { overset {d} {=}}}$ prostředek stejný v distribuci. Tato podmínka intuitivně znamená, že distribuce náhodného grafu se nezmění pomocí rebrandingu jeho vrcholů: to znamená, že štítky vrcholů neobsahují žádné informace.

Existuje věta o reprezentaci pro společně vyměnitelné matice náhodných sousedů, analogické k de Finettiho věta o reprezentaci pro vyměnitelné sekvence. Toto je zvláštní případ Aldous – Hooverova věta pro společně vyměnitelná pole a v tomto nastavení tvrdí, že náhodná matice ${ displaystyle (X_ {ij})}$ generuje:

1. Vzorek ${ displaystyle u_ {j} sim U [0,1]}$ nezávisle
2. ${ displaystyle X_ {ij} = X_ {ji} = 1}$ nezávisle náhodně s pravděpodobností ${ displaystyle W (u_ {i}, u_ {j}),}$

kde ${ displaystyle W: [0,1] ^ {2} až [0,1]}$ je (možná náhodný) grafon. To znamená, že model náhodného grafu má společně vyměnitelnou matici sousedství právě tehdy, pokud se jedná o společně vyměnitelný model náhodného grafu definovaný v podmínkách nějakého grafu.

Odhad grafu

Kvůli problémům s identifikovatelností není možné odhadnout ani grafovou funkci ${ displaystyle W}$ nebo latentní polohy uzlu ${ displaystyle u_ {i},}$ a existují dva hlavní směry odhadu grafonu. Jeden směr má za cíl odhadnout ${ displaystyle W}$až do třídy ekvivalence,^[2][3] nebo odhadněte matici pravděpodobnosti vyvolanou ${ displaystyle W}$.^[4][5]

Analytická formulace

Libovolný graf ${ displaystyle n}$ vrcholy ${ displaystyle {1,2, tečky, n }}$ lze identifikovat s jeho matice sousedství ${ displaystyle A_ {G}}$.Tato matice odpovídá stupňovité funkci ${ displaystyle W_ {G}: [0,1] ^ {2} až [0,1]}$, definované rozdělením ${ displaystyle [0,1]}$ do intervalů ${ displaystyle I_ {1}, I_ {2}, tečky, I_ {n}}$ takhle ${ displaystyle I_ {j}}$ má interiér

$${ displaystyle left ({ frac {j-1} {n}}, { frac {j} {n}} right)}$$

${ displaystyle (x, y) v I_ {i} krát I_ {j}}$

${ displaystyle W_ {G} (x, y)}$

${ displaystyle (i, j) ^ { text {th}}}$

${ displaystyle A_ {G}}$

${ displaystyle W_ {G}}$

${ displaystyle G}$

Obecně platí, že pokud máme posloupnost grafů ${ displaystyle (G_ {n})}$ kde je počet vrcholů ${ displaystyle G_ {n}}$ jde do nekonečna, můžeme analyzovat omezující chování sekvence zvážením omezujícího chování funkcí ${ displaystyle (W_ {G_ {n}})}$. Pokud tyto grafy konvergují (podle nějaké vhodné definice konvergence ), pak očekáváme, že limit těchto grafů bude odpovídat limitu těchto přidružených funkcí.

To motivuje definici grafonu (zkratka pro „funkci grafu“) jako symetrické měřitelné funkce ${ displaystyle W: [0,1] ^ {2} až [0,1]}$ který zachycuje pojem limitu posloupnosti grafů. Ukazuje se, že pro sekvence hustých grafů je několik zjevně odlišných představ o konvergenci ekvivalentních a pod všemi z nich je přirozeným limitním objektem graf.^[6]

Příklady

Příklad 1: Vezměte náhodnou sekvenci ${ displaystyle (G_ {n})}$ Erdős – Rényiho grafy ${ displaystyle G_ {n} = G (n, p)}$ s nějakým pevným parametrem ${ displaystyle p}$.Intuitivně, jak ${ displaystyle n}$ má tendenci k nekonečnu, limit této posloupnosti grafů je určen pouze hustotou hran těchto grafů.

V prostoru grafonů se ukazuje, že taková posloupnost konverguje téměř jistě do konstanty ${ displaystyle W (x, y) equiv p}$, který zachycuje výše uvedenou intuici.

Příklad 2: Vezměte sekvenci ${ displaystyle (H_ {n})}$ z poloviční grafy, definovaný převzetím ${ displaystyle H_ {n}}$ být bipartitním grafem ${ displaystyle 2n}$ vrcholy ${ displaystyle u_ {1}, u_ {2}, tečky, u_ {n}}$ a ${ displaystyle v_ {1}, v_ {2}, tečky, v_ {n}}$ takhle ${ displaystyle u_ {i}}$ sousedí s ${ displaystyle v_ {j}}$ přesně kdy ${ Displaystyle i leq j}$. Pokud jsou vrcholy uvedeny v uvedeném pořadí, pak matice sousedství ${ displaystyle A_ {H_ {n}}}$ má dva rohy blokových matic „půl čtverečních“ vyplněných jednotkami, přičemž ostatní položky se rovnají nule. Například matice sousedství ${ displaystyle H_ {3}}$ je dána

${ displaystyle { begin {bmatrix} 0 & 0 & 0 & 1 & 1 & 1 0 & 0 & 0 & 0 & 1 & 1 0 & 0 & 0 & 0 & 0 1 1 & 0 & 0 & 0 & 0 0 1 1 & 0 & 0 & 0 0 1 & 1 & 1 & 0 & 0 end {bmatrix}}}$

Tak jako ${ displaystyle n}$ zvětší se, tyto rohy těch „vyhladí“. Shoduje se s touto intuicí, posloupností ${ displaystyle (H_ {n})}$ konverguje k půl grafu ${ displaystyle W}$ definován ${ displaystyle W (x, y) = 1}$ když ${ displaystyle | x-y | geq 1/2}$ a ${ displaystyle W (x, y) = 0}$ v opačném případě.

Příklad 3: Vezměte sekvenci ${ displaystyle (K_ {n, n})}$ z kompletní bipartitní grafy Pokud objednáme vrcholy umístěním všech vrcholů do jedné části na začátku a umístěním vrcholů druhé části na konec, matice sousedství ${ displaystyle (K_ {n, n})}$ vypadá jako blok mimo diagonální matici se dvěma bloky jednotek a dvěma bloky nul. Například matice sousedství ${ displaystyle K_ {2,2}}$ je dána

${ displaystyle { begin {bmatrix} 0 & 0 & 1 & 1 0 & 0 & 1 & 1 1 & 1 & 0 & 0 1 & 1 & 0 & 0 end {bmatrix}}.}$

Tak jako ${ displaystyle n}$ zvětšuje se, tato bloková struktura matice sousedství zůstává konstantní, takže tato posloupnost grafů konverguje k „úplnému bipartitnímu“ grafu ${ displaystyle W}$definován ${ displaystyle W (x, y) = 1}$ kdykoli ${ displaystyle min (x, y) leq 1/2}$ a ${ displaystyle max (x, y)> 1/2}$a nastavení ${ displaystyle W (x, y) = 0}$ v opačném případě.

Příklad 4: Zvažte sekvenci ${ displaystyle (K_ {n, n})}$ Pokud si místo toho objednáme vrcholy střídáním částí, matice sousedství má šachovnicovou strukturu nul a jedniček. Například v tomto pořadí matice sousedství ${ displaystyle K_ {2,2}}$ je dána

${ displaystyle { begin {bmatrix} 0 & 1 & 0 & 1 1 & 0 & 1 & 0 0 & 1 & 0 & 1 1 & 0 & 1 & 0 end {bmatrix}}.}$

Tak jako ${ displaystyle n}$ zvětší, matice sousedství se stanou jemnější a jemnější šachovnicí. I přes toto chování stále chceme limit ${ displaystyle (K_ {n, n})}$ být jedinečný a vyústit v graf z příkladu 4. To znamená, že když formálně definujeme konvergenci pro posloupnost grafů, definice limitu by měla být agnostická vůči relabelingům vrcholů.

Příklad 5: Vezměte náhodnou sekvenci ${ displaystyle (G_ {n})}$ z ${ displaystyle W}$- běžné grafy kreslením ${ displaystyle G_ {n} sim mathbb {G} (n, W)}$ pro nějaký pevný graf ${ displaystyle W}$Pak se stejně jako v prvním příkladu z této části ukazuje, že ${ displaystyle (G_ {n})}$ konverguje k ${ displaystyle W}$ téměř jistě.

Příklad 6: Daný graf ${ displaystyle G}$ s přidruženým grafonem ${ displaystyle W = W_ {G}}$, můžeme obnovit teoretické vlastnosti grafů a parametry ${ displaystyle G}$ integrací transformací ${ displaystyle W}$.

Například okrajová hustota (tj. Průměrný stupeň dělený počtem vrcholů) z ${ displaystyle G}$ je dáno integrálem${ displaystyle int _ {0} ^ {1} int _ {0} ^ {1} W (x, y) ; mathrm {d} x , mathrm {d} y.}$To je proto, že ${ displaystyle W}$ je ${ displaystyle {0,1 }}$-hodnota a každá hrana ${ displaystyle (i, j)}$v ${ displaystyle G}$ odpovídá regionu ${ displaystyle I_ {i} krát I_ {j}}$oblasti ${ displaystyle 1 / n ^ {2}}$ kde ${ displaystyle W}$ rovná se ${ displaystyle 1}$.

Podobné uvažování ukazuje, že počet trojúhelníků v ${ displaystyle G}$ je rovný${ displaystyle { frac {1} {6}} int _ {0} ^ {1} int _ {0} ^ {1} int _ {0} ^ {1} W (x, y) W (y, z) W (z, x) ; mathrm {d} x , mathrm {d} y , mathrm {d} z.}$

Pojmy konvergence

Existuje mnoho různých způsobů, jak měřit vzdálenost mezi dvěma grafy. Pokud nás zajímají metriky, které „zachovávají“ extrémní vlastnosti grafů, měli bychom omezit naši pozornost na metriky, které identifikují náhodné grafy jako podobné. Například pokud náhodně nakreslíme dva grafy nezávisle na modelu Erdős – Rényi ${ displaystyle G (n, p)}$ pro některé pevné ${ displaystyle p}$, vzdálenost mezi těmito dvěma grafy pod „rozumnou“ metrikou by měla být blízká nule s velkou pravděpodobností pro velké ${ displaystyle n}$.

Existují dvě přirozené metriky, které se v tomto smyslu chovají dobře na hustých náhodných grafech. První je metrika vzorkování, která říká, že dva grafy jsou blízké, pokud jsou jejich distribuce podgrafů blízké. Druhá je hrana rozpor metrika, která říká, že dva grafy jsou blízké, když jsou jejich okrajové hustoty blízké u všech jejich odpovídajících podmnožin vrcholů.

Sekvence grafů jako zázrakem konverguje s ohledem na jednu vzdálenost právě tehdy, když konverguje s ohledem na druhou. Limitní objekty pod oběma vzdálenostmi se navíc projeví v grafech. Ekvivalence těchto dvou pojmů konvergence zrcadlí, jak různé pojmy kvazirandom grafy jsou ekvivalentní.^[7]

Počty podgrafů

Jeden způsob, jak měřit vzdálenost mezi dvěma grafy ${ displaystyle G}$ a ${ displaystyle H}$ je porovnat jejich relativní počty podgrafů. To znamená pro každý graf ${ displaystyle F}$ můžeme porovnat počet kopií ${ displaystyle F}$ v ${ displaystyle G}$ a ${ displaystyle F}$ v ${ displaystyle H}$Pokud jsou tato čísla blízká pro každý graf ${ displaystyle F}$, potom intuitivně ${ displaystyle G}$ a ${ displaystyle H}$ jsou podobně vypadající grafy.

Hustoty homomorfismu

Spíše než pracovat přímo s podgrafy se ukazuje, že je snadnější pracovat s homomorfismy grafů, což je v pořádku, když se jedná o velké a husté grafy, protože v tomto scénáři je počet podgrafů a počet homomorfismů grafů z pevného grafu asymptoticky stejný .

Vzhledem ke dvěma grafům ${ displaystyle F}$ a ${ displaystyle G}$, hustota homomorfismu ${ displaystyle t (F, G)}$ z ${ displaystyle F}$ v ${ displaystyle G}$ je definován jako počet homomorfismy grafů z ${ displaystyle F}$ na ${ displaystyle G}$ .Jinými slovy, ${ displaystyle t (F, G)}$ je pravděpodobnost náhodně vybrané mapy z vrcholů ${ displaystyle F}$ k vrcholům ${ displaystyle G}$ posílá sousední vrcholy dovnitř ${ displaystyle F}$ na sousední vrcholy v ${ displaystyle G}$.

Grafony nabízejí jednoduchý způsob výpočtu hustoty homomorfismu. Daný graf ${ displaystyle G}$ s přidruženým grafonem ${ displaystyle W_ {G}}$ a další ${ displaystyle F}$, my máme

${ displaystyle t (F, G) = int prod _ {(i, j) v E (F)} W_ {G} (x_ {i}, x_ {j}) ; doleva { mathrm {d} x_ {i} right } _ {i ve V (F)}}$

kde je integrál vícerozměrný, převzatý jednotkou hyperkrychle ${ displaystyle [0,1] ^ {V (F)}}$To vyplývá z definice přidruženého grafonu tím, že se vezme v úvahu, kdy se výše uvedená integrand rovná ${ displaystyle 1}$Poté můžeme definici hustoty homomorfismu rozšířit na libovolné grafony ${ displaystyle W}$pomocí stejného integrálu a definování

${ displaystyle t (F, W) = int prod _ {(i, j) v E (F)} W (x_ {i}, x_ {j}) ; vlevo { mathrm {d } x_ {i} doprava } _ {i ve V (F)}}$

pro jakýkoli graf ${ displaystyle F}$.

Meze z hlediska hustoty homomorfismu

Vzhledem k tomuto nastavení říkáme posloupnost grafů ${ displaystyle (G_ {n})}$ konverguje, pokud pro každý pevný graf ${ displaystyle F}$posloupnost hustot homomorfismu ${ displaystyle left (t (F, G_ {n}) right)}$ konverguje. Ačkoli to není zřejmé ze samotné definice, pokud ${ displaystyle (G_ {n})}$ konverguje v tomto smyslu, pak vždy existuje grafon ${ displaystyle W}$ tak, že pro každý graf ${ displaystyle F}$, my máme

$${ displaystyle lim _ {n to infty} t (F, G_ {n}) = t (F, W)}$$

Vzdálenost řezu

Vezměte dva grafy ${ displaystyle G}$ a ${ displaystyle H}$ protože tyto grafy sdílejí stejné vrcholy, jedním ze způsobů měření jejich vzdálenosti je omezení na podmnožiny ${ displaystyle X, Y}$ sady vrcholů a pro každou takovou dvojici podmnožiny porovnejte počet hran ${ displaystyle e_ {G} (X, Y)}$ z ${ displaystyle X}$ na ${ displaystyle Y}$ v ${ displaystyle G}$ na počet hran ${ displaystyle e_ {H} (X, Y)}$ mezi ${ displaystyle X}$ a ${ displaystyle Y}$ v ${ displaystyle H}$Pokud jsou tato čísla pro každou dvojici podmnožin podobná (vzhledem k celkovému počtu vrcholů), pak to naznačuje ${ displaystyle G}$ a ${ displaystyle H}$ jsou podobné grafy.

Abychom to formalizovali, pro jakoukoli symetrickou měřitelnou funkci ${ displaystyle f: [0,1] ^ {2} to mathbb {R}}$, definovat řezná norma z ${ displaystyle f}$ být množství

${ displaystyle lVert f rVert _ { square} = sup _ {S, T subseteq [0,1]} left | int _ {S} int _ {T} f (x, y) ; mathrm {d} x , mathrm {d} y doprava |}$

převzal všechny měřitelné podmnožiny ${ displaystyle S, T}$ jednotkového intervalu. ^[6]Tato norma zachycuje naši dřívější představu o vzdálenosti, protože pro dva grafy ${ displaystyle G}$ a ${ displaystyle H}$ se stejnou sadou vrcholů ${ displaystyle V}$ velikosti ${ displaystyle | V | = n}$, řezná norma s přidruženými grafony

${ displaystyle lVert W_ {G} -W_ {H} rVert _ { square} = { frac {1} {n ^ {2}}} max _ {X, Y subseteq V} vlevo | e_ {G} (X, Y) -e_ {H} (X, Y) doprava |}$

pojďme vypočítat maximální rozdíl mezi hraničními hustotami ${ displaystyle G}$ a ${ displaystyle H}$.Tato definice může být stále použita, i když porovnávané grafy nesdílejí sadu vrcholů.

Toto měření vzdálenosti má stále jedno hlavní omezení: může přiřadit nenulovou vzdálenost dvěma izomorfním grafům. Aby se ujistilo, že izomorfní grafy mají vzdálenost nula, měli bychom vypočítat minimální normu řezu pro všechna možná „zpětná vazba“ vrcholů. To motivuje definici the vzdálenost řezu mezi dvěma grafony ${ displaystyle W}$ a ${ displaystyle U}$ být

${ displaystyle delta _ { square} (U, W) = inf _ { varphi} lVert U-W ^ { varphi} rVert _ { square}}$

kde ${ displaystyle W ^ { varphi} (x, y) = W ( varphi (x), varphi (y))}$ je složení ${ displaystyle W}$ s mapou ${ displaystyle varphi}$a infimum je převzato všemi zachování opatření bijekce z jednotkového intervalu k sobě samému.^[8]Vzdálenost řezu mezi dvěma grafy je definována jako vzdálenost řezu mezi jejich přidruženými grafony.

Jako metrický prostor

Abychom provedli vzdálenost řezu do metriky, vezmeme množinu všech grafů a identifikovat dva grafony ${ displaystyle U sim W}$ kdykoli ${ displaystyle delta _ { square} (U, W) = 0}$Výsledný prostor grafonů je označen ${ displaystyle { tilde { mathcal {W}}} _ {0}}$a společně s ${ displaystyle delta _ { square}}$ tvoří a metrický prostor.

Ukázalo se, že tento prostor je kompaktní Kromě toho obsahuje sadu všech konečných grafů jako a hustá podmnožina Zde jsou grafy identifikovány jako ${ displaystyle {0,1 }}$- funkce krokových funkcí na jednotkovém čtverci. Tato pozorování ukazují, že prostor grafonů je a dokončení prostoru grafů s ohledem na vzdálenost řezu.

Aplikace

Lemma pravidelnosti

Využití kompaktnosti prostoru grafonů ${ displaystyle ({ tilde { mathcal {W}}} _ {0}, delta _ { square})}$, lze prokázat silnější verze Szemerédiho lemma pravidelnosti.

Sidorenkova domněnka

Analytická povaha grafonů umožňuje větší flexibilitu při útoku na nerovnosti související s homomorfismy.

Například Sidorenkova domněnka je hlavním otevřeným problémem teorie extrémních grafů, který tvrdí, že pro jakýkoli graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy s průměrným stupněm ${ displaystyle pn}$ (pro některé ${ displaystyle p v [0,1]}$) a bipartitní graf ${ displaystyle H}$ na ${ displaystyle v}$ vrcholy a ${ displaystyle e}$ hran, počet homomorfismy z ${ displaystyle H}$ na ${ displaystyle G}$ je alespoň ${ displaystyle p ^ {e} n ^ {v}}$.^[9]Jelikož se jedná o množství, je očekávaný počet označených podgrafů ${ displaystyle H}$ v náhodném grafu ${ displaystyle G (n, p)}$, lze domněnku interpretovat jako tvrzení, že pro jakýkoli bipartitní graf ${ displaystyle H}$, náhodný graf dosahuje (v očekávání) minimálního počtu kopií ${ displaystyle H}$ přes všechny grafy s určitou pevnou hranovou hustotou.

Mnoho přístupů k Sidorenkově domněnce formuluje problém jako integrální nerovnost na grafech, což pak umožňuje útok na problém pomocí jiných analytických přístupů. ^[10]

Zobecnění

Grafony jsou přirozeně spojeny s hustými jednoduchými grafy. Existují rozšíření tohoto modelu o husté směrované vážené grafy, často označované jako zdobené grafony.^[11] Existují také nedávná rozšíření režimu řídkých grafů, a to jak z pohledu modelů náhodných grafů ^[12] a teorie mezí grafů.^[13][14]

Reference