Las autoridades de la Facultad de Ciencias Exactas y Naturales y del Doctorado en Ciencia y Tecnología invitan a la defensa de Ana Laura Gargantini titulada “Propiedades combinatorias de los asociaedros de grafos". La tesis ha sido dirigida por el Dr. Pablo Torres y el Co-dirigida por el Dr. Sebastián Simondi. La defensa tendrá lugar el día martes 26 de junio a las 14:30 horas en el Auditorio de la FCEN.
Resumen
Los asociaedros de grafos, introducidos por Carr y Devadoss, generalizan diversas familias de politopos, incluidos los asociaedros clásicos. Más allá de su relevancia geométrica, constituyen una herramienta valiosa para el estudio de estructuras combinatorias. Dado un grafo conexo G, el 1-esqueleto de su asociaedro A(G) es isomorfo a su grafo de rotación R(G), cuyos vértices son los árboles de búsqueda en G y cuyas aristas están determinadas por la operación de rotación entre ellos. En esta tesis estudiamos aspectos combinatorios de estos objetos, profundizando en tres propiedades de sus grafos de rotación asociados: el diámetro, el número cromático y el espectro.
Como enfoque general, analizamos primero cómo cambia la estructura de R(G) al aplicar ciertas operaciones al grafo subyacente G: añadir un vértice pendiente, un mellizo verdadero o un mellizo falso. Proporcionamos una caracterización estructural completa de los grafos de rotación resultantes. Utilizando estas descripciones, investigamos su número cromático e identificamos condiciones bajo las cuales este parámetro permanece constante tras dichas operaciones. Como aplicación, demostramos que el número cromático es 3 para los grafos de rotación de los grafos threshold no completos y bipartitos completos.
Respecto al diámetro, establecemos una relación entre la estructura de R(G) y R(G-S) para un conjunto particular S de aristas. Mostramos que si W es un conjunto de mellizos verdaderos en G, y S es el conjunto de aristas con ambos extremos en W, entonces R(G-S) es un grafo cociente de R(G), obteniendo a partir de ello una cota inferior para su diámetro. Utilizando este resultado, determinamos el diámetro exacto de los grafos de rotación de los grafos molino generalizados. Además, aportamos una nueva cota inferior para el diámetro en grafos bipartitos completos balanceados y calculamos el valor exacto de diam(R(K_{2,q})) para q entre 3 y 8.
Finalmente, contribuimos al estudio de las propiedades espectrales de los grafos de rotación, estableciendo una cota inferior para el segundo autovalor más grande de R(G). Para grafos split completos y bipartitos completos, obtenemos una cota superior para su expansión por aristas, lo que permite mejorar la cota espectral general mediante las desigualdades de Cheeger. En esteloedros, identificamos dos autovalores pequeños adicionales. Concluimos con perspectivas futuras y problemas abiertos en el área.
