Ciclos hamiltonianos y simetría en los niveles medios del hipercubo.

Abstract: Consideremos el grafo de los niveles medios que tiene como vértices todos los bitstrings de largo 2n+1 con exactamente n o n+1 unos, y aristas entre todo par de bitstrings que difieren en exactamente una coordenada. El recientemente demostrado teorema de los niveles medios dicta que este grafo tiene un ciclo hamiltoniano. Siendo los niveles medios un grafo altamente simétrico, este teorema es uno de los ejemplos más notables de la conjetura de Lovász: Todo grafo conexo y altamente simétrico (salvo 5 excepciones) tiene un ciclo hamiltoniano. Dicha interacción entre simetría y hamiltonicidad no es bien entendida, en particular, las construcciones conocidas de ciclos hamiltonianos de los niveles medios no parecen ser simétricas o explotar la simetría que proporciona el grafo.

En esta línea el 2011 Knuth conjetura la existencia de un ciclo hamiltoniano que respete la simetría de los niveles medios, esto es que sea invariante bajo 1-shift.

En esta charla:
– introduciremos de manera accesible la noción de simetría en grafos, las conjeturadas conexiones con la hamiltonicidad y
– bosquejaremos una demostración de la conjetura de Knuth.

La demostración está basada en una reducción a un problema de conectividad y una particular relación entre los niveles medios y los objetos de Catalán. Más aún, las técnicas desarrolladas nos permiten construir ciclos hamiltonianos k-shift invariantes para todo k coprimo con 2n+1.

Posted on Dec 1, 2020 in Seminario de Grafos, Seminars