Toida's conjecture

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

^ 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.
^ Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics, 9 (1): R35:1–R35:14, doi:10.37236/1651, MR 1928787

This number theory-related article is a stub. You can help Wikipedia by expanding it.

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

[1] S. Toida: "A note on Adam's conjecture", Journal of Combinatorial Theory (B), pp. 239–246, October–December 1977

[2] 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.

[3] Golfand, J.J., N.L. Najmark and R. Poschel: The structure of S-rings over Z2m, preprint (1984).

[4] 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.

[5] Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics, 9 (1): R35:1–R35:14, doi:10.37236/1651, MR 1928787

[1]

[2]

[3]

[4]

[5]