Lévy grafik ailesi - Lévy family of graphs

İçinde grafik teorisi, bir matematik dalı, bir Lévy grafik ailesi bir aile grafikler G_n, n = 1, 2, 3, ..., belirli bir tür "kompaktlık" veya "karışıklığa" sahip. Doğal olarak oluşan birçok grafik ailesi Lévy aileleridir. Birçok matematikçi bu gerçeği kaydetti ve hazır bir açıklaması yokmuş gibi görünmesine şaşırdığını ifade etti.

Resmen, bir grafik ailesi G_n, n = 1, 2, 3, ..., eğer varsa, bir Lévy ailesidir ${displaystyle varepsilon> 0}$

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

nerede

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

Buraya D ... grafik çapı nın-nin G, ve Bir_(n) ... n-grafik komşuluk nın-nin Bir. Maksimizasyonun alt kümelere göre değiştiğini unutmayın. Bir nın-nin Gtabi Bir yarıdan büyük olmak G

Başka bir deyişle, bu, birinin en az yarısı kadar bir boyut alt kümesini alabileceği anlamına gelir. Gve sadece havaya uçur ${displaystyle epsilon}$ ve neredeyse tüm setle sonuçlanır.

Uzun "ip gibi" (yani "kompakt" olmayan) grafik aileleri döngü grafiği düzenin n açıkça böyle bir mülke sahip değildir: aşağıdakileri içeren bir alt küme düşünülebilir: n / 2 bir noktanın mahallesi (örneğin gece yarısından saat altıya kadar). Grafiğin grafik çapı vardır D yaklaşık n / 2. Böylece ${displaystyle epsilon D}$-Alt kümenin mahallesi yalnızca yaklaşık boyuttadır n / 2. Bir Levy ailesi bu mahalleye neredeyse tüm seti kapsayacaktı. Bir Levy ailesinin çok özel bir kompakt yapıya sahip olması gerektiği açık olmalıdır.

• Hypercube grafikleri düzenin n bir Lévy ailesi olarak biliniyor.
• Eğer S_n unsurları olan noktaları içeren grafiktir. permütasyon grubu nın-nin n elemanlar, kenarları birleştirme noktaları ile farklılık gösteren aktarım, sonra dizi S_ben, i = 1,2, ..., bir Lévy ailesidir.

Referanslar

• Bollobás (editör). Olasılık kombinatorikleri ve uygulamaları. Amerikan Matematik Derneği, 1991 (s63)