Lévy familj av grafer

Inom grafteorin , en gren av matematiken, är en Lévy-familj av grafer en familj av grafer G _n , n = 1, 2, 3, ..., som har en viss typ av "kompakthet" eller "trasslighet". Många naturligt förekommande graffamiljer är Lévy-familjer. Många matematiker har noterat detta faktum och har uttryckt förvåning över att det inte verkar ha en klar förklaring.

Formellt är en familj av grafer G _n , n = 1, 2, 3, ... en Lévy-familj om, för någon $\varepsilon >0$

$\lim _{n\longrightarrow \infty }\alpha \left(G_{n},\varepsilon \right)=0$

var

$\alpha (G,\varepsilon )=\max \left\{1-{\frac {\left|A_{(\varepsilon D)}\right|}{|G|}}\,:\, A\subseteq G,|A|>|G|/2\right\}.$

Här är D grafens diameter för G , och A _{( n )} är n -grafområdet till A . Observera att maximeringen sträcker sig över delmängder A av G , med förbehåll för att A är över hälften av G

Med ord betyder detta att man kan ta en delmängd av storleken minst hälften av G , och spränga den med endast $\epsilon$ av grafens diameter, och sluta med nästan hela mängden.

Långa "trådiga" (dvs inte "kompakta") familjer av grafer, såsom cykelgrafen av ordning n , har uppenbarligen inte en sådan egenskap: man skulle kunna överväga en delmängd som omfattar n/2 grannskapet av en punkt (midnatt till sex o 'klocka, säg). Grafen har en grafdiameter D på cirka n/2 . Så $\epsilon D$ -grannskapet till delmängden är bara av storleken omkring n/2 . En Levy-familj skulle ha denna stadsdel som täcker nästan hela uppsättningen. Det ska stå klart att en Levy-familj måste ha en mycket speciell typ av kompakt struktur.

• Hyperkubgrafer av ordning n är kända för att vara en Lévy-familj.
• Om S _n är grafen med punkter som är element i permutationsgruppen _av n element , med kanter som förenar punkter som skiljer sig åt genom en transponering , då är serien Si , i=1,2,... , en Lévy-familj.

• Bollobás (redaktör). Probabilistisk kombinatorik och dess tillämpningar. American Mathematical Society , 1991 (s.63)