ケージ (グラフ理論)
ムーアバウンドの議論から、大きいgに対して頂点数はgの指数関数的に増大する項で下から抑えられる。言い換えると、gはnの対数に比例する項で上から抑えられる。すなわち次式を得る。
g ≤ 2 log r − 1  n + O ( 1 ) . {\displaystyle g\leq 2\log _{r-1}n+O(1).}
実際この上限に近づくと予想されている(Bollobás & Szemerédi 2002)。知られている中でもっともよいgの下限は比較的小さな定数係数の対数で書けている。とくにラマヌジャングラフ(Lubotzky, Phillips & Sarnak 1988) は次式を満たす。
g ≥ 4 3 log r − 1  n + O ( 1 ) . {\displaystyle g\geq {\frac {4}{3}}\log _{r-1}n+O(1).}
これらのグラフがケージとなることはおそらくないが、これらのグラフの存在によって上限のグラフはケージとなる必要がある。
グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。
厳密に述べると次のようになる。(r,g)-グラフとは任意の頂点が相異なるr個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さがgに一致するものを指す。任意のr ≥ 2、g ≥ 3に対して(r,g)-グラフは存在することが知られている。(r,g)-ケージとは(r,g)-グラフのうちもっとも頂点数が少ないグラフのことである。
次数r、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は
1 + r ∑ i = 0 ( g − 3 ) / 2 ( r − 1 ) i {\displaystyle 1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}}
以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は
2 ∑ i = 0 ( g − 2 ) / 2 ( r − 1 ) i {\displaystyle 2\sum _{i=0}^{(g-2)/2}(r-1)^{i}}
以上となる。またrとgの組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージはバラバン10-ケージ、Harries graphとHarries-Wong graphの同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となるバラバン11-ケージのみである。