Hipotézis Sidorenko

Sidorenko gráfelméletből származó sejtése néhány (tetszőleges, de rögzített) gráf homomorfizmusainak számának becslésére vonatkozik egy tetszőleges gráfba . Megállapítja, hogy egy bipartit esetén ez a szám soha nem kisebb, mint egy véletlenszerű méretű gráfnál , amelynek várható élsűrűsége megegyezik a . $H$ $G$ $H$ $|G|$ $G$

A sejtést Alekszandr Sidorenko terjesztette elő 1986-ban [1] (egy konkrét esetet még korábban is bebizonyítottak [2] ). Különféle módszerekkel bizonyították egyes gráfosztályok esetében , de messze nem általános megoldás. $H$

Megfogalmazás

Jelölje gráfról gráfra a homomorfizmusok számát . Konkrétan jelölje az élek számát -ben . Jelöljük az ilyen homomorfizmusok "sűrűségét" a csúcsok csúcsokra való leképezései között . $h_{H}(G)$ $H$ $G$ $h_{K_{2}}(G)$ $G$ ${\displaystyle t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|))))$ $H$ $G$

Hipotézis Sidorenko

Ha egy kétrészes élgráf , akkor bármelyik gráfra igaz, hogy $H$ $m$ $G$ $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

Általában egy hipotézist úgy tekintenek, mint a különböző állítások halmazát, és pontosan az egyik vagy a másik esetében a megoldásáról beszélünk, és önkényes . $H$ $H$ $G$

Sidorenko eredetileg általánosabb formában fogalmazta meg az állítást, egy súlyozott kontinuumgráfokon (az úgynevezett grafonokon ). [3]

Értelmezés a véletlenen keresztül

A modellben szereplő véletlenszerű gráf esetén a gráf éleinek várható száma és a várható előfordulások száma pontosan megegyezik a Sidorenko-sejtésben szereplő egyenlőséggel. $G(n,p)$ ${\mathbb {E} }\ {t_{K_{2}}(G)}=np$ $H$ ${\displaystyle {\mathbb {E} }\ t_{H}(G)=n^{|V(H)|}p^{|E(H)|))$

Első pillantásra paradoxnak tűnhet az az ítélet, hogy egy bizonyos mennyiség (itt az előfordulások száma) "soha nem kisebb az átlagnál", mert ez azt jelentené, hogy a mennyiség minden értéke egyenlő az átlaggal. Ez így lenne, ha a véletlenszerűségen keresztüli értelmezés a véletlenszerű , rögzített élszámú Erdős-Rényi gráfok modelljét venné figyelembe, mivel a Sidorenko-sejtésben a becslés a gráf tényleges éleinek számától függ. A modellben pedig csak a várható élek száma lesz egyenlő vele. vagyis az átlagolás nem csak az adott méretű gráfokon történik, hanem olyan grafikonokon is, amelyekre a Sidorenko-hipotézis nagyon eltérő becsléseket ad az előfordulások számára . $H$ $G(n,m)$ $G(n,p)$ $H$

Néhány eredmény

A hipotézis bizonyítást nyert:

utak [4] ;
páros hosszúságú ciklusok [5] ;
fák [6] ;
hiperkocka gráfok [7] ;
teljes kétrészes gráfok [8] ;
olyan kétrészes gráfokhoz, amelyek egyikének mérete nem haladja meg a 4-et [9] ;
olyan gráfokhoz, amelyeknek legalább egy csúcsa szomszédos az ellentétes rész összes csúcsával [10] .

Sok eredményt egyetlen bizonyítási koncepcióba vontak össze az entrópia információelméletből származó tulajdonságainak felhasználásával . [11] [12]

A gráfok felépítésével kapcsolatban is ismertek eredmények: bármely kétrészes gráfnál van olyan szám , hogy ha valamelyik rész csúcsait (a kimenő élekkel együtt) többszörösen megduplikáljuk, akkor a kapott gráf kielégíti a Sidorenko-sejtést [13 ] . $p$ $p$

A sejtés azonban sok gráf esetében nyitott marad. Például for (egy teljes kétrészes gráf Hamilton-ciklus nélkül ). ${\displaystyle K_{5,5}\setminus C_{10))$

Jegyzetek

↑ Lásd ennek említését Sidorenko, 1993-ban az 1. hipotézis előtt
↑ Mulholland, Smith, 1959 .
↑ Sidorenko, 1993 .
↑ Mulholland, Smith, 1959 , lásd a kijelentést a p. elején. 674 at $v=(1,\pontok ,1)$
↑ Sidorenko, 1991 , 1. példa
↑ Sidorenko, 1991 , 1. következmény
↑ Hatami, 2010 .
↑ Sidorenko, 1991 , lásd az 5. tételt és az azt követő megjegyzést
↑ Sidorenko, 1991 , lásd az 1. tételt és az azt követő megjegyzést
↑ Conlon, Sudakov, Fox, 2010 , 1.2. tétel
↑ Szegedy, 2015 .
↑ Entrópia és Sidorenko sejtése - Szegedy után Archiválva 2020. szeptember 26-án a Wayback Machine -nél , áttekintve Gowers blogján
↑ Conlon, Lee, 2018 , következmény 1.2

Irodalom

HP Mulholland, CAB Smith. A genetikai elméletben felmerülő egyenlőtlenség // The American Mathematical Monthly. - 1959. - 1. évf. 66 , iss. 8 . — P. 673–683 .

A. Sidorenko. Korrelációs egyenlőtlenség kétrészes gráfokhoz // Graphs and Combinatorics. - 1993. - 1. évf. 9 . — P. 201–204 .

A. F. Sidorenko. Kétrészes gráfok által generált funkcionális egyenlőtlenségek // Discrete Mathematics. - 1991. - 3. évf. , szám. 3 . – S. 50–65 . (Orosz)

H. Hatami. Gráfnormák és Sidorenko sejtése (angol) // Israel Journal of Mathematics. - 2010. - 20. évf. 175 . — P. 125–150 . - arXiv : 0806.0047 .

D. Conlon, J. Fox, B. Sudakov. Sidorenko sejtésének hozzávetőleges változata // Geometriai és funkcionális elemzés. - 2010. - 20. évf. 20 . - P. 1354-1366 . - arXiv : 1004.4236 .

D. Conlon, J. Lee. Sidorenko sejtése a robbantásokról . - 2018. - arXiv : 1809.01259 .

B. Szegedy. Sidorenko sejtésének információelméleti megközelítése (angol) . - 2015. - arXiv : 1406.6738v3 .