Hypotes Sidorenko

Sidorenkos gissning från grafteorin rör en uppskattning av antalet homomorfismer av någon (godtycklig men fixerad) graf till en godtycklig graf . Hon konstaterar att för en tvådelad siffra är aldrig lägre än för en graf med slumpmässig storlek med samma förväntade kanttäthet som . $H$ $G$ $H$ $|G|$ $G$

Gissningen framfördes av Alexander Sidorenko 1986 [1] (ett särskilt fall bevisades ännu tidigare [2] ). Det har bevisats med olika metoder för vissa klasser av grafer , men är långt ifrån en generell lösning. $H$

Formulering

Låt beteckna antalet homomorfismer från graf till graf . Låt särskilt ange antalet kanter i . Låt också beteckna "densiteten" av sådana homomorfismer bland alla mappningar av hörn till hörn . $h_{H}(G)$ $H$ $G$ $h_{K_{2}}(G)$ $G$ ${\displaystyle t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|)))))$ $H$ $G$

Hypotes Sidorenko

Om är en tvådelad kantgraf , så är det sant för vilken graf som helst $H$ $m$ $G$ $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

Vanligtvis betraktas en hypotes som en uppsättning påståenden för olika och man talar om dess lösning just för en eller annan och godtycklig . $H$ $H$ $G$

Sidorenko formulerade ursprungligen uttalandet i en mer allmän form, för ett mått på viktade kontinuumgrafer (de så kallade grafonerna ). [3]

Tolkning genom slumpen

För en slumpmässig graf i modellen motsvarar det förväntade antalet kanter och det förväntade antalet förekomster av grafen lika med exakt likheten i Sidorenko-förmodan. $G(n,p)$ ${\mathbb {E} }\ {t_{K_{2}}(G)}=np$ $H$ ${\displaystyle {\mathbb {E} }\ t_{H}(G)=n^{|V(H)|}p^{|E(H)|))$

Vid en första anblick kan bedömningen att en viss kvantitet (här antalet förekomster ) är "aldrig mindre än genomsnittet" tyckas paradoxalt, eftersom detta skulle innebära att alla värden på kvantiteten är lika med genomsnittet. Detta skulle vara så om tolkningen genom slumpmässighet betraktade modellen av slumpmässiga Erdős-Rényi-grafer med ett fast antal kanter, eftersom uppskattningen i Sidorenko-förmodan beror på det faktiska antalet kanter i grafen. Och i modellen kommer bara det förväntade antalet kanter att vara lika med det. det vill säga, medelvärdesbildning görs inte bara över grafer av samma storlek som den givna, och även över grafer för vilka Sidorenko-hypotesen ger väldigt olika uppskattningar för antalet förekomster . $H$ $G(n,m)$ $G(n,p)$ $H$

Vissa resultat

Hypotesen har bevisats för:

stigar [4] ;
cykler av jämn längd [5] ;
träd [6] ;
hyperkubgrafer [7] ;
kompletta tvådelade grafer [8] ;
för tvådelade grafer med storleken på en av delarna som inte överstiger 4 [9] ;
för grafer som har minst en vertex som gränsar till alla hörn av den motsatta andelen [10] .

Många av resultaten har kombinerats till ett enda beviskoncept genom att använda entropins egenskaper från informationsteorin . [11] [12]

Det finns också kända resultat för konstruktion av grafer: för alla tvådelade grafer finns det ett antal så att om vi duplicerar hörn av en av delarna (tillsammans med utgående kanter) gånger, så kommer den resulterande grafen att uppfylla Sidorenko-förmodan [13 ] . $sid$ $sid$

Förmodan är dock fortfarande öppen för många grafer. Till exempel för (en fullständig tvådelad graf utan en Hamiltonsk cykel ). ${\displaystyle K_{5,5}\setminus C_{10))$

Anteckningar

↑ Se omnämnandet av detta i Sidorenko, 1993 före hypotes 1
↑ Mulholland, Smith, 1959 .
↑ Sidorenko, 1993 .
↑ Mulholland, Smith, 1959 , se uttalande i början av sid. 674 kl $v=(1,\dots ,1)$
↑ Sidorenko, 1991 , exempel 1
↑ Sidorenko, 1991 , konsekvens 1
↑ Hatami, 2010 .
↑ Sidorenko, 1991 , se sats 5 och anmärkningen efter den
↑ Sidorenko, 1991 , se sats 1 och anmärkningen efter den
↑ Conlon, Sudakov, Fox, 2010 , sats 1.2
↑ Szegedy, 2015 .
↑ Entropi och Sidorenkos förmodan - efter Szegedy arkiverad 26 september 2020 på Wayback Machine , granskad på Gowers blogg
↑ Conlon, Lee, 2018 , följd 1.2

Litteratur

HP Mulholland, CAB Smith. An Inequality Rising in Genetical Theory // The American Mathematical Monthly. - 1959. - Vol. 66 , iss. 8 . — S. 673–683 .

A. Sidorenko. En korrelationsojämlikhet för tvådelade grafer // Grafer och kombinatorik. - 1993. - Vol. 9 . — S. 201–204 .

A. F. Sidorenko. Ojämlikheter för funktionaler genererade av tvådelade grafer // Diskret matematik. - 1991. - Vol. 3 , nummer. 3 . — S. 50–65 . (ryska)

H. Hatami. Grafnormer och Sidorenkos gissning (engelska) // Israel Journal of Mathematics. - 2010. - Vol. 175 . — S. 125–150 . - arXiv : 0806.0047 .

D. Conlon, J. Fox, B. Sudakov. En ungefärlig version av Sidorenkos förmodan // Geometrisk och funktionell analys. - 2010. - Vol. 20 . - P. 1354-1366 . - arXiv : 1004.4236 .

D. Conlon, J. Lee. Sidorenkos gissning för blow-ups . - 2018. - arXiv : 1809.01259 .

B. Szegedy. En informationsteoretisk ansats till Sidorenkos gissning (engelska) . - 2015. - arXiv : 1406.6738v3 .