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 [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,[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 (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics 9 (1): R35:1–R35:14, https://www.combinatorics.org/Volume_9/Abstracts/v9i1r35.html
 |  |
