漸近的振る舞い
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/02 08:43 UTC 版)
「ケージ (グラフ理論)」の記事における「漸近的振る舞い」の解説
ムーアバウンドの議論から、大きい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).} これらのグラフがケージとなることはおそらくないが、これらのグラフの存在によって上限のグラフはケージとなる必要がある。
※この「漸近的振る舞い」の解説は、「ケージ (グラフ理論)」の解説の一部です。
「漸近的振る舞い」を含む「ケージ (グラフ理論)」の記事については、「ケージ (グラフ理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「漸近的振る舞い」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 漸近的振る舞いのページへのリンク
