Toida's conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In combinatorial mathematics, Toida's conjecture, due to Shunichi Toida in 1977,[1] is a refinement of the disproven Ádám's conjecture in 1967. Toida's conjecture states formally:


S is a subset of


then is a CI-digraph.


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]


  1. ^ *S. Toida: "A note on Adam's conjecture", J. 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. ^ *E. Dobson, J. Morris: TOIDA’S CONJECTURE IS TRUE, PhD Thesis, 2002.