Ipoteza Sidorenko

Conjectura lui Sidorenko din teoria grafurilor se referă la o estimare a numărului de homomorfisme ale unor graf (arbitrar, dar fix) într-un graf arbitrar . Ea afirmă că pentru un bipartit acest număr nu este niciodată mai mic decât pentru un grafic de mărime aleatorie cu aceeași densitate de margine așteptată ca . $H$ $G$ $H$ $|G|$ $G$

Conjectura a fost înaintată de Alexander Sidorenko în 1986 [1] (un caz particular a fost dovedit chiar mai devreme [2] ). A fost dovedit prin diferite metode pentru unele clase de grafice , dar este departe de a fi o soluție generală. $H$

Formulare

Să notăm numărul de homomorfisme de la un grafic la altul . În special, să notăm numărul de muchii în . Să notăm, de asemenea, „densitatea” unor astfel de homomorfisme printre toate mapările de vârfuri la vârfuri . $h_{H}(G)$ $H$ $G$ $h_{K_{2}}(G)$ $G$ $t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|)))$ $H$ $G$

Ipoteza Sidorenko

Dacă este un graf cu muchii bipartite , atunci pentru orice graf este adevărat că $H$ $m$ $G$ $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

De obicei, o ipoteză este considerată ca un set de afirmații pentru diferite și se vorbește despre soluția ei tocmai pentru una sau alta și arbitrară . $H$ $H$ $G$

Sidorenko a formulat inițial enunțul într-o formă mai generală, pentru o măsură pe grafice continuum ponderate (așa-numitele grafoni ). [3]

Interpretarea prin întâmplare

Pentru un grafic aleatoriu din model, numărul așteptat de muchii și numărul așteptat de apariții ale graficului corespund exact egalității din conjectura Sidorenko. $G(n,p)$ ${\mathbb {E} }\ {t_{K_{2}}(G)}=np$ $H$ ${\mathbb {E} }\ t_{H}(G)=n^{|V(H)|}p^{|E(H)|}$

La prima vedere, judecata că o anumită cantitate (aici, numărul de apariții ) este „niciodată mai mică decât media” poate părea paradoxală, deoarece aceasta ar însemna că toate valorile cantității sunt egale cu media. Acest lucru ar fi așa dacă interpretarea prin aleatorie ar considera modelul graficelor aleatoare Erdős-Rényi cu un număr fix de muchii, deoarece estimarea din conjectura Sidorenko depinde de numărul real de muchii din grafic. Și în model, doar numărul așteptat de margini va fi egal cu acesta. adică, media se face nu numai pe grafice de aceeași dimensiune cu cea dată, ci și pe grafice pentru care ipoteza Sidorenko oferă estimări foarte diferite pentru numărul de apariții . $H$ $G(n,m)$ $G(n,p)$ $H$

Unele rezultate

Ipoteza a fost dovedită pentru:

poteci [4] ;
cicluri de lungime uniformă [5] ;
copaci [6] ;
grafice hipercube [7] ;
grafuri bipartite complete [8] ;
pentru grafuri bipartite cu dimensiunea uneia dintre părți care nu depășește 4 [9] ;
pentru graficele care au cel puțin un vârf adiacent tuturor vârfurilor cotei opuse [10] .

Multe dintre rezultate au fost combinate într-un singur concept de demonstrare prin utilizarea proprietăților entropiei din teoria informației . [11] [12]

Există, de asemenea, rezultate cunoscute privind construcția graficelor: pentru orice graf bipartit există un număr astfel încât dacă duplicăm vârfurile uneia dintre părți (împreună cu muchiile de ieșire) ori, atunci graficul rezultat va satisface conjectura Sidorenko [13]. ] . $p$ $p$

Cu toate acestea, conjectura rămâne deschisă pentru multe grafice. De exemplu, pentru (un grafic bipartit complet fără un ciclu hamiltonian ). $K_{5,5}\setminus C_{10)$

Note

↑ Vezi menționarea acestui lucru în Sidorenko, 1993 înainte de ipoteza 1
↑ Mulholland, Smith, 1959 .
↑ Sidorenko, 1993 .
↑ Mulholland, Smith, 1959 , vezi declarația de la începutul p. 674 la $v=(1,\dots ,1)$
↑ Sidorenko, 1991 , exemplul 1
↑ Sidorenko, 1991 , consecința 1
↑ Hatami, 2010 .
↑ Sidorenko, 1991 , vezi Teorema 5 și observația de după ea
↑ Sidorenko, 1991 , vezi Teorema 1 și observația de după ea
↑ Conlon, Sudakov, Fox, 2010 , Teorema 1.2
↑ Szegedy, 2015 .
↑ Entropia și conjectura lui Sidorenko - după Szegedy Arhivat 26 septembrie 2020 la Wayback Machine , revizuit pe blogul lui Gowers
↑ Conlon, Lee, 2018 , corolarul 1.2

Literatură

HP Mulholland, CAB Smith. O inegalitate care apare în teoria genetică // The American Mathematical Monthly. - 1959. - Vol. 66 , iss. 8 . — P. 673–683 .

A. Sidorenko. O inegalitate de corelație pentru graficele bipartite // Grafice și combinatorie. - 1993. - Vol. 9 . — P. 201–204 .

A. F. Sidorenko. Inegalități pentru funcționale generate de grafice bipartite // Matematică discretă. - 1991. - Vol. 3 , numărul. 3 . — S. 50–65 . (Rusă)

H. Hatami. Norme grafice și conjectura lui Sidorenko (engleză) // Israel Journal of Mathematics. - 2010. - Vol. 175 . — P. 125–150 . - arXiv : 0806.0047 .

D. Conlon, J. Fox, B. Sudakov. O versiune aproximativă a conjecturei lui Sidorenko // Analiză geometrică și funcțională. - 2010. - Vol. 20 . - P. 1354-1366 . - arXiv : 1004.4236 .

D. Conlon, J. Lee. Conjectura lui Sidorenko pentru explozii . - 2018. - arXiv : 1809.01259 .

B. Szegedy. O abordare teoretică a informației a conjecturii lui Sidorenko (engleză) . - 2015. - arXiv : 1406.6738v3 .