Pilas de arena y grafos de ramanujan
No Thumbnail Available
Date
2011
Authors
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
El Modelo Abeliano de Pila de Arena y los Grafos de Ramanujan son los protagonistas de esta historia. El Modelo de Pila de Arena o modelo BTW, (introducido por los físicos Per Bak, Chao Tang y Kurt Wiesenfeld en 1988), es un sistema dinámico disipativo discreto definido sobre un grafo en el que hay intercambio de información entre los vértices del grafo. Decimos que un grafo G es óptimo para el Modelo de Pila de Arena si y sólo si la dinámica del modelo se estabiliza rápidamente. En este trabajo se estudia el comportamiento asintótico del Modelo Abeliano de Pilas de Arena sobre grafos de alta conectividad. Centramos nuestra atención en grafos de Ramanujan. Nosotros conjeturábamos que el proceso de estabilización es veloz (eficiente) sobre clases de grafos de Ramanujan, esto es: conjeturábamos que sobre esta clase de grafos las avalanchas eran mucho más cortas. La mejor cota superior para la longitud de avalanchas críticas sobre grafos generales es la cota de Tardos, la cual estipula que las avalanchas tienen una longitud acotada por O(n³), donde n es el número de vértices del grafo, siendo esta cota óptima. Nosotros probamos que sobre grafos de Ramanujan, las avalanchas críticas tienen una longitud acotada por O(n1,5).
Description
Keywords
Modelo abeliano de pilas de arena, Grafos de Ramanujan, Auto-organización crítica, Complejidad computacional.