Hustota homomorfismu - Homomorphism density - Wikipedia

V matematický pole teorie extrémních grafů, hustota homomorfismu s ohledem na graf ${ displaystyle H}$ je parametr ${ displaystyle t (H, -)}$ který je přidružen ke každému grafu ${ displaystyle G}$ následujícím způsobem:

${ displaystyle t (H, G): = { frac {| hom (H, G) |} {| V (G) | ^ {| V (H) |}}}}$ .

Výše, ${ displaystyle hom (H, G)}$ je sada homomorfismy grafů nebo mapy zachování sousedství z ${ displaystyle H}$ na ${ displaystyle G}$ . Hustotu lze také interpretovat jako pravděpodobnost, že mapa z vrcholů ${ displaystyle H}$ k vrcholům ${ displaystyle G}$ náhodně zvolený rovnoměrně je homomorfismus grafu.^[1] Existuje souvislost mezi hustotami homomorfismu a hustotami podgrafů, která je rozpracována níže. ^[2]

Příklady

Okrajová hustota grafu ${ displaystyle G}$ je dána ${ displaystyle t (K_ {2}, G)}$ .
V grafu s ${ displaystyle n}$ vrcholy, kde je průměrný stupeň větší nebo roven ${ displaystyle pn}$ , hustota hran je minimálně ${ displaystyle p}$ .
Hustota trojúhelníků v grafu ${ displaystyle G}$ je dána ${ displaystyle t (K_ {3}, G)}$ .
Hustota 4 cyklů v grafu ${ displaystyle G}$ je dána ${ displaystyle t (C_ {4}, G)}$ .

Hustoty podgrafu

Definujeme (označenou) hustotu podgrafu ${ displaystyle H}$ v ${ displaystyle G}$ být

${ displaystyle d (H, G): = { frac { # { text {označené kopie}} H { text {in}} G} {| V (G) | ^ {| V (H) |}}}}$ .

Všimněte si, že by mohlo být trochu pochybné nazývat to hustotou, protože nejsme zcela rozděleni celkovým počtem označených podgrafů na ${ displaystyle | V (H) |}$ vrcholy ${ displaystyle G}$ , ale naše definice je asymptoticky ekvivalentní a její analýza je pro naše účely jednodušší. Všimněte si, že všechny označené kopie ${ displaystyle H}$ v ${ displaystyle G}$ odpovídá homomorfismu z ${ displaystyle H}$ do ${ displaystyle G}$ . Ne každý homomorfismus však odpovídá označené kopii - existují zde zvrhlé případy, kdy více vrcholů ${ displaystyle H}$ jsou odesílány na stejný vrchol ${ displaystyle G}$ . To znamená, že počet takových degenerovaných homomorfismů je pouze ${ displaystyle O (n ^ {| V (H) | -1})}$ , takže máme ${ displaystyle t (H, G) = d (H, G) + O (1 / n)}$ . Například vidíme, že pro grafy s konstantní hustotou homomorfismu jsou označená hustota podgrafu a hustota homomorfismu asymptoticky ekvivalentní. Pro ${ displaystyle H}$ být úplným grafem ${ displaystyle K_ {m}}$ , hustota homomorfismu a hustota podgrafu jsou ve skutečnosti stejné (pro ${ displaystyle G}$ bez vlastních smyček), jako okraje ${ displaystyle K_ {m}}$ vynutit rozlišování všech obrázků pod homomorfismem grafu.

Zobecnění na grafony

Pojem hustoty homomorfismu lze zobecnit na případ, kdy místo grafu ${ displaystyle G}$ , máme grafon ${ displaystyle W}$ ,

${ displaystyle t (H, W) = int _ {[0,1] ^ {| V (H) |}} prod _ {ij v E (H)} W (x_ {i}, x_ { j}) prod _ {i ve V (H)} dx_ {i}}$

Všimněte si, že integrand je produkt, který běží přes okraje v podgrafu ${ displaystyle H}$ , zatímco diferenciál je produkt běžící přes vrcholy v ${ displaystyle H}$ . Intuitivně každý vrchol ${ displaystyle i}$ v ${ displaystyle H}$ je reprezentována proměnnou ${ displaystyle x_ {i}}$ .

Například hustota trojúhelníku v grafu je dána vztahem

${ displaystyle t (K_ {3}, W) = int limity _ {[0,1] ^ {3}} W (x, y) W (y, z) W (z, x) dxdydz}$ .

Tato definice hustoty homomorfismu je skutečně zobecněním, protože pro každý graf ${ displaystyle G}$ a související krokový graf ${ displaystyle W_ {G}}$ , ${ displaystyle t (H, G) = t (H, W_ {G})}$ .^[1]

Tato představa je užitečná pro pochopení asymptotického chování hustot homomorfismu grafů, které splňují určité vlastnosti, protože grafon je limitem posloupnosti grafů.

Důležité výsledky: nerovnosti

Mnoho výsledků v teorie extrémních grafů lze popsat nerovnostmi zahrnujícími hustoty homomorfismu spojené s grafem. Například, Mantelova věta uvádí v kontextu grafony, to když ${ displaystyle t (K_ {3}, W) = 0}$ , pak ${ displaystyle t (K_ {2}, W) leq 1/2}$ . Dalším příkladem je Turánova věta, který uvádí, že pokud ${ displaystyle t (K_ {r}, W) = 0}$ , pak ${ displaystyle t (K_ {2}, W) leq (r-2 / r-1)}$ .

Podle Hamed Hatami a Sergei Norine lze převést jakoukoli algebraickou nerovnost mezi hustotami homomorfismu na lineární nerovnost.^[2] V některých situacích lze rozhodování, zda je taková nerovnost pravdivá, či nikoli, zjednodušit, jako je tomu v následující větě.

Věta (Bollobás ). Nechat ${ displaystyle a_ {1}, cdots, a_ {n}}$ být skutečné konstanty. Potom nerovnost
${ displaystyle sum _ {i = 1} ^ {n} a_ {i} t (K_ {i}, G) geq 0}$
platí pro každý graf ${ displaystyle G}$ právě když platí pro každý úplný graf ${ displaystyle K_ {m}}$ .^[3]

Dostaneme však mnohem těžší problém, ve skutečnosti nerozhodnutelný jeden, když máme homomorfismus nerovnosti na obecnější sadu grafů ${ displaystyle H_ {i}}$ :

Věta (Hatami, Norine). Nechat ${ displaystyle a_ {1}, cdots, a_ {n}}$ být skutečné konstanty a ${ displaystyle {H_ {i} } _ {i = 1} ^ {n}}$ grafy. Potom je nerozhodnutelným problémem určit, zda je nerovnost hustoty homomorfismu
${ displaystyle sum _ {i = 1} ^ {n} a_ {r} t (H_ {i}, G) geq 0}$
platí pro každý graf ${ displaystyle G}$ . ^[2]

Nedávné pozorování^[4] dokazuje, že jakákoli nerovnoměrnost hustoty lineárního homomorfismu je důsledkem pozitivní polodefinitivity určité nekonečné matice nebo pozitivity kvantový graf; jinými slovy, jakákoli taková nerovnost by vyplývala z aplikací Cauchy Schwarzovy nerovnosti. ^[2]

Popis ${ displaystyle D_ {2,3}}$

Další nedávný vývoj spočívá v dokončení porozumění problému nerovnoměrnosti homomorfismu, popis ${ displaystyle D_ {2,3}}$ , což je oblast proveditelné okrajové hustoty, trojúhelníkové páry hustoty v grafu:

${ displaystyle D_ {2,3} = {(t (K_ {2}, W), t (K_ {3}, W)) ;: ; W { text {je graf}} } subseteq [0,1] ^ {2}}$

Pozorování 1. Tato oblast je uzavřená, protože limit posloupnosti grafů je graf. ^[1]

Pozorování 2. Pro každého ${ displaystyle 0 leq r leq 1}$ , sada ${ displaystyle D_ {2,3} čepice [0,1] krát {r }}$ je svislý úsečka bez mezer.

Důkaz: Zvažte dva grafony ${ displaystyle W_ {0}}$ , ${ displaystyle W_ {1}}$ se stejnou hustotou hran; potom rodina grafonů následující formy, as ${ displaystyle t}$ se pohybuje od 0 do 1

${ displaystyle W_ {t} = (1-t) W_ {0} + tW_ {1}}$

dosahuje všech možných hustot trojúhelníků mezi hodnotami ${ displaystyle t (K_ {3}, W_ {0})}$ a ${ displaystyle t (K_ {3}, W_ {1})}$ , kontinuitou této mapy.

Pozorování 3. Pro každého, grafon ${ displaystyle W: [0,1] ^ {2} rightarrow [0,1]}$ , máme horní hranici ${ displaystyle t (K_ {3}, W) leq t (K_ {2}, W) ^ {3/2}}$

Důkaz: Tuto nerovnost stačí prokázat pro jakýkoli graf ${ displaystyle G}$ . Říci ${ displaystyle G}$ je graf na ${ displaystyle n}$ vrcholy a ${ displaystyle { lambda _ {i} } _ {i = 1} ^ {n}}$ jsou vlastní čísla jeho matice sousedství ${ displaystyle A_ {G}}$ . Podle teorie spektrálních grafů, víme

${ displaystyle hom (K_ {2}, G) = t (K_ {2}, G) | V (G) | ^ {2} = součet _ {i = 1} ^ {n} lambda _ {i } ^ {2}}$ ,

${ displaystyle hom (K_ {3}, G) = t (K_ {3}, G) | V (G) | ^ {3} = součet _ {i = 1} ^ {n} lambda _ {i } ^ {3}}$ .

Závěr pak vychází z následující nerovnosti:

${ displaystyle hom (K_ {3}, G) = součet _ {i = 1} ^ {n} lambda _ {i} ^ {3} leq left ( sum _ {i = 1} ^ { n} lambda _ {i} ^ {2} right) ^ {3/2} = hom (K_ {2}, G) ^ {3/2}}$

Pozorování 3. Extrémní body konvexního trupu

${ displaystyle D_ {2,3, cdots, r} = {(t (K_ {2}, W), t (K_ {3}, W), cdots, t (K_ {r}, W) ) ;: ; W { text {je graf}} } subseteq [0,1] ^ {r-1}}$

jsou dány ${ displaystyle W = K_ {m}}$ pro každého ${ displaystyle m}$ kladné celé číslo. Zejména extrémy ${ displaystyle D_ {2,3}}$ jsou dány následující samostatnou sadou bodů v křivce ${ displaystyle y = x (2x-1)}$ :

${ displaystyle p_ {m} = left ({ frac {m-1} {m}}, { frac {(m-1) (m-2)} {m ^ {2}}} right) }$

Pozorování 3. Toto je věta kvůli Razborov,^[5] což uvádí, že pro danou hustotu hran ${ displaystyle r = t (K_ {2}, W)}$ , pokud

${ displaystyle { frac {k-1} {k}}$ ,

pro nějaké kladné celé číslo ${ displaystyle k}$ , pak je minimální proveditelná hustota trojúhelníku dosažena jedinečným grafem s krokovou funkcí ${ displaystyle W}$ s váhami uzlů ${ displaystyle a_ {1}, cdots a_ {k}}$ se součtem rovným 1 a takovým ${ displaystyle a_ {1} = cdots = a_ {k-1} geq a_ {k}}$ . Přesněji řečeno, možné minimum ${ displaystyle t (K_ {3}, W)}$ je

${ displaystyle { frac {(k-1) levý (k-2 { sqrt {k (kr (k + 1))}} pravý) levý (k + { sqrt {k (kr (k + 1))}} vpravo) ^ {2}} {k ^ {2} (k + 1) ^ {2}}}}$ .

Viz také

Sidorenkova domněnka

Reference

^ ^A ^b ^C Borgs, C., Chayes, J.T., Lovász, L., Sós, V.T., Vestergombi, K. (2008). "Konvergentní sekvence hustých grafů. I. Frekvence podgrafu, metrické vlastnosti a testování". Pokroky v matematice. 219, č. 6: 1805, 1811 - prostřednictvím vědeckého projektu ELSEVIER.CS1 maint: více jmen: seznam autorů (odkaz)
^ ^A ^b ^C ^d Hatami, H., Norine, S. (2011). „Nerozhodnutelnost lineárních nerovností v hustotách homomorfismu grafů“ (PDF). Journal of the American Mathematical Society. 24, č. 2: 553 - přes MathSciNet.CS1 maint: více jmen: seznam autorů (odkaz)
^ Bollobás, Bela (1986). Kombinatorika: Setové systémy, hypergrafy, rodiny vektorů a kombinatorická pravděpodobnost. Cambridge: Cambridge University Press. str.79-84. ISBN 0-521-33059-9.
^ Freedman, M., Lovász, L., Schrijver, A. (2007). "Odrazová pozitivita, konektivita hodnosti a homomorfismus grafů" (PDF). Journal of the American Mathematical Society. 20, č. 1: 1.CS1 maint: více jmen: seznam autorů (odkaz)
^ Razborov, Alexander (2008). „O minimální hustotě trojúhelníků v grafech“ (PDF). Kombinatorika, pravděpodobnost a výpočetní technika. 17, č. 4: 1 - prostřednictvím MathSciNet (AMS).

[:0-1] A ^b ^C Borgs, C., Chayes, J.T., Lovász, L., Sós, V.T., Vestergombi, K. (2008). "Konvergentní sekvence hustých grafů. I. Frekvence podgrafu, metrické vlastnosti a testování". Pokroky v matematice. 219, č. 6: 1805, 1811 - prostřednictvím vědeckého projektu ELSEVIER.CS1 maint: více jmen: seznam autorů (odkaz)

[:1-2] A ^b ^C ^d Hatami, H., Norine, S. (2011). „Nerozhodnutelnost lineárních nerovností v hustotách homomorfismu grafů“ (PDF). Journal of the American Mathematical Society. 24, č. 2: 553 - přes MathSciNet.CS1 maint: více jmen: seznam autorů (odkaz)

[3] Bollobás, Bela (1986). Kombinatorika: Setové systémy, hypergrafy, rodiny vektorů a kombinatorická pravděpodobnost. Cambridge: Cambridge University Press. str.79-84. ISBN 0-521-33059-9.

[4] Freedman, M., Lovász, L., Schrijver, A. (2007). "Odrazová pozitivita, konektivita hodnosti a homomorfismus grafů" (PDF). Journal of the American Mathematical Society. 20, č. 1: 1.CS1 maint: více jmen: seznam autorů (odkaz)

[5] Razborov, Alexander (2008). „O minimální hustotě trojúhelníků v grafech“ (PDF). Kombinatorika, pravděpodobnost a výpočetní technika. 17, č. 4: 1 - prostřednictvím MathSciNet (AMS).

[1]

[2]

[3]

[4]

[5]