Detección y Análisis de Amoebas

Resumen:
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’ es un reemplazo admisible de arista. Además, 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 de n vértices Kn, G2 puede ser obtenida 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 1, 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 plática mostraremos los resultados obtenidos de correr un algoritmo para identificar amoebas, globales y locales, de entre todas las gráficas no etiquetadas con entre 1 y 10 vértices.

Presentamos también a aquellas amoebas conexas de orden mínimo que son globales pero no locales. 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.

Semblanza:
Marcos estudió la Licenciatura en Tecnología en el Centro de Física Aplicada y Tecnología Avanzada de la UNAM, Querétaro, y actualmente estudia la Maestría en Ciencias Matemáticas en el Instituto de Matemáticas, Juriquilla, desarrollando su tesis bajo la dirección de la Dra. Amanda Montejano Cantoral de la Unidad Multidisciplinaria de Docencia e Investigación, Unidad Juriquilla, de la Facultad de Ciencias de la UNAM.