En teoría de grafos , una rama de las matemáticas, una familia de grafos de Lévy es una familia de grafos G n , n = 1, 2, 3, ..., que poseen un cierto tipo de "compacidad" o "enredo". Muchas familias de grafos que se dan de forma natural son familias de Lévy. Muchos matemáticos han observado este hecho y han expresado su sorpresa por el hecho de que no parezca tener una explicación clara.
Formalmente, una familia de grafos G n , n = 1, 2, 3, ..., es una familia de Lévy si, para cualquier
dónde
Aquí D es el diámetro del gráfico de G y A ( n ) es el entorno de n -gráficos de A. Nótese que la maximización se extiende sobre subconjuntos A de G , siempre que A sea más de la mitad del tamaño de G.
En palabras, esto significa que uno puede tomar un subconjunto de tamaño al menos la mitad de G y ampliarlo solo por el diámetro del grafo, y terminar con casi todo el conjunto.
Las familias de grafos largas y "fibrosas" (es decir, no "compactas"), como el grafo cíclico de orden n, claramente no tienen esa propiedad: se podría considerar un subconjunto que comprenda la vecindad n/2 de un punto (de la medianoche a las seis en punto, por ejemplo). El grafo tiene un diámetro de grafo D de aproximadamente n/2 . Por lo tanto, la vecindad del subconjunto solo tiene un tamaño de aproximadamente n/2 . Una familia de Levy tendría esta vecindad cubriendo casi todo el conjunto. Debería estar claro que una familia de Levy debe tener un tipo muy especial de estructura compacta.
