Hypoteesi Sidorenko

Sidorenkon arvelu graafiteoriasta koskee arviota jonkin (mielivaltaisen mutta kiinteän) graafin homomorfismien lukumäärästä mielivaltaiseksi graafiksi . Hän toteaa, että kaksiosaiselle tämä luku ei ole koskaan pienempi kuin satunnaisen kokoiselle graafille , jolla on sama odotettu reunatiheys kuin . $H$ $G$ $H$ $|G|$ $G$

Arvauksen esitti Alexander Sidorenko vuonna 1986 [1] (erityinen tapaus todistettiin jo aikaisemmin [2] ). Se on todistettu useilla menetelmillä joillekin graafiluokille , mutta se on kaukana yleisestä ratkaisusta. $H$

Sanamuoto

Olkoon merkitsee homomorfismien lukumäärää graafista toiseen . Erityisesti anna tarkoittaa reunojen lukumäärää . Merkitään myös tällaisten homomorfismien "tiheys" kaikkien pisteiden ja kärkipisteiden kuvauksissa . $h_{H}(G)$ $H$ $G$ $h_{K_{2}}(G)$ $G$ ${\displaystyle t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|))))$ $H$ $G$

Hypoteesi Sidorenko

Jos on kaksiosainen reunagraafi , niin mille tahansa graafille se on totta $H$ $m$ $G$ $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

Yleensä hypoteesia pidetään joukkona väitteitä eri väitteille ja sen ratkaisusta puhutaan juuri yhdelle tai toiselle ja mielivaltaisesti . $H$ $H$ $G$

Sidorenko muotoili lausunnon alun perin yleisemmässä muodossa painotettujen jatkumograafien (ns. grafonit ) mittaa varten. [3]

Tulkinta sattuman kautta

Mallin satunnaisessa graafissa odotettu reunojen määrä ja graafin odotettu esiintymistiheys vastaavat täsmälleen Sidorenkon arvelun yhtäläisyyttä. $G(n,p)$ ${\mathbb {E} }\ {t_{K_{2}}(G)}=np$ $H$ ${\näyttötyyli {\mathbb {E} }\ t_{H}(G)=n^{|V(H)|}p^{|E(H)|}}$

Ensi silmäyksellä arvio siitä, että tietty määrä (tässä esiintymien lukumäärä ) on "ei koskaan pienempi kuin keskiarvo", voi tuntua paradoksaalliselta, koska tämä tarkoittaisi, että suuren kaikki arvot ovat yhtä suuret kuin keskiarvo. Näin olisi, jos satunnaisuuden kautta tapahtuvassa tulkinnassa otettaisiin huomioon satunnaisten Erdős-Rényi-graafien malli, joissa on kiinteä määrä reunoja, koska Sidorenko-oletuksen estimaatti riippuu graafin todellisesta reunojen lukumäärästä. Ja mallissa vain odotettu reunojen määrä on yhtä suuri kuin se. eli keskiarvoa ei tehdä vain samankokoisille graafisille kuin annettu, vaan myös graafiille, joille Sidorenkon hypoteesi antaa hyvin erilaisia arvioita esiintymien lukumäärästä . $H$ $G(n,m)$ $G(n,p)$ $H$

Jotkut tulokset

Hypoteesi on todistettu:

polut [4] ;
parillisen pituiset syklit [5] ;
puut [6] ;
hyperkuutiograafit [7] ;
täydelliset kaksiosaiset graafit [8] ;
kaksiosaisille kaavioille, joiden yhden osan koko on enintään 4 [9] ;
graafiille, joilla on vähintään yksi kärki vastakkaisen osuuden kaikkien kärkien vieressä [10] .

Monet tuloksista on yhdistetty yhdeksi todistuskäsitteeksi käyttämällä informaatioteorian entropian ominaisuuksia . [11] [12]

Myös graafien rakentamisesta on tiedossa tuloksia: mille tahansa kaksiosaiselle graafille on olemassa sellainen luku , että jos toistamme yhden osan kärjet (yhdessä lähtevien reunojen kanssa) kertaa, niin tuloksena oleva graafi täyttää Sidorenko-oletuksen [13 ] . $s$ $s$

Oletus on kuitenkin avoin monille kaavioille. Esimerkiksi for (täydellinen kaksiosainen graafi ilman Hamiltonin sykliä ). ${\displaystyle K_{5,5}\setminus C_{10))$

Muistiinpanot

↑ Katso maininta tästä Sidorenkossa, 1993 ennen hypoteesia 1
↑ Mulholland, Smith, 1959 .
↑ Sidorenko, 1993 .
↑ Mulholland, Smith, 1959 , katso lausunto sivun alussa. 674 klo $v=(1,\pisteet ,1)$
↑ Sidorenko, 1991 , esimerkki 1
↑ Sidorenko, 1991 , seuraus 1
↑ Hatami, 2010 .
↑ Sidorenko, 1991 , katso Lause 5 ja sen jälkeinen huomautus
↑ Sidorenko, 1991 , katso Lause 1 ja sen jälkeinen huomautus
↑ Conlon, Sudakov, Fox, 2010 , Lause 1.2
↑ Szegedy, 2015 .
↑ Entropia ja Sidorenkon arvelu – Szegedyn jälkeen Arkistoitu 26. syyskuuta 2020 Wayback Machinessa , arvosteltu Gowersin blogissa
↑ Conlon, Lee, 2018 , seuraus 1.2

Kirjallisuus

HP Mulholland, CAB Smith. Geneettisessä teoriassa nouseva epätasa-arvo // The American Mathematical Monthly. - 1959. - Voi. 66 , iss. 8 . — s. 673–683 .

A. Sidorenko. Kaksiosaisten graafien korrelaatioepäyhtälö // Grafit ja kombinatoriikka. - 1993. - Voi. 9 . — s. 201–204 .

A. F. Sidorenko. Kaksiosaisten graafien generoimien funktionaalisten funktioiden epäyhtälöt // Discrete Mathematics. - 1991. - Vol. 3 , numero. 3 . - S. 50-65 . (Venäjän kieli)

H. Hatami. Graafinormit ja Sidorenkon arvelu (englanniksi) // Israel Journal of Mathematics. - 2010. - Vol. 175 . — s. 125–150 . - arXiv : 0806.0047 .

D. Conlon, J. Fox, B. Sudakov. Likimääräinen versio Sidorenkon arvelusta // Geometrinen ja funktionaalinen analyysi. - 2010. - Vol. 20 . - s. 1354-1366 . - arXiv : 1004.4236 .

D. Conlon, J. Lee. Sidorenkon arvelu räjäyttämisestä . - 2018. - arXiv : 1809.01259 .

B. Szegedy. Tietoteoreettinen lähestymistapa Sidorenkon olettamukseen (englanniksi) . - 2015. - arXiv : 1406.6738v3 .