Lévyho rodina grafů - Lévy family of graphs

v teorie grafů, obor matematiky, a Lévyho rodina grafů je rodina grafy G_n, n = 1, 2, 3, ..., které mají určitý typ „kompaktnosti“ nebo „zamotanosti“. Mnoho přirozeně se vyskytujících rodin grafů jsou rodiny Lévyových. Mnoho matematiků si tuto skutečnost všimlo a vyjádřilo překvapení, že se nezdá, že by měla připravené vysvětlení.

Formálně rodina grafů G_n, n = 1, 2, 3, ..., je rodina Lévyových, pokud vůbec ${displaystyle varepsilon> 0}$

${displaystyle lim _ {nlongrightarrow infty} alfa vlevo (G_ {n}, varepsilon ight) = 0}$

kde

${displaystyle alpha (G, varepsilon) = max left {1- {frac {left | A _ {(varepsilon D)} ight |} {| G |}},:, Asubseteq G, | A |> | G | / 2ight }.}$

Tady D je průměr grafu z G, a A_(n) je n-sousedství grafu z A. Všimněte si, že se maximalizace pohybuje přes podmnožiny A z G, s výhradou A je přes polovinu velikosti G

Řečeno slovy, znamená to, že lze mít podmnožinu velikosti alespoň poloviny Ga vyhodit do povětří jen ${displaystyle epsilon}$ průměru grafu a skončí s téměř celou sadou.

Dlouhé "vláknité" (tj. Ne "kompaktní") rodiny grafů, jako například graf cyklu řádu n zjevně takovou vlastnost nemají: dalo by se uvažovat o podmnožině zahrnující n / 2 sousedství bodu (řekněme půlnoc až šest hodin). Graf má průměr grafu D asi n / 2. Takže ${displaystyle epsilon D}$-sousedství podmnožiny je pouze o velikosti asi n / 2. Rodina Levyů by měla tuto čtvrť pokrývající téměř celou scénu. Mělo by být jasné, že rodina Levyových musí mít velmi zvláštní typ kompaktní struktury.

• Hypercube grafy řádu n je známo, že jsou Lévyovci.
• Li S_n je graf s body, které jsou prvky permutační skupina z n prvky s hranami spojujícími body, které se liší o a transpozice, pak série S_i, i = 1,2, ..., je Lévyova rodina.

Reference

• Bollobás (editor). Pravděpodobnostní kombinatorika a její aplikace. Americká matematická společnost, 1991 (str. 63)