Reconstrucción de gráficas de fichas

Ponente(s): Ana Laura Trujillo Negrete, Ruy Fabila Monroy

Sea G una gráfica de orden n y sea k un entero entre 1 y n−1. La gráfica de k-fichas de G es la gráfica cuyos vértices son todos los k-conjuntos de V(G) y donde dos de estos k-conjuntos son adyacentes si su diferencia simétrica es un par de vértices adyacentes en G. El estudio de las gráficas de fichas data (al menos) a finales de la década de los 80's, y desde entonces han sido estudiadas por varios matemáticos, entre ellos, el matemático Paul Erdös, y con distintos objetivos, tales como el problema de isomorfismo en gráficas así como para modelar fenómenos físicos. En el año 2012, Ruy Fabila et al. conjeturaron que si G y H son dos gráficas tales que sus gráficas de k-fichas son isomorfas para algún k, entonces G y H son isomorfas. Esta conjetura es equivalente a mostrar que una gráfica G puede reconstruirse de manera única (salvo isomorfismo) a partir de su gráfica de k-fichas. El objetivo de esta plática es mostrar que si G es una gráfica conexa con cuello mayor que cuatro, entonces podemos reconstruir a G a partir de su gráfica de 2-fichas. Además, hablaremos de los antecedentes al problema de reconstrucción de gráficas de fichas.