Toida's conjecture explained
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
and a set
of positive integers.Their vertices can be identified with the numbers from 0 to
, and two vertices
and
are connected by an edgewhenever their difference
modulo
belongs to set
. Every symmetry of the
cyclic group of addition modulo
gives rise to a
symmetry of the
-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
in which some elements share non-trivial
divisors with
.Toida's conjecture states that, when every member of
is
relatively prime to
, then the only symmetries of the circulant graph for
and
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.
Notes and References
- S. Toida: "A note on Adam's conjecture", Journal of Combinatorial Theory (B), pp. 239–246, October–December 1977
- Klin, M.H. and R. Poschel: The Konig problem, the isomorphism problem for cyclic graphs and the method of Schur rings, Algebraic methods in graph theory, Vol. I, II., Szeged, 1978, pp. 405–434.
- Golfand, J.J., N.L. Najmark and R. Poschel: The structure of S-rings over Z2m, preprint (1984).
- Klin, M.H., M. Muzychuk and R. Poschel: The isomorphism problem for circulant graphs via Schur ring theory, Codes and Association Schemes, American Math. Society, 2001.
