La conjetura de Toida

En matemáticas combinatorias , la conjetura de Toida , debida a Shunichi Toida en 1977, ^{[ 1 ]} es un refinamiento de la conjetura de Ádám refutada de 1967.

Ambas conjeturas se refieren a grafos circulantes . Estos son grafos definidos a partir de un entero positivo.${\displaystyle n}$y un conjunto${\displaystyle S}$de enteros positivos. Sus vértices pueden identificarse con los números del 0 al${\displaystyle n-1}$y dos vértices${\displaystyle i}$y${\displaystyle j}$están conectados por una arista siempre que su diferencia módulo${\displaystyle n}$pertenece al conjunto${\displaystyle S}$. Toda simetría del grupo cíclico de adición módulo${\displaystyle n}$ da lugar a una simetría de la${\displaystyle n}$-grafos circulantes de vértices, y Ádám conjeturó (incorrectamente) que estas son las únicas simetrías de los grafos circulantes.

Sin embargo, los contraejemplos conocidos a la conjetura de Ádám involucran conjuntos${\displaystyle S}$en el que algunos elementos comparten divisores no triviales con${\displaystyle n}$La conjetura de Toida afirma que, cuando cada miembro de${\displaystyle S}$es relativamente primordial para${\displaystyle n}$, entonces las únicas simetrías del grafo circulante para${\displaystyle n}$y${\displaystyle S}$son simetrías que provienen del grupo cíclico subyacente.

La conjetura fue demostrada en el caso especial donde n es una potencia prima por Klin y Poschel en 1978, ^{[ 2 ]} y por Golfand, Najmark y Poschel en 1984. ^{[ 3 ]}

La conjetura fue demostrada completamente por Muzychuk, Klin y Poschel en 2001 utilizando el álgebra de Schur , ^{[ 4 ]} y simultáneamente por Dobson y Morris en 2002 utilizando la clasificación de grupos simples finitos . ^{[ 5 ]}