超置換

組合せ数学における記号の超置換（ちょうちかん、）とは、n個の記号の全ての置換を部分文字列（）として含む文字列。最小の超置換を求める問題は2025年時点で未解決である。

に対しては、最小の記号の超置換の長さはに等しい。つまり、順に（）である。

最小の超置換の具体的な例としては及び以下のものが挙げられる :123451234152341253412354123145231425314235142315423124531243 512431524312543121345213425134215342135421324513241532413524 132541321453214352143251432154321

においても同様の式で長さを求められると予想されていたが、それは成り立たないことが判明している。の場合、よりも短い、長さがのものがRobin Houstonによって発見されたからである。

なお、およびの場合もそれぞれ長さ、のものが確認されており、この数値が最小かどうかは未だ証明されていない。今もさらに短いものを探す試みは継続しており、においては、2019年2月1日には長さのものが、2019年2月27日には長さのものが次々と発見された。

最小超置換の長さ最小超置換の正確な長さは未だ求められていないが、答えの範囲は次のように絞り込まれている。

下界 2011年9月、4chanの匿名投稿者が記号の超置換の長さは少なくとも以上であることを証明した。この証明は4chanにおいて、アニメシリーズ『涼宮ハルヒの憂鬱』第1期全14話は2006年の放送時は物語の時系列とは異なる順序で放映されたため、エピソードをどの順序で観るのがよいのか、という疑問がきっかけになったことから、「ハルヒ問題」とも呼ばれる。この証明が大衆の関心を引いたのは、2018年10月に数学者兼計算機科学者のロビン・ヒューストンがツイートして以降である。2018年10月25日、ロビン・ヒューストン、ジェイ・パントン、ヴィンス・ヴァッターはこの証明をより洗練させたものをOEISに投稿した。

上界 2018年10月20日、グレッグ・イーガンは、アーロン・ウィリアムズが対称群のケイリーグラフのハミルトン路を構成するのに用いた方法を適用することで、長さの超置換を生成するアルゴリズムを開発した。2018年の時点で、これらはに対しては知られている中で最小の超置換である。2019年には、に対して、にあたるがよりよい上界になった。

Źródło i licencja