Misplaced Pages

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 ${\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, 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.

Notes

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

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

• v
• t
• e

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

• v
• t
• e

• Combinatorics
• Conjectures that have been proved
• Number theory stubs
• Graph theory stubs