セレセダの推測

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

退化したグラフの2 つの -色付けはすべて、一度に 1 つの頂点の色を変更する 2 乗個のステップによって相互に変換できますか?${\displaystyle (d+2)}$${\displaystyle d}$

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

グラフ彩色の数学において、セレセダ予想は、疎グラフの彩色のペア間の距離に関する未解決の問題である。これは、退化度 dのグラフの 2 つの異なる彩色(どちらも最大d + 2色を使用) について、グラフのサイズの 2 乗のステップ数を使用して、一度に 1 つの頂点の色を変更することで、一方の彩色をもう一方の彩色に再構成できるはずだというものである。この予想は、2007 年の博士論文でこれを定式化したルイス・セレセダにちなんで名付けられた。

無向グラフGの退化とは、 Gの空でない部分グラフのすべてに次数が最大dの頂点が少なくとも 1 つ存在するような最小の数d のことである。G から次数が最小の頂点を繰り返し削除して頂点がなくなると、削除時点での頂点の次数のうち最大のものはちょうどdになり、この繰り返し削除法を使用して線形時間で任意のグラフの退化を計算できる。この削除順序の逆順に頂点を貪欲に彩色すると、最大d + 1色の彩色が自動的に生成され、一部のグラフ (完全グラフや奇数長サイクルグラフなど) ではこの色数が最適です。^[1]

d + 1色の彩色では、頂点の色を 1 つずつ変更して、ある彩色から別の彩色に移動できない場合があります。特に、フォレストの 2 彩色(退化 1 のグラフ) 間や完全グラフの( d + 1)彩色間でこの方法で移動することは決してできません。これらの彩色は凍結されていると言われています。^[2]長さが 4 以外のサイクル グラフにも、分離した( d + 1)彩色の族があります。^{[3]ただし、} d + 2色 の彩色を使用して 1 色追加すると、このタイプの移動のシーケンスによってすべての彩色のペアを互いに接続できます。このことから、このタイプの移動を使用して( d + 2)彩色の空間上で適切に設計されたランダム ウォークは混合であることがわかります。これは、ランダムウォークが最終的にこれらの色付け上の離散一様分布に定常状態として収束し、すべての色付けが選択される確率が等しくなることを意味します。より正確には、ランダムウォークは、一様ランダムな頂点を繰り返し選択し、その頂点にすでにある色を含むすべての利用可能な色の中から一様ランダムに選択することによって進行します。このプロセスはグラウバーダイナミクスと呼ばれます。^[4]

グラウバー動力学が( d + 2) -彩色上で一様分布に収束するという事実は、当然、それがどれだけ速く収束するかという疑問を生じさせる。つまり、混合時間はどれくらいか？混合時間の下限は、彩色空間の直径、つまり、（彩色のペア全体にわたって）ペアの一方の彩色を他方の彩色に変更するために必要なステップ数の最大値である。直径がグラフの頂点数nに対して指数的に大きい場合、彩色上のグラウバー動力学は確かに急速に混合していない。一方、直径がnの多項式関数によって制限される場合、これは混合時間も多項式である可能性があることを示唆している。2007 年の博士論文で、Cereceda はこの問題を調査し、（色の空間の連結成分であっても） d -退化したグラフの( d + 1) -彩色では直径が指数的になる可能性があることを発見した。一方、彼は、少なくとも2 d + 1色を使用する色付けの場合、色空間の直径はせいぜい 2 次式 (または、大文字の O 表記ではO ( n ² ) ) であることを証明しました。彼は、直径がこれらの 2 つの極端な値の間の色の数に対して多項式であるかどうか、または「おそらく 2 次式である」かどうかは「まだ決定されていない」と書いています。^[5]

セレセダはこの質問を色の範囲について尋ね、予想として表現しなかったが、2018年までにこの問題の形式はセレセダの予想として知られるようになった。この証明されていない仮説は、セレセダが提起した質問の中で最も楽観的な可能性である。つまり、最大でdの退化を持つグラフと、これらのグラフの( d + 2) ^-彩色の場合、彩色の空間の直径はO ( n2 )である。^{[6] [7] [8] [9]これが本当なら、}パスグラフ の3-彩色の空間は直径が2乗であるため、これが最も可能性の高いものとなる。^[10]

セレセダの予想自体は退化d = 2 の場合でも未解決のままであるが、任意の固定されたdの値に対して( d + 2) -彩色の空間の直径は多項式である（異なるdの値に対しては異なる多項式を持つ）ことが知られている。より正確には、直径はO ( n ^{d + 1} )である。色の数が少なくとも(3 d + 3)/2のとき、直径は2乗である。^[7]

関連する疑問として、色の数がd + 2より大きい場合、色彩空間の直径が2次から1次へと減少する可能性があるということがある。^[7] Bousquet & Bartier (2019)は、色の数が少なくともd + 3である場合、これが当てはまる可能性があると示唆している。^[9]

グラウバーダイナミクスは、グラフの色を互いに入れ替える唯一の方法ではありません。代替案としては、ケンペチェーンの色を繰り返し見つけて交換するケンペダイナミクス^[8]や、隣接する頂点のペアとそのペアの有効な再着色を選択する「ヒートバス」ダイナミクスなどがあります。これらの両方の種類の動きには、グラウバーの1頂点の動きが特別なケースとして含まれます。1つの頂点の色を変更することは、その1つの頂点のみを含むケンペチェーンの色を交換することと同じだからです。これらの動きは、より強い混合特性と、着色空間の直径がより小さい場合があります。たとえば、ケンペダイナミクスとヒートバスダイナミクスはどちらも、サイクルグラフの3色で急速に混合しますが、グラウバーダイナミクスは、サイクルの長さが4でない場合は接続されていません。