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

数学における未解決問題

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

数学におけるさらなる未解決問題

完全グラフをの3つのコピーに分解し、入力に対するオーバーヴォルフアッハ問題を解く。${\displaystyle K_{7}}$ ${\displaystyle C_{3}+C_{4}}$ ${\displaystyle (3,4)}$

数学において、オーバーヴォルフアッハ問題（オーバーヴォルフアッハじんぶつ、英: Oberwolfach problem）は、未解決問題であり、レストランの座席割り当てのスケジュール問題として、あるいはより抽象的にはグラフ理論における完全グラフの辺閉路被覆の問題として定式化される。この問題は、1967年にゲルハルト・リンゲルによってオーバーヴォルフアッハ数学研究所で提起されたことにちなんで名付けられた。^{[ 1 ]}十分に大きな完全グラフすべてにおいて、この問題が成り立つことが知られている。

処方

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

グラフ理論の問題として定式化すると、同じ食事の席に隣り合って座っている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}$

既知の結果

Glock, Joos, Kim, Kühn, Osthus ^{[ 3 ]}は、オーバーヴォルファッハ問題において有限個を除くすべての例に対して解を見出した。 、、、 に対しては解が存在しないこと^{[ 4 ]}が知られており、その他の例には解が存在すると広く信じられている。 ${\displaystyle OP(3^{2})}$ ${\displaystyle OP(3^{4})}$ ${\displaystyle OP(4,5)}$ ${\displaystyle OP(3,3,5)}$

頂点数が大きい場合の解法には、多くのランダム化ステップが含まれます。構成的解が知られているケースには以下が含まれます。

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

関連する問題

グロック、キューン、オスタス^{[ 14 ]}は、オーバーヴォルフアッハ問題の-一様ハイパーグラフ（大きな）に対する一般化を提案した。 ${\displaystyle k}$ ${\displaystyle n}$

数学における未解決問題

がを割り切り、が長さ 以上のタイトサイクルの頂点分離和である -頂点グラフであるとします。すると、は のコピーに分解可能です。${\displaystyle n}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle 2k+1}$ ${\displaystyle K_{n}^{(k)}}$ ${\displaystyle F}$

数学におけるさらなる未解決問題

より正確には、十分に大きく、かつ自明な必要可分性条件を満たす場合、頂点を合計で 個覆う頂点分離タイトサイクルの集合が与えられたとき、完全な-一様ハイパーグラフはのコピーに分解できると彼らは推測した。この問題は、元の定式化における座席表を求める問題と同等であるが、夕食会を通して各組の人々がちょうど一度連続して座るという問題である。が1つのサイクルのみに収束している場合も、依然として は未解決である。 ${\displaystyle n}$ ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle K_{n}^{(k)}}$ ${\displaystyle F}$ ${\displaystyle k}$ ${\displaystyle F}$

カークマンの女子生徒問題 は、15人の女子生徒を3人ずつ7通りの方法でグループ化し、各組に各女子生徒のペアが1回ずつ現れるようにする問題であり、オーバーヴォルファッハ問題の特殊なケースである。完全グラフのハミルトン分解の問題もまた特殊なケースである。^{[ 9 ]}${\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}$

参考文献

1. Lenz, Hanfried ; Ringel, Gerhard (1991)、「エグモント・ケーラーの数学的研究に関する簡潔なレビュー」、離散数学、97 ( 1– 3): 3– 16、doi : 10.1016/0012-365X(91)90416-Y、MR  1140782
2. Huang, Charlotte; Kotzig, Anton ; Rosa, Alexander (1979)「オーバーヴォルフアッハ問題のバリエーションについて」、Discrete Mathematics、27 (3): 261– 277、doi : 10.1016/0012-365X(79)90162-6、MR 0541472 
3. グロック、ステファン; ヨース、フェリックス; キム、ジェフーン;キューン、ダニエラ; オストゥス、デリック (2021)、「オーバーヴォルフアッハ問題の解決」、ヨーロッパ数学会誌、23 (8): 2511– 2547、arXiv : 1806.04644、doi : 10.4171/jems/1060、MR 4269420 
4. Salassa, F.; Dragotto, G.; Traetta, T.; Buratti, M.; Della Croce, F. (2019), Merging Combinatorial Design and Optimization: the Oberwolfach Problem , arXiv : 1903.12112 , Bibcode : 2019arXiv190312112S
5. Häggkvist, Roland (1985), 「サイクル分解に関する補題」Cycles in graphs (Burnaby, BC, 1982) , North-Holland Math. Stud., vol. 115, Amsterdam: North-Holland, pp.  227– 232, doi : 10.1016/S0304-0208(08)73015-9 , ISBN 978-0-444-87803-8、MR  0821524
6. アルスパッハ、ブライアン；ヘッグクヴィスト、ローランド（1985）「オーバーヴォルフアッハ問題に関するいくつかの観察」、グラフ理論ジャーナル、9（1）：177–187、doi：10.1002/jgt.3190090114、MR 0785659 
7. アルスパッハ、ブライアン；シェレンバーグ、PJ；スティンソン、DR；ワグナー、デイヴィッド（1989）「オーバーヴォルフアッハ問題と一様奇数長サイクルの因子」、Journal of Combinatorial Theory、シリーズA、52（1）：20– 43、doi：10.1016/0097-3165（89）90059-9、MR 1008157 
8. Hoffman, DG; Schellenberg, PJ (1991)、「の-因数分解の存在」、離散数学、97 ( 1– 3): 243– 250、doi : 10.1016/0012-365X(91)90440-D、MR 1140806${\displaystyle C_{k}}$ ${\displaystyle K_{2n}-F}$  
9. ブライアント、ダリン; ダンジガー、ピーター (2011)、「の二部2因数分解とオーバーヴォルフアッハ問題について」(PDF)、グラフ理論ジャーナル、68 (1): 22– 37、doi : 10.1002/jgt.20538、MR 2833961${\displaystyle K_{n}-I}$  
10. Deza, A.; Franek, F.; Hua, W.; Meszka, M.; Rosa, A. (2010)、「18次から40次のオーバーヴォルフアッハ問題の解法」(PDF)、Journal of Combinatorial Mathematics and Combinatorial Computing、74 : 95–102、MR 2675892 
11. ブライアント、ダリン; シャラシュキン、ビクター (2009)、「無限順序集合に対するオーバーヴォルフアッハ問題の完全解」、Journal of Combinatorial Theory、シリーズB、99 (6): 904– 918、doi : 10.1016/j.jctb.2009.03.003、MR 2558441 
12. Alspach, Brian ; Bryant, Darryn ; Horsley, Daniel ; Maenhaut, Barbara ; Scharaschkin, Victor (2016) 「完全グラフの循環グラフへの因数分解とオーバーヴォルフアッハ問題について」 Ars Mathematica Contemporanea , 11 (1): 157– 173, arXiv : 1411.6047 , doi : 10.26493/1855-3974.770.150 , MR 3546656 
13. Traetta, Tommaso (2013)、「2表オーバーヴォルフアッハ問題の完全解」、Journal of Combinatorial Theory、シリーズA、120 (5): 984– 997、doi : 10.1016/j.jcta.2013.01.003、MR 3033656 
14. Kühn, D. ; Osthus, D. (2021)、「グラフとハイパーグラフの分解問題の極限的側面」、Lo, A.; Mycroft, R.; Perarnau, G.; Treglown, A. (編)、『組合せ論サーベイ 2021』、ロンドン数学会講義ノートシリーズ、第470巻、ケンブリッジ：ケンブリッジ大学出版局、pp.  279– 315、doi : 10.1017/9781108999737.009 (2026年1月31日現在休止)、ISBN 9781009036214