予想の紹介は止そう

グラフ理論に残されたconjectureを幾つか紹介します。今回の記事は open problem garden を参考にさせて頂き、面白いと感じた予想の中身と簡単なコメントのみを広く浅く紹介させて頂く形になってます。ですのでその予想を思いつくモチベーションとか重要性などは書いていませんので、気になる方は予想の名前で検索して色んな文献を調べてみてください。もし何か間違っている点がありましたらご指摘いただけると幸いです。

1. 5-flow conjecture

登場人物.

・$G=(V,E)$ : ループなしグラフ。ただし多重辺は持ちうる。

・$D$ : $E$の向き付け.

・$\phi:E \to \mathbb{Z}_{\geq 0}$

・$\phi$ が nowhere-zero であるとは、全ての辺 $e\in E$ に対し $\phi(e)\neq 0$ が成り立つことをいう。

・$(D,\phi)$ が $k$-flow であるとは、$\phi$の値域が$\{0,\ldots,k-1\}$であり, 全ての頂点$v\in V$においてキルヒホッフ則を満たすことをいう。つまり、

$$\forall v\in V, \sum_{e\in \delta^{-}(v)} \phi(e) = \sum_{e\in \delta^+ (v)} \phi(e)$$

が成り立つことをいう。ここで$\delta^{-}(v)$ と $\delta^{+}(v)$ は $v$にそれぞれ向き付け$D$において $v$ に入る辺と出る辺の集合である。

Conjecture [Tutte, 1954].

    橋を持たない任意のグラフは nowhere-zero な 5-flow を持つ。

コメント.

・橋を持つグラフならnowhere-zeroなフローはない（橋をどちらの向きにしても流量は保存されないから）。

・5ではなく6なら証明されている [Seymour, 81].

2. Cycle Double Cover Conjecture

登場人物.

・$G=(V,E)$: グラフ.

・閉路の多重集合 $[C_1,\ldots,C_m]$ が $G$の cycle double cover であるとは、$G$の全ての辺がちょうど2個の相異なる $C_i$ と $C_j$ に含まれることをいう。

Conjecture [Szekeres, 73][Seymour, 80].

橋を持たない任意のグラフは cycle double cover を持つ。

コメント.

・cycle double cover が多重集合であることには意味があります。例えば $G$ が単なる閉路の場合は多重集合じゃないと予想の反例になってしまいます。

・$G$が橋を持たない平面グラフなら、面の全体 (外面も含む）が cycle double cover になりますね。

・$G$が橋を持つなら、その橋はいかなる閉路にも含まれないので cycle double cover を持ちません。

・「この予想を証明した」と主張する論文が幾つかarXivにあがっています。

3. The Berge-Furkerson Conjecture

登場人物.

・$G$ : 橋を持たない$3$-正則グラフ.

Conjecture [Fulkerson, 71]

$G$には以下を満たす6個の完全マッチング $M_1,\ldots,M_6$ が存在する:

    全ての辺はそれぞれ$M_1,\ldots,M_6$のうちちょうど2個に含まれる。

コメント.

・$M_1,\ldots,M_6$ は相異なる必要はありません (例えば$M_1=M_2$でもokです)。

・$G$ は必ず完全マッチングを持ちます (cf. ピーターセンの定理)

・$G$ が 3-辺彩色可能なら、それぞれの色を持つ辺集合を$M_1=M_2, M_3=M_4, M_5=M_6$ とすれば構成できます。

・Fulkerson が初めて提示した予想ですが、元々 Berge がこれに似ているちょっと弱い予想をunpublishながら提示していて、それを元に Fulkerson が提示したものらしいです。

・余談ですが、橋を持たない3正則グラフで3-辺彩色可能でないもののうち最小のグラフがピーターセングラフです。ちなみに色んな予想の反例になることで有名なピーターセングラフに対してもBerge-Fulkerson conjectureは成り立ちます。実際、$M_1,\ldots,M_6$ として次が考えられます。

4. Erdős–Gyárfás Conjecture

Conjecture [Erdős, 97].

全ての次数が3以上の任意のグラフは長さが2ベキの閉路を含む.

コメント.

・示したら$100, 反例を見つけたら$50 貰えるらしい。

・3-連結かつ3-正則な平面的グラフでは成り立つ [Heckman, Krakovski, 13].

・次数2の頂点を許すと反例が簡単に構成できます。例えば

・ピーターセングラフは15頂点で長さ4の閉路を持たないのですが、長さ8の閉路を持ちます。

5. Reconstruction Conjecture.

登場人物.

・$G=(V,E)$ : 多重辺を持ちうるグラフ

・$n$頂点グラフ $G$ に対して, $D(G)$ を多重集合 $[H_1,\ldots,H_n]$ であって各 $H_i$ は $G-v_i$ と同型なラベルなしグラフ と定める。ただし $v_i$ は $G$ の $i$番目の頂点。例えば

Conjecture [Kelly, 57][Ulam, 60].

3つ以上の頂点を持つ二つのグラフ $G,H$ が $D(G)=D(H)$ を満たすならば、$G$ と $H$ は同型.

コメント

・要するに、各頂点を削除した時のグラフの形状をみれば元々のグラフ$G$の形状が復元できる、ということを主張しています。

・2頂点だと多重辺を持つグラフ同士が識別できなくなってしまいます。

・$D(G)$ は $G$ の デッキ (deck) と呼ばれます。

・[Kelly, 57] では $G$ が木である場合にreconstruction conjectureが正しいことを証明しています。

6. The Barnette Conjecture

Conjecture [Barnette, 69].

任意の3-連結, 3-正則, 二部な平面的グラフはハミルトン閉路を持つ.

コメント.

・二部という条件は本質で、二部じゃない場合は反例が [Tutte, 46] で見つかっています（二部の条件を外した時のステートメントは元々は[Tait, 1884]が予想していて、Tutteが反例を見つけたということです。詳しくは Tait's Conjecture を参照）。

・3正則平面的グラフがハミルトン閉路を持つかどうかの判定がすでにNP-completeなのでコンピュータによるチェックは大変ですが、66頂点未満のグラフはこの予想が正しいことが知られています [Holton, Manvel, McKay, 85]。100頂点未満のグラフで確認とかしたら学士論文とかになるんじゃないですかね。