Toida's conjecture

In combinatorial mathematics, Toida's conjecture, due to Shunichi Toida in 1977, 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 [math]\displaystyle{ n }[/math] and a set [math]\displaystyle{ S }[/math] of positive integers. Their vertices can be identified with the numbers from 0 to [math]\displaystyle{ n-1 }[/math], and two vertices [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] are connected by an edge whenever their difference modulo [math]\displaystyle{ n }[/math] belongs to set [math]\displaystyle{ S }[/math]. Every symmetry of the cyclic group of addition modulo [math]\displaystyle{ n }[/math] gives rise to a symmetry of the [math]\displaystyle{ n }[/math]-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 [math]\displaystyle{ S }[/math] in which some elements share non-trivial divisors with [math]\displaystyle{ n }[/math]. Toida's conjecture states that, when every member of [math]\displaystyle{ S }[/math] is relatively prime to [math]\displaystyle{ n }[/math], then the only symmetries of the circulant graph for [math]\displaystyle{ n }[/math] and [math]\displaystyle{ S }[/math] 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, and by Golfand, Najmark, and Poschel in 1984.

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