Hypotese Sidorenko

Sidorenkos formodning fra grafteorien vedrører et estimat for antallet af homomorfier af nogle (vilkårlige, men faste) grafer til en vilkårlig graf . Hun anfører, at for en todelt er dette tal aldrig mindre end for en graf med tilfældig størrelse med samme forventede kanttæthed som . $H$ $G$ $H$ $|G|$ $G$

Formodningen blev fremsat af Alexander Sidorenko i 1986 [1] (en bestemt sag blev bevist endnu tidligere [2] ). Det er blevet bevist med forskellige metoder for nogle klasser af grafer , men er langt fra en generel løsning. $H$

Ordlyd

Lad betegne antallet af homomorfier fra graf til graf . Lad især betegne antallet af kanter i . Lad også betegne "densiteten" af sådanne homomorfismer blandt alle kortlægninger af toppunkter til toppunkter . $h_{H}(G)$ $H$ $G$ $h_{K_{2}}(G)$ $G$ ${\displaystyle t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|))))$ $H$ $G$

Hypotese Sidorenko

Hvis er en todelt kantgraf , så er det sandt for enhver graf $H$ $m$ $G$ $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

Normalt betragtes en hypotese som et sæt af udsagn for forskellige, og man taler om dens løsning netop for en eller anden og vilkårlig . $H$ $H$ $G$

Sidorenko formulerede oprindeligt udsagnet i en mere generel form, for et mål på vægtede kontinuumsgrafer (de såkaldte grafoner ). [3]

Fortolkning gennem tilfældigheder

For en tilfældig graf i modellen svarer det forventede antal kanter og det forventede antal forekomster af grafen lig med nøjagtigt ligheden i Sidorenko-formodningen. $G(n,p)$ ${\mathbb {E} }\ {t_{K_{2}}(G)}=np$ $H$ ${\displaystyle {\mathbb {E} }\ t_{H}(G)=n^{|V(H)|}p^{|E(H)|))$

Ved første øjekast kan dommen om, at en bestemt mængde (her antallet af forekomster ) er "aldrig mindre end gennemsnittet" virke paradoksalt, fordi det ville betyde, at alle værdier af mængden er lig med gennemsnittet. Dette ville være tilfældet, hvis fortolkningen gennem tilfældighed betragtede modellen af tilfældige Erdős-Rényi-grafer med et fast antal kanter, fordi estimatet i Sidorenko-formodningen afhænger af det faktiske antal kanter i grafen. Og i modellen vil kun det forventede antal kanter være lig med det. det vil sige, at gennemsnittet ikke kun foretages over grafer af samme størrelse som den givne, og også over grafer, for hvilke Sidorenko-hypotesen giver meget forskellige estimater for antallet af forekomster . $H$ $G(n,m)$ $G(n,p)$ $H$

Nogle resultater

Hypotesen er blevet bevist for:

stier [4] ;
cyklusser af lige længde [5] ;
træer [6] ;
hyperkubegrafer [7] ;
komplette todelte grafer [8] ;
for todelte grafer, hvor størrelsen af en af delene ikke overstiger 4 [9] ;
for grafer, der har mindst ét toppunkt, der støder op til alle hjørner af den modsatte andel [10] .

Mange af resultaterne er blevet kombineret til et enkelt beviskoncept ved at bruge entropiens egenskaber fra informationsteori . [11] [12]

Der er også kendte resultater om konstruktion af grafer: for enhver todelt graf er der et tal , således at hvis vi duplikerer hjørnerne af en af delene (sammen med udgående kanter) gange, så vil den resulterende graf opfylde Sidorenko-formodningen [13 ] . $s$ $s$

Formodningen forbliver dog åben for mange grafer. For eksempel for (en komplet todelt graf uden en Hamiltonsk cyklus ). ${\displaystyle K_{5,5}\setminus C_{10))$

Noter

↑ Se omtale af dette i Sidorenko, 1993 før hypotese 1
↑ Mulholland, Smith, 1959 .
↑ Sidorenko, 1993 .
↑ Mulholland, Smith, 1959 , se udtalelse i begyndelsen af s. 674 kl $v=(1,\dots ,1)$
↑ Sidorenko, 1991 , eksempel 1
↑ Sidorenko, 1991 , konsekvens 1
↑ Hatami, 2010 .
↑ Sidorenko, 1991 , se sætning 5 og bemærkningen efter den
↑ Sidorenko, 1991 , se sætning 1 og bemærkningen efter den
↑ Conlon, Sudakov, Fox, 2010 , sætning 1.2
↑ Szegedy, 2015 .
↑ Entropi og Sidorenkos formodning - efter Szegedy arkiveret 26. september 2020 på Wayback Machine , gennemgået på Gowers' blog
↑ Conlon, Lee, 2018 , følge 1.2

Litteratur

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

A. Sidorenko. En korrelationsulighed for todelte grafer // Grafer og kombinatorik. - 1993. - Bd. 9 . — S. 201–204 .

A. F. Sidorenko. Uligheder for funktionaler genereret af todelte grafer // Diskret matematik. - 1991. - Vol. 3 , udgave. 3 . — S. 50–65 . (Russisk)

H. Hatami. Grafnormer og Sidorenkos formodning (engelsk) // Israel Journal of Mathematics. - 2010. - Bd. 175 . — S. 125–150 . - arXiv : 0806.0047 .

D. Conlon, J. Fox, B. Sudakov. En omtrentlig version af Sidorenkos formodning // Geometrisk og funktionel analyse. - 2010. - Bd. 20 . - S. 1354-1366 . - arXiv : 1004.4236 .

D. Conlon, J. Lee. Sidorenkos formodning om blow- ups . - 2018. - arXiv : 1809.01259 .

B. Szegedy. En informationsteoretisk tilgang til Sidorenkos formodning (engelsk) . - 2015. - arXiv : 1406.6738v3 .