超置換

組合せ数学における 記号の超置換（ちょうちかん、）とは、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年の時点ではで、つまり  が上界になっている。

 関連項目 

 - n個の記号の全ての置換をとして含むような置換。

 注釈 

 参考文献 

 外部リンク 
 最小超置換問題 - Nathaniel Johnstonのブログ


Category:数学に関する記事

Category:組合せ論
Category:置換
Category:4chan