Sesión Matemática DiscretaPropiedades espectrales de los asociaedros de grafos
Ana Gargantini
Facultad de Ciencias Exactas y Naturales de la Universidad Nacional de Cuyo, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los asociaedros de grafos fueron introducidos por Carr y Devadoss [1], como una generalización de los asociaedros clásicos, como así también de otras familias conocidas de politopos. En particular, cuando $G$ es un camino, un ciclo, un grafo completo o un grafo estrella, el asociaedro $\mathcal{A}(G)$ de $G$ permite recuperar, respectivamente, el asociaedro clásico, el cicloedro, el permutoedro o el stelloedro. Más allá de su caracter de generalización, los asociaedros de grafos constituyen una herramienta valiosa en el estudio de estructuras combinatorias y su representación geométrica, y han encontrado aplicaciones en áreas tan diversas como la optimización, los sistemas jerárquicos de visualización, la generación de estructuras aleatorias y los modelos probabilísticos. El interés en estos objetos no solo recae en los politopos mismos, sino también en las propiedades de los grafos que estos determinan. Desde la teoría de grafos, se han estudiado diversos parámetros, entre ellos su hamiltonicidad, conectividad y diámetro [2,3].
Una herramienta central en la teoría de grafos es el análisis espectral de la matriz de adyacencia. El espectro de un grafo, definido como el conjunto de autovalores de dicha matriz, está estrechamente vinculado con propiedades estructurales como la conectividad, la expansión y la simetría, y desempeña un papel relevante en aplicaciones relacionadas con el isomorfismo, las caminatas aleatorias y el análisis de robustez. Sin embargo, pese a su importancia, el estudio espectral de los asociaedros de grafos ha recibido poca atención; en la literatura solo se encuentran algunos resultados sobre los autovalores del permutoedro y el asociaedro clásico [4].
En este trabajo, realizamos una contribución al análisis espectral de los asociaedros de grafos. En particular, obtenemos una cota inferior para el segundo autovalor más grande del asociaedro $\mathcal{A}(G)$ asociado a un grafo $G$. Asimismo, empleando particiones equitables, estudiamos el espectro de los stelloedros $\mathcal{A}(K_{1,n})$, probando la existencia de un autovalor en el intervalo $(n-2, n-1]$ e identificando, además, dos autovalores pequeños adicionales.
Trabajo en conjunto con: Adrián Pastine (Instituto de Matemática Aplicada San Luis, CONICET-UNSL), Pablo Torres (Universidad Nacional de Rosario y CONICET) y Mario Valencia-Pabon (Université de Lorraine, CNRS, Inria, LORIA).
Referencias
[1] M. Carr, S. Devadoss. Coxeter complexes and graph-associahedra. Topology and its Applications, 153.12 (2006): 2155-2168.
[2] T. Manneville, V. Pilaud. Graph properties of graph associahedra. Séminaire Lotharingien de Combinatoire, 73 (2015), Article B73d.
[3] J. Cardinal, L. Pournin, M. Valencia-Pabon. Diameter estimates for graph associahedra. Annals of Combinatorics, 26 (2022): 873–902.
[4] S. Cioaba, V. Gupta. A lower bound for the smallest eigenvalue of a graph and an application to the associahedron graph. Bulletin of the Romanian Mathematical Society, 65.113, no. 4 (2022): 393-404.