Toida's conjecture

Last updated

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.



Both conjectures concern circulant graphs. These are graphs defined from a positive integer 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 edge whenever 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.


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", 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, MR   1928787

Related Research Articles

<span class="mw-page-title-main">Equivalence class</span> Mathematical concept

In mathematics, when the elements of some set have a notion of equivalence, then one may naturally split the set into equivalence classes. These equivalence classes are constructed so that elements and belong to the same equivalence class if, and only if, they are equivalent.

<span class="mw-page-title-main">Isomorphism</span> In mathematics, invertible homomorphism

In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".

<span class="mw-page-title-main">Group (mathematics)</span> Set with associative invertible operation

In mathematics, a group is a non-empty set with an operation that satisfies the following constraints: the operation is associative, has an identity element, and every element of the set has an inverse element.

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Klein four-group</span> Mathematical abelian group

In mathematics, the Klein four-group is an abelian group with four elements, in which each element is self-inverse (composing it with itself produces the identity) and in which composing any two of the three non-identity elements produces the third one. It can be described as the symmetry group of a non-square rectangle (with the three non-identity elements being horizontal and vertical reflection and 180-degree rotation), as the group of bitwise exclusive or operations on two-bit binary values, or more abstractly as Z2 × Z2, the direct product of two copies of the cyclic group of order 2. It was named Vierergruppe (meaning four-group) by Felix Klein in 1884. It is also called the Klein group, and is often symbolized by the letter V or as K4.

<span class="mw-page-title-main">Cyclic group</span> Mathematical group that can be generated as the set of powers of a single element

In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted Cn, that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as an integer power of g in multiplicative notation, or as an integer multiple of g in additive notation. This element g is called a generator of the group.

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Cubic graph</span> Graph with all vertices of degree 3

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

<span class="mw-page-title-main">Circulant graph</span> Undirected graph acted on by a vertex-transitive cyclic group of symmetries

In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.

<span class="mw-page-title-main">Paley graph</span>

In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally.

<span class="mw-page-title-main">Rado graph</span> Infinite graph containing all countable graphs

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Frucht's theorem</span>

Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G.

In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

<span class="mw-page-title-main">Zero-divisor graph</span> Graph of zero divisors of a commutative ring

In mathematics, and more specifically in combinatorial commutative algebra, a zero-divisor graph is an undirected graph representing the zero divisors of a commutative ring. It has elements of the ring as its vertices, and pairs of elements whose product is zero as its edges.

<span class="mw-page-title-main">Sergei Evdokimov</span>

Sergei Alekseevich Evdokimov was a Russian mathematician who contributed to the theory of modular forms, computational complexity theory, algebraic combinatorics and p-adic analysis.

Joy Morris is a Canadian mathematician whose research involves group theory, graph theory, and the connections between the two through Cayley graphs. She is also interested in mathematics education, is the author of two open-access undergraduate mathematics textbooks, and oversees a program in which university mathematics education students provide a drop-in mathematics tutoring service for parents of middle school students. She is a professor of mathematics at the University of Lethbridge.

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.