Sidorenkovy dohady - Sidorenkos conjecture - Wikipedia

Sidorenkova domněnka je důležité dohad v oblasti teorie grafů, představuje Alexander Sidorenko v roce 1986. Zhruba řečeno, domněnka uvádí, že pro všechny bipartitní graf ${ displaystyle H}$ a graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy s průměrným stupněm ${ displaystyle pn}$, existují alespoň ${ displaystyle p ^ {| E (H) |} n ^ {| V (H) |}}$ označené kopie ${ displaystyle H}$ v ${ displaystyle G}$, až na malý chybový termín. Formálně poskytuje intuitivní nerovnost kolem homomorfismus grafů hustoty v grafony. Domnělou nerovnost lze interpretovat jako tvrzení, že hustota kopií ${ displaystyle H}$ v grafu je asymptoticky minimalizován náhodným grafem, jak by se dalo očekávat a ${ displaystyle p ^ {| E (H) |}}$ zlomek možných podgrafů být kopií ${ displaystyle H}$ pokud každá hrana existuje s pravděpodobností ${ displaystyle p}$.

Prohlášení

Nechat ${ displaystyle H}$ být graf. Pak ${ displaystyle H}$ se říká, že má Sidorenkův majetek pokud pro všechny grafony ${ displaystyle W}$nerovnost

${ displaystyle t (H, W) geq t (K_ {2}, W) ^ {| E (H) |}}$

je pravda, kde ${ displaystyle t (H, W)}$ je hustota homomorfismu z ${ displaystyle H}$ v ${ displaystyle W}$.

Sidorenkova domněnka (1986) uvádí, že každý bipartitní graf má Sidorenkovu vlastnost.^[1]

Li ${ displaystyle W}$ je graf ${ displaystyle G}$, To znamená, že pravděpodobnost jednotného náhodného mapování z ${ displaystyle V (H)}$ na ${ displaystyle V (G)}$ být homomorphism je přinejmenším produkt přes každou hranu v ${ displaystyle H}$ pravděpodobnosti mapování této hrany na hranu v ${ displaystyle G}$. To zhruba znamená, že náhodně vybraný graf s pevným počtem vrcholů a průměrným stupněm má minimální počet označených kopií ${ displaystyle H}$. To není překvapivá domněnka, protože pravá strana nerovnosti je pravděpodobnost, že mapování bude homomorfismus, pokud je každá okrajová mapa nezávislá. Měli bychom tedy očekávat, že obě strany budou alespoň ve stejném pořadí. Přirozené rozšíření grafonů by vyplývalo ze skutečnosti, že každý grafon je mezní bod nějaké posloupnosti grafů.

Požadavek, že ${ displaystyle H}$ je bipartitní mít Sidorenkův majetek je nutný - pokud ${ displaystyle W}$ je tedy bipartitní graf ${ displaystyle t (K_ {3}, W) = 0}$ od té doby ${ displaystyle W}$ je bez trojúhelníků. Ale ${ displaystyle t (K_ {2}, W)}$ je dvojnásobný počet hran ${ displaystyle W}$, takže Sidorenkovo ​​vlastnictví neplatí ${ displaystyle K_ {3}}$. Podobný argument ukazuje, že žádný graf s lichým cyklem nemá Sidorenkovu vlastnost. Protože graf je bipartitní právě tehdy, pokud nemá žádné liché cykly, znamená to, že jediné možné grafy, které mohou mít Sidorenkovu vlastnost, jsou bipartitní grafy.

Ekvivalentní formulace

Majetek Sidorenka je ekvivalentní následujícímu přeformulování:

Pro všechny grafy ${ displaystyle G}$, pokud ${ displaystyle G}$ má ${ displaystyle n}$ vrcholy a průměrný stupeň ${ displaystyle pn}$, pak ${ displaystyle t (H, G) geq p ^ {| E (H) |}}$.

To je ekvivalentní, protože počet homomorfismů z ${ displaystyle K_ {2}}$ na ${ displaystyle G}$ je dvojnásobný počet hran ${ displaystyle G}$a nerovnost je třeba zkontrolovat pouze tehdy, když ${ displaystyle W}$ je graf, jak již bylo zmíněno.

V této formulaci, protože počet neinjekčních homomorfismů z ${ displaystyle H}$ na ${ displaystyle G}$ je nanejvýš konstantní doba ${ displaystyle n ^ {| V (H) | -1}}$, Sidorenkova vlastnost by znamenala, že jich je alespoň ${ displaystyle (p ^ {| E (H) |} -o (1)) n ^ {| V (H) |}}$ označené kopie ${ displaystyle H}$ v ${ displaystyle G}$.

Příklady

Jak již bylo uvedeno výše, k prokázání Sidorenkovy vlastnosti stačí prokázat nerovnost pro všechny grafy ${ displaystyle G}$. V této části ${ displaystyle G}$ je graf na ${ displaystyle n}$ vrcholy s průměrným stupněm ${ displaystyle pn}$. Množství ${ displaystyle operatorname {hom} (H, G)}$ odkazuje na počet homomorfismů od ${ displaystyle H}$ na ${ displaystyle G}$. Toto množství je stejné jako ${ displaystyle n ^ {| V (H) |} t (H, G)}$.

Základní důkazy o majetku Sidorenka pro některé grafy vyplývají z Cauchy – Schwarzova nerovnost nebo Hölderova nerovnost. Ostatní lze provést pomocí teorie spektrálních grafů, zejména všímat si pozorování, že počet uzavřených cest délky ${ displaystyle ell}$ z vrcholu ${ displaystyle i}$ na vrchol ${ displaystyle j}$ v ${ displaystyle G}$ je složkou v ${ displaystyle i}$th řádek a ${ displaystyle j}$sloupec matice ${ displaystyle A ^ { ell}}$, kde ${ displaystyle A}$ je matice sousedství z ${ displaystyle G}$.

Cauchy – Schwarz: 4-cyklus C₄

Upevněním dvou vrcholů ${ displaystyle u}$ a ${ displaystyle v}$ z ${ displaystyle G}$, každá kopie ${ displaystyle C_ {4}}$ které mají ${ displaystyle u}$ a ${ displaystyle v}$ na opačných koncích lze identifikovat výběrem dvou (ne nutně odlišných) společných sousedů ${ displaystyle u}$ a ${ displaystyle v}$. Pronájem ${ displaystyle operatorname {codeg} (u, v)}$ označit kódový kód z ${ displaystyle u}$ a ${ displaystyle v}$ (tj. počet společných sousedů), z toho vyplývá

${ displaystyle operatorname {hom} (C_ {4}, G) = součet _ {u, v ve V (G)} operatorname {codeg} (u, v) ^ {2} geq { frac {1} {n ^ {2}}} left ( sum _ {u, v in V (G)} operatorname {codeg} (u, v) right) ^ {2}}$

Cauchy-Schwarzovou nerovností. Součet se nyní stal počtem všech párů vrcholů a jejich společných sousedů, který je stejný jako počet všech vrcholů a párů jejich sousedů. Tak

${ displaystyle operatorname {hom} (C_ {4}, G) geq { frac {1} {n ^ {2}}} left ( sum _ {x ve V (G)} deg ( x) ^ {2} right) ^ {2} geq { frac {1} {n ^ {2}}} left ({ frac {1} {n}} left ( sum _ {x ve V (G)} deg (x) vpravo) ^ {2} vpravo) ^ {2} = { frac {1} {n ^ {2}}} vlevo ({ frac {1} {n}} (n cdot pn) ^ {2} vpravo) ^ {2} = p ^ {4} n ^ {4}}$

Cauchy – Schwarz znovu. Tak

${ displaystyle t (C_ {4}, G) = { frac { operatorname {hom} (C_ {4}, G)} {n ^ {4}}} geq p ^ {4}}$

podle přání.

Teorie spektrálních grafů: 2k-cyklus C_2k

Ačkoli přístup Cauchy – Schwarz pro ${ displaystyle C_ {4}}$ je elegantní a základní, okamžitě se nezobecňuje na všechny sudé cykly. Lze však použít spektrální teorii grafů k prokázání, že všechny sudé cykly mají Sidorenkovu vlastnost. Všimněte si, že liché cykly nejsou v Sidorenkově domněnce zohledněny, protože nejsou bipartitní.

Z pozorování o uzavřených cestách z toho vyplývá ${ displaystyle operatorname {hom} (C_ {2k}, G)}$ je součet diagonálních záznamů v ${ displaystyle A ^ {2k}}$. To se rovná stopa z ${ displaystyle A ^ {2k}}$, což se zase rovná součtu ${ displaystyle 2k}$th pravomoci vlastní čísla z ${ displaystyle A}$. Li ${ displaystyle lambda _ {1} geq lambda _ {2} geq tečky geq lambda _ {n}}$ jsou vlastní čísla z ${ displaystyle A}$, pak věta o min-max to naznačuje

${ displaystyle lambda _ {1} geq { frac { mathbf {1} ^ { intercal} A mathbf {1}} { mathbf {1} ^ { intercal} mathbf {1}}} = { frac {1} {n}} součet _ {x ve V (G)} deg (x) = pn,}$

kde ${ displaystyle mathbf {1}}$ je vektor s ${ displaystyle n}$ komponenty, které všechny jsou ${ displaystyle 1}$. Ale pak

${ displaystyle operatorname {hom} (C_ {2k}, G) = součet _ {i = 1} ^ {n} lambda _ {i} ^ {2k} geq lambda _ {1} ^ {2k } geq p ^ {2k} n ^ {2k}}$

protože vlastní čísla a skutečná symetrická matice jsou skutečné. Tak

${ displaystyle t (C_ {2k}, G) = { frac { operatorname {hom} (C_ {2k}, G)} {n ^ {2k}}} geq p ^ {2k}}$

podle přání.

Entropie: Cesty o délce 3

J.L. Xiang Li a Balázs Szegedy (2011) představili myšlenku používání entropie dokázat některé případy Sidorenkovy domněnky. Szegedy (2015) později tyto myšlenky dále aplikoval, aby dokázal, že Sidorenkova vlastnost má ještě širší třída bipartitních grafů.^[2] Zatímco Szegedyho důkaz byl abstraktní a technický, Tim Gowers a Jason Long snížil argument na jednodušší pro konkrétní případy, jako jsou cesty délky ${ displaystyle 3}$.^[3] V podstatě si důkaz vybere pěkný rozdělení pravděpodobnosti výběru vrcholů v cestě a platí Jensenova nerovnost (tj. konvexita) k odvození nerovnosti.

Částečné výsledky

Zde je seznam některých bipartitních grafů ${ displaystyle H}$ u kterých bylo prokázáno, že mají Sidorenkův majetek. Nechat ${ displaystyle H}$ mít biparticii ${ displaystyle A sqcup B}$.

• Cesty mají Sidorenkův majetek, jak ukazují Mulholland a Smith v roce 1959 (předtím, než Sidorenko formuloval domněnku).^[4]
• Stromy mít Sidorenkův majetek, zobecňující cesty. To ukázal Sidorenko v dokumentu z roku 1991.^[5]
• Cykly rovnoměrné délky mít Sidorenkův majetek, jak bylo uvedeno výše. Sidorenko to také prokázal ve své práci z roku 1991.
• Kompletní bipartitní grafy mít Sidorenkův majetek. To bylo také ukázáno v Sidorenkově dokumentu z roku 1991.
• Bipartitní grafy s ${ displaystyle min {| A |, | B | } leq 4}$ mít Sidorenkův majetek. To bylo také ukázáno v Sidorenkově dokumentu z roku 1991.
• Hypercube grafy (zobecnění ${ displaystyle Q_ {3}}$) mají Sidorenkův majetek, jak prokázal Hatami v roce 2008.^[6]
  • Obecněji řečeno, normovací grafy (zavedené Hatami) mají Sidorenkovu vlastnost.
• Pokud je v ${ displaystyle A}$ to je soused s každým vrcholem v ${ displaystyle B}$ (nebo naopak) ${ displaystyle H}$ má majetek Sidorenka, jak to prokázali Conlon, Fox a Sudakov v roce 2010.^[7] Tento důkaz používal závislá náhodná volba metoda.
• Pro všechny bipartitní grafy ${ displaystyle H}$, existuje nějaké kladné celé číslo ${ displaystyle p}$ takové, že ${ displaystyle p}$-nafouknout z ${ displaystyle B}$ má Sidorenkův majetek. Tady je ${ displaystyle p}$- vyhodit do povětří ${ displaystyle H}$ je vytvořen nahrazením každého vrcholu v ${ displaystyle B}$ s ${ displaystyle p}$ její kopie, každá spojená se svými původními sousedy v ${ displaystyle A}$. To ukázali Conlon a Lee v roce 2018.^[8]
• Byly vyzkoušeny některé rekurzivní přístupy, které berou kolekci grafů, které mají Sidorenkovu vlastnost, k vytvoření nového grafu, který má Sidorenkovu vlastnost. Hlavní pokrok tímto způsobem dosáhl Sidorenko ve svém příspěvku z roku 1991, Li a Szegedy v roce 2011^[9]a Kim, Lee a Lee v roce 2013^[10].
  • Článek Li a Szegedyho také používal metody entropie k prokázání vlastnosti pro třídu grafů zvaných „reflexní stromy“.
  • Článek Kim, Lee a Lee rozšířil tuto myšlenku na třídu grafů se stromovou strukturou nazvanou „stromově uspořádatelné grafy“.

Existují však grafy, pro které je Sidorenkova domněnka stále otevřená. Příkladem je graf „Möbiusův pás“ ${ displaystyle K_ {5,5} setminus C_ {10}}$, vytvořený odstraněním a ${ displaystyle 10}$-cyklus z celého bipartitního grafu s částmi velikosti ${ displaystyle 5}$.

László Lovász se ukázal jako lokální verze Sidorenkovy domněnky, tj. pro grafy, které jsou „blízké“ náhodným grafům ve smyslu řezané normy.^[11]

Vynucená domněnka

Posloupnost grafů ${ displaystyle {G_ {n} } _ {n = 1} ^ { infty}}$ je nazýván kvazi náhodný s hustotou ${ displaystyle p}$ pro určitou hustotu ${ displaystyle 0$

pokud pro každý graf ${ displaystyle H}$,

${ displaystyle t (H, G_ {n}) = (1 + o (1)) p ^ {| E (H) |}.}$

Posloupnost grafů by tedy měla vlastnosti Erdős – Rényi náhodný graf ${ displaystyle G (n, p)}$.

Pokud je hustota hran ${ displaystyle t (K_ {2}, G_ {n})}$ je stanovena na ${ displaystyle (1 + o (1)) p}$, pak podmínka znamená, že posloupnost grafů se blíží případu rovnosti ve vlastnosti Sidorenko pro každý graf ${ displaystyle H}$.

Z článku Chunga, Grahama a Wilsona z roku 1989 o kvazi náhodných grafech to stačí pro ${ displaystyle C_ {4}}$ spočítat tak, aby odpovídalo očekávání náhodného grafu (tj. podmínka platí pro ${ displaystyle H = C_ {4}}$).^[12] Příspěvek se také ptá, které grafy ${ displaystyle H}$ mít tuto vlastnost navíc ${ displaystyle C_ {4}}$. Takové grafy se nazývají nutit grafy protože jejich počet řídí kvazi náhodnost posloupnosti grafů.

Donucovací domněnka uvádí následující:

Graf ${ displaystyle H}$ nutí právě tehdy, je-li bipartitní a ne strom.

Je zřejmé, že pokud ${ displaystyle H}$ nutí, pak je to bipartita a ne strom. Některé příklady vynucení grafů jsou dokonce cykly (ukázané Chungem, Grahamem a Wilsonem). Skokan a Thoma ukázali, že všechny úplné bipartitní grafy, které nejsou stromy, nutí.^[13]

Sidorenkova domněnka vyplývá z domněnky. Donucovací domněnka by dále ukázala, že grafy, které jsou blízké rovnosti v Sidorenkově majetku, musí splňovat podmínky kvazi náhodnosti.^[14]

Reference