Sesión Matemática DiscretaPropiedades 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.
Una rotación en un árbol binario es una operación local y reversible sobre dicho árbol, que intercambia el nivel de un par de nodos adyacentes. Dado $n\in\mathbb{N}$, el asociaedro clásico $(n-1)$-dimensional se puede describir como el politopo cuyo 1-esqueleto es isomorfo al grafo de rotaciones de árboles binarios de $n$ nodos internos, es decir, el grafo cuyos vértices son todos los árboles binarios de $n$ nodos internos, y dos árboles son adyacentes si difieren en una rotación. Esta construcción se generaliza para definir el asociaedro de un grafo $G$ a partir del grafo de rotaciones de los árboles de búsqueda sobre $G$, recuperando familias conocidas de politopos como casos particulares: el asociaedro clásico como asociaedro de un camino, el permutoedro como asociaedro de un grafo completo, el cicloedro como asociaedro de un ciclo, entre otros [1].
Los asociaedros como politopos son objetos de interés en geometría discreta y topología algebraica, pero también admiten formulaciones que permiten establecer relaciones con distintos sistemas combinatorios. Las propiedades estructurales de los grafos que determinan los asociaedros resultan de utilidad debido a sus variadas aplicaciones. Estas van desde complejidad computacional hasta física [4] y biología [5]. Para el asociaedro clásico, se han estudiado y establecido distintos parámetros de grafos, entre ellos su diámetro [3]. Para el caso general, solo se conocen resultados sobre el diámetro de asociaedros de algunas familias de grafos [2]. En la actualidad esta sigue siendo un área de estudio abierta.
En esta comunicación, presentaremos resultados obtenidos a partir del estudio de distancias en asociaedros de grafos bipartitos completos. Además, mostraremos el efecto de eliminar ciertos subconjuntos de aristas de un grafo en el diámetro de su asociaedro, acotándolo inferior y superiormente. Mostraremos también cómo se pueden utilizar estas cotas en el cálculo de algunos diámetros de asociaedros de grafos bipartitos completos. Por otro lado, presentaremos algunos resultados sobre ciertos parámetros de asociaedros de grafos estrella, en particular su número de independencia y su número cromático.
Trabajo en conjunto con: Adrián Pastine (Instituto de Matemática Aplicada San Luis, CONICET-UNSL) y Pablo Torres (Universidad Nacional de Rosario - CONICET).
Referencias
[1] J. Cardinal, S. Langerman, P. Perez-Lantero, On the diameter of tree associahedra, Electronic Journal of Combinatorics, 25(4) (2018), P4.18.
[2] J. Cardinal, L. Pournin, M. Valencia-Pabon, Diameter estimates for graph associahedra, Annals of Combinatorics, 26 (2022), 873–902.
[3] L. Pournin, The diameter of associahedra, Advances in Mathematics, 259 (2014), 13–42.
[4] F. Santos, A counterexample to the Hirsch conjecture, Annals of Mathematics, 176 (2012), 383–412.
[5] C. Semple, M. Steel, Phylogenetics. Oxford Lecture Series in Mathematics and its Applications 24, Oxford University Press, 2003.