ランダム正規グラフ

ランダムr -正則グラフはから選択されたグラフであり、これは頂点上のすべてのr -正則グラフの確率空間を表し、と は偶数です。^[1] したがって、これは特定の種類のランダムグラフですが、ほとんどのグラフは正則ではないため、正則性制約により が保持する特性が大幅に変わります。 ${\displaystyle {\mathcal {G}}_{n,r}}$${\displaystyle n}$${\displaystyle 3\leq r<n}$${\displaystyle nr}$

より一般的なランダムグラフと同様に、ランダム r -正則グラフの特定の特性は漸近的にほぼ確実にとなることを証明することができます。特に、 に対して、大きなサイズのランダムr -正則グラフは漸近的にほぼ確実にr -連結です。^[2]言い換えれば、連結性が 未満の r -正則グラフは存在しますが、そのようなグラフを選択する確率は が増加するにつれて 0 に近づきます。 ${\displaystyle m}$${\displaystyle r\geq 3}$${\displaystyle r}$${\displaystyle r}$${\displaystyle n}$

が正の定数で、が最小の整数である 場合、${\displaystyle \epsilon >0}$${\displaystyle d}$

${\displaystyle (r-1)^{d-1}\geq (2+\epsilon )rn\ln n}$

すると、漸近的にほぼ確実に、ランダムなr -正則グラフの直径は最大でもdになります。また、 r -正則グラフの直径には（より複雑な）下限値があり、ほとんどすべてのr -正則グラフ（同じサイズ）はほぼ同じ直径を持ちます。^[3]

短周期の数の分布も知られている。 を固定し、までの長さの周期の数を とする。すると は平均^[4]を持つ漸近的に独立したポアソン確率変数となる。${\displaystyle m\geq 3}$${\displaystyle Y_{3},Y_{4},...Y_{m}}$${\displaystyle m}$${\displaystyle Y_{i}}$

${\displaystyle \lambda _{i}={\frac {(r-1)^{i}}{2i}}}$

ほとんどのグラフは正則ではないため、 r正則グラフのランダム選択を効率的かつ偏りのない方法で実装するのは簡単ではありません。ペアリングモデル（構成モデルとも呼ばれる）は、 nr個の点を取り、それらをr個の点がそれぞれに含まれるn個のバケットに分割する方法です。nr 個の点をランダムにマッチングし、各バケットのr個の点を単一の頂点に縮小すると、r正則グラフまたはマルチグラフが生成されます。このオブジェクトに多重辺やループがない場合（つまりグラフである場合）、これが必要な結果です。そうでない場合は、再起動が必要です。^[5]

この方法の改良版はブレンダン・マッケイとニコラス・ワーマルドによって開発された。^[6]