アルスパッハの予想

アルスパックの予想は、所定のサイクル長を持つ完全グラフの互いに素なサイクル被覆を特徴付ける数学定理です。これは、 1981 年に研究課題として提起したブライアン・アルスパックにちなんで名付けられました。証明は、ダリン・ブライアント、ダニエル・ホースリー、ウィリアム・ペッターソン (2014) によって発表されました。

この文脈では、分離サイクルカバーは、2 つのサイクルが同じエッジを使用しない単純なサイクルの集合であり、グラフのすべてのエッジを含みます。分離サイクルカバーが存在するためには、各頂点の次数が偶数であることが必要です。これは、各頂点の次数が、その頂点を含むサイクルの数である偶数の 2 倍であるためです。また、分離サイクルカバー内のサイクルが所定の長さの集合を持つためには、所定のサイクル長の合計が所定のグラフ内のエッジの総数に等しくなることも必要です。Alspach は、完全グラフの場合、次の 2 つの必要条件も十分であると予想しました。が奇数 (したがって次数は偶数) であり、所定のサイクル長のリスト (すべて最大) を足すと(完全グラフ内のエッジの数) になる場合、完全グラフは常に所定の長さのサイクルに分解できます。これは、Bryant、Horsley、および Pettersson が証明したことです。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle {\tbinom {n}{2}}}$${\displaystyle K_{n}}$

頂点の数が偶数である完全グラフの場合、グラフを完全マッチングと、合計が となる所定の長さのサイクルの集合に分解することが常に可能であるとアルスパッハは予想した。この場合、マッチングによって各頂点の奇数次数が除去され、偶数次数のサブグラフが残り、残りの条件は再びサイクルの長さの合計がカバーされるエッジの数に等しいというものである。この予想の変形は、ブライアント、ホースリー、ペッターソンによっても証明された。 ${\displaystyle K_{n}}$${\displaystyle n}$${\displaystyle {\tbinom {n}{2}}-{\tfrac {n}{2}}}$

完全グラフを与えられた 2正則グラフのコピーに分解するオーバーヴォルファッハ問題は関連しているが、どちらも他方の特殊なケースではない。 が頂点を持つ 2 正則グラフで、特定の長さのサイクルの互いに素な和集合から形成される場合、 に対するオーバーヴォルファッハ問題の解決は、完全グラフをの各サイクルのコピーに分解することにもなる。しかし、 を各サイズのこれだけ多くのサイクルに分解すると、必ずしも のコピーを形成する互いに素なサイクルにグループ化できるわけではなく、一方で、アルスパッハの予想のすべてのインスタンスが、各サイクルのコピーを持つサイクルの集合を伴うわけではない。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle G}$${\displaystyle (n-1)/2}$${\displaystyle G}$${\displaystyle K_{n}}$${\displaystyle G}$${\displaystyle (n-1)/2}$

• アルスパック、B. (1981)、「問題3」、研究問題、離散数学、36 (3): 333、doi :10.1016/s0012-365x(81)80029-5
• ブライアント、ダリン; ホースリー、ダニエル; ペッターソン、ウィリアム (2014)、「サイクル分解 V: 完全グラフから任意の長さのサイクルへの分解」、ロンドン数学会紀要、第 3 シリーズ、108 (5): 1153–1192、arXiv : 1204.3709、doi :10.1112/plms/pdt051、MR  3214677
• チャートランド, ゲーリー;レスニアック、リンダ。Zhang、Ping (2015)、「Alspach's conjecture」、Graphs & Digraphs、Textbooks in Mathematics、vol. 39 (第 6 版)、CRC Press、p. 349、ISBN 9781498735803