オーバーヴォルフアッハ問題

数学における未解決の問題:

どの 2 正則 -頂点グラフに対して、完全グラフをの辺が互いに素なコピーに分解できますか?${\displaystyle n}$${\displaystyle G}$${\displaystyle K_{n}}$${\displaystyle G}$

（数学における未解決の問題がさらに増える）

数学において、オーバーヴォルファッハ問題は、食事客の座席割り当てのスケジュール問題として、またはより抽象的にはグラフ理論における完全グラフのエッジサイクル被覆の問題として定式化される未解決問題である。この問題は、1967年にゲルハルト・リンゲルによってオーバーヴォルファッハ数学研究所で提起されたことにちなんで名付けられた。^[1]この問題は、十分に大きな完全グラフすべてに対して成り立つことが知られている。

オーバーヴォルフアッハで開催される会議では、参加者は円形のテーブルが置かれた部屋で一緒に食事をするのが通例である。テーブルはすべて同じ大きさではなく、座席は食事ごとに順番に並べ替えられる。オーバーヴォルフアッハの問題は、与えられたテーブルセットの座席表をどのように作成すれば、食事のたびにすべてのテーブルが満席になり、会議参加者のすべてのペアがちょうど一度隣同士に座れるかというものである。問題のインスタンスは と表記でき、ここで は与えられたテーブルのサイズである。あるいは、テーブルのサイズが重複している場合は、指数表記法を使用して表記することができる。たとえば、 はサイズ 5 のテーブルが 3 つあるインスタンスを表す。^[1]${\displaystyle OP(x,y,z,\dots )}$${\displaystyle x,y,z,\dots }$${\displaystyle OP(5^{3})}$

グラフ理論の問題として定式化すると、1 回の食事で隣同士に座っている 2 人のペアは、指定された長さのサイクル グラフの非結合和として表すことができ、各ダイニング テーブルに 1 つのサイクルがあります。このサイクルの和は2正則グラフであり、すべての2 正則グラフはこの形式を持ちます。 がこの2 正則グラフで、頂点がある場合、順序の完全グラフがのコピーの辺非結合和として表せるかどうかが問題になります。^[1] ${\displaystyle C_{x}+C_{y}+C_{z}+\cdots }$${\displaystyle G}$${\displaystyle n}$${\displaystyle K_{n}}$${\displaystyle n}$${\displaystyle G}$

解が存在するためには、会議参加者の総数（または同等に、テーブルの総収容人数、または与えられたサイクルグラフの頂点の総数）が奇数でなければならない。なぜなら、各食事で、各参加者は2人の隣人の隣に座るので、各参加者の隣人の総数は偶数でなければならないが、これは参加者の総数が奇数の場合にのみ可能である。しかし、この問題は、 の偶数値に対して、完全マッチングを除く完全グラフのすべての辺が、与えられた2-正則グラフのコピーで覆われるかどうかを問うことにより、 の偶数値にも拡張されている。メネジェ問題（食事客とテーブルの座席配置に関する別の数学的問題）と同様に、この問題の変種は、食事客が夫婦に分かれて配置され、座席配置によって各食事客が配偶者以外の食事客とちょうど1度隣り合うことになると仮定することで定式化できる。^[2]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n/2}$

オーバーヴォルフアッハ問題で解けないことが知られている唯一の例は、、、、およびです。^[3]他のすべての例には解があると広く信じられています。この予想は、下限より大きい順序を持つ大規模完全グラフに対する最近の非構成的かつ漸近的な解によって裏付けられています。下限は定量化されていません。^{[4] [5]}${\displaystyle OP(3^{2})}$${\displaystyle OP(3^{4})}$${\displaystyle OP(4,5)}$${\displaystyle OP(3,3,5)}$

建設的な解決策が知られているケースには、次のようなものがあります。

• とを除くすべてのインスタンス。^{[6] [7] [8] [9] [2]}${\displaystyle OP(x^{y})}$${\displaystyle OP(3^{2})}$${\displaystyle OP(3^{4})}$
• すべてのサイクルの長さが偶数であるすべてのインスタンス。^{[6] [10]}
• （既知の例外を除く）すべてのインスタンス。^{[11] [3]}${\displaystyle n\leq 60}$
• の特定の選択のすべてのインスタンス。自然数の無限部分集合に属します。^{[12] [13]}${\displaystyle n}$
• 既知の例外とを除くすべてのインスタンス。^[14]${\displaystyle OP(x,y)}$${\displaystyle OP(3,3)}$${\displaystyle OP(4,5)}$

カークマンの女子生徒問題、すなわち15人の女子生徒を3人ずつ7通りの方法でグループ化し、各組の女子生徒が1度ずつ現れるようにする問題は、オーバーヴォルフアッハ問題の特殊なケースである。完全グラフのハミルトン分解の問題も、別の特殊なケースである。[ ^10]${\displaystyle OP(3^{5})}$${\displaystyle K_{n}}$${\displaystyle OP(n)}$

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