In combinatorial mathematics, Toida's conjecture, due to Shunichi Toida in 1977,^[1] is a refinement of the disproven Ádám's conjecture from 1967.

Statement

Both conjectures concern circulant graphs. These are graphs defined from a positive integer ${\displaystyle n}$ and a set ${\displaystyle S}$ of positive integers. Their vertices can be identified with the numbers from 0 to ${\displaystyle n-1}$, and two vertices ${\displaystyle i}$ and ${\displaystyle j}$ are connected by an edge whenever their difference modulo ${\displaystyle n}$ belongs to set ${\displaystyle S}$. Every symmetry of the cyclic group of addition modulo ${\displaystyle n}$ gives rise to a symmetry of the ${\displaystyle n}$-vertex circulant graphs, and Ádám conjectured (incorrectly) that these are the only symmetries of the circulant graphs.

However, the known counterexamples to Ádám's conjecture involve sets ${\displaystyle S}$ in which some elements share non-trivial divisors with ${\displaystyle n}$. Toida's conjecture states that, when every member of ${\displaystyle S}$ is relatively prime to ${\displaystyle n}$, then the only symmetries of the circulant graph for ${\displaystyle n}$ and ${\displaystyle S}$ are symmetries coming from the underlying cyclic group.

Proofs

The conjecture was proven in the special case where n is a prime power by Klin and Poschel in 1978,^[2] and by Golfand, Najmark, and Poschel in 1984.^[3]

The conjecture was then fully proven by Muzychuk, Klin, and Poschel in 2001 by using Schur algebra,^[4] and simultaneously by Dobson and Morris in 2002 by using the classification of finite simple groups.^[5]

Notes