戸井田の予想

組合せ数学において、戸井田予想は1977年に戸井田俊一によって提唱され^{[1] 、1967年に反証された}アダム予想を改良したものである。

声明

どちらの予想も巡回グラフに関するものである。これらは正の整数 と正の整数の集合から定義されるグラフである。頂点は 0 から までの数で識別でき、2つの頂点と は、それらの差を法として集合 に属する場合、辺で結ばれている。加法を法とする巡回群のすべての対称性は、 - 頂点巡回グラフの対称性 を生じ、アダムはこれらが巡回グラフの唯一の対称性であると（誤って）予想した。 ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle n-1}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle n}$

しかし、アダムの予想に対する既知の反例としては、 のいくつかの要素がと非自明な約数を共有する集合が挙げられる。トイダの予想によれば、 のすべての要素がと互いに素であるとき、およびの巡回グラフの唯一の対称性は、基礎となる巡回群に由来する対称性である。 ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$

証明

この予想は、 nが素数冪である特殊なケースにおいて、1978年にクリンとポシェルによって証明され、^[2] 1984年にゴルファンド、ナジマーク、ポシェルによって証明された^。[3]

この予想は、2001年にムジチュク、クリン、ポシェルによってシュア代数を用いて完全に証明され、^[4]また同時に、2002年にドブソンとモリスによって有限単純群の分類を用いて完全に証明されました。^[5]

注記

1. S. Toida：「アダムの予想に関するノート」、Journal of Combinatorial Theory (B)、pp. 239–246、1977年10月-12月
2. Klin, MH および R. Poschel: ケーニッヒ問題、巡回グラフの同型問題、およびシューア環法、グラフ理論における代数的手法、第 I 巻、第 II 巻、セゲド、1978 年、405–434 頁。
3. Golfand, JJ、NL Najmark、R. Poschel: Z2m上のSリングの構造、プレプリント（1984）。
4. Klin, MH, M. Muzychuk および R. Poschel: シュアー環理論による巡回グラフの同型性問題、コードおよびアソシエーションスキーム、アメリカ数学協会、2001 年。
5. ドブソン、エドワード;モリス、ジョイ(2002)、「戸田の予想は正しい」、電子組合せ論ジャーナル、9 (1): R35:1–R35:14、doi :10.37236/1651、MR  1928787