Los gráficos de expansión ("escasa gráficas que tienen fuertes propiedades de conectividad") irrumpió en la matemática de la escena torno al cambio de milenio, pero no he tenido éxito en la localización de la procedencia de (a) el concepto, y (b) el nombre del expansor. ¿Alguien sabe? Y puede dar una cita?
Paley gráficos
(la conexión de los pares de elementos que difieren en residuos cuadráticos) son expansores.
El concepto (pero no el nombre) fue introducido por Barzdin y la prueba de Kolmogorov en
A. N. Kolmogorov y Y. M. Barzdin, "En la realización de redes en el espacio tridimensional" en Obras escogidas de Kolmogorov, vol. 3, Kluwer, Dordrecht, 1993, 194-202.
que fue publicado en 1967. Se demostró que existen a través de un argumento probabilístico. Ellos fueron redescubiertas y nombre expansores por Pinsker en su papel
M. S. Pinsker, "la complejidad de un concentrador", Actas del vii Internacional de Teletraffic Congreso (Estocolmo, 1973), pp 318/1–318/4, Papel Nº 318.
disponible aquí (véase el apéndice). También demuestra que existe a través de un argumento probabilístico. Los primeros ejemplos explícitos fueron encontrados por Margulis en su papel
G. Margulis, Explícita construcciones de concentradores, Problemy Peredachi Informatsii, 9(4) (1973), pp 71-80; Problemas de Informar. Transmisión, 10 (1975), pp 325-332.
y por Gabber-Galil en su papel
O. Gabber y Z. Galil, Explícita construcciones de tamaño linear superconcentrators, Proc. 20 Simposio Anual sobre los Fundamentos de la Ciencia de la computación, 1979, pp 364-370.
Por el camino, aprendí sobre la historia de la siguiente encantadora de papel:
M. Gromov y L. Guth, Generalizaciones de la prueba de Kolmogorov-Barzdin la incrustación de las estimaciones. El Duque De Matemáticas. J. 161 (2012), no. 13, 2549-2603.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
