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.

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, [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

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

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.

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".

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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).

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.

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.