Estudio Computacional de Amoebas y sus Propiedades

Ponente(s): Marcos Emmanuel González Laffitte, Dra. Amanda Montejano Cantoral

Dadas una gráfica G, una arista e en G y una arista e’ en el complemento de G, si la gráfica G - e + e’ es isomorfa a G, diremos que el reemplazo de arista de e por e’ en G es un reemplazo admisible de arista. De esta forma, diremos que un gráfica G de orden n es una amoeba local si, dadas cualesquiera dos copias G1 y G2 de G encajadas en la gráfica completa Kn de n vértices, es posible obtener G2 a partir de G1 por medio de una sucesión de reemplazos admisibles de aristas. Por otro lado, diremos que G es una amoeba global si existe un entero T mayor o igual a 0, tal que la unión disjunta de G con t copias disjuntas de K1 (la gráfica G más t vértices aislados) es una amoeba local para todo t mayor igual a T. En esta miniplática resumiremos los resultados obtenidos de correr un algoritmo para identificar amoebas, globales y/o locales, en dos colecciones de gráficas: todas las gráficas no isomorfas con entre 1 y 10 vértices, y todos los árboles no isomorfos con entre 1 y 22 vértices. Presentamos también algunos ejemplos extremales interesantes. Las amoebas son una familia de gráficas originalmente definidas por el Dr. Yair Caro, la Dra. Adriana Hansberg y la Dra. Amanda Montejano, en el contexto de problemas de coloraciones de tipo Ramsey-Turán. Los resultados mostrados aquí son el avance del trabajo de tesis de maestría de Marcos Laffitte con la Dra. Amanda Montejano Cantoral.