ラドグラフ

数学のグラフ理論の分野において、ラドグラフ、エルデシュ-レーニグラフ、あるいはランダムグラフは、各頂点の組について頂点を辺で結ぶかどうかを独立にランダムに選択することによって（確率 1で）構築できる可算無限グラフである。このグラフの名前は、1960 年代初頭にこのグラフを研究した数学者、リチャード・ラド、ポール・エルデシュ、およびアルフレッド・レーニにちなんで付けられたものである。このグラフはさらに古く、ヴィルヘルム・アッカーマン(1937)の研究にも登場している。ラドグラフは、遺伝的有限集合 の帰属関係を対称化することや、自然数の2 進表現にBIT 述語を適用すること、または互いに法を法とする平方剰余である 1 mod 4 に合同な素数の組を接続する辺を持つ無限ペイリーグラフとして、非ランダムに構築することもできる。

すべての有限または可算無限グラフは、ラド グラフの誘導サブグラフであり、頂点を 1 つずつサブグラフを構築する貪欲アルゴリズムによって誘導サブグラフとして見つけることができます。ラド グラフは、可算グラフの中で、このアルゴリズムの正しさを保証する拡張プロパティによって一意に定義されます。つまり、どの頂点が誘導サブグラフの一部を形成するためにすでに選択されているかに関係なく、またサブグラフをもう 1 つの頂点で拡張するために必要な隣接パターンに関係なく、貪欲アルゴリズムが選択できる隣接パターンを持つ別の頂点が常に存在します。

ラドグラフは対称性が非常に高い。つまり、その有限誘導サブグラフの同型性は、グラフ全体の対称性に拡張できる。ラドグラフに当てはまる一階論理文は、ほぼすべてのランダム有限グラフにも当てはまり、ラドグラフに当てはまらない文は、ほぼすべての有限グラフにも当てはまらない。モデル理論では、ラドグラフはωカテゴリカル理論の唯一の可算モデルの例である。

ラドグラフは、頂点が遺伝的有限集合または自然数である 2 つの方法で、アッカーマン (1937) によって最初に構築されました。(厳密に言えば、アッカーマンは有向グラフ を記述し、ラドグラフは、辺の方向を忘れることによって与えられる、対応する無向グラフです。) エルデシュとレーニ (1963) は、ラドグラフを可算数の点上のランダムグラフとして構築しました。彼らは、ラドグラフには無限個の自己同型があることを証明し、明示的には言及していませんが、その議論はラドグラフが一意であることも示しています。リチャード・ラド (1964) は、ラドグラフを普遍グラフとして再発見し、自然数を頂点集合とする明示的な構築を与えました。ラドの構築は、本質的にアッカーマンの構築の 1 つに相当します。

アッカーマン (1937) とラドー (1964) は、BIT 述語を使用して次のようにラドー グラフを構築しました。彼らは、グラフの頂点を自然数0、1、2、...で識別しました。のバイナリ表現の 番目のビットが非ゼロの場合、グラフ ( )内の頂点とを辺が接続します。したがって、たとえば、頂点 0 の隣接頂点はすべて奇数頂点で構成されます。これは、0 番目のビットが非ゼロである数がまさに奇数であるためです。頂点 1 には、1 が奇数であり、頂点 0 がすべての奇数頂点に接続されているため、頂点 0 という 1 つの小さい隣接頂点があります。頂点 1 の大きい隣接頂点はすべて、2 または 3 を法として 4 に一致する数を持つ頂点です。これは、それらがインデックス 1 に非ゼロ ビットを持つ数とまったく同じであるためです。^[1]${\displaystyle x}$${\displaystyle y}$${\displaystyle x<y}$${\displaystyle x}$${\displaystyle y}$

ラドグラフは、可算数の頂点を持つランダムグラフのエルデシュ・レーニモデルでほぼ確実に発生します。具体的には、各頂点ペアに対して独立に、確率 1/2 で 2 つの頂点を辺で接続するかどうかを選択することで、無限グラフを形成できます。確率 1 で、結果として得られるグラフはラドグラフと同型になります。この構成は、1/2 の代わりに 0 または 1 以外の任意の固定確率を使用した場合にも機能します。^[2]${\displaystyle p}$

ポール・エルデシュとアルフレッド・レーニ （1963）によって示されたこの結果は、ラドグラフの一般的な別名「ランダムグラフ」の定冠詞を正当化するものである。エルデシュ・レーニモデルから有限グラフを繰り返し描くと、一般的には異なるグラフが得られる。しかし、可算無限グラフに適用すると、モデルはほぼ常に同じ無限グラフを生成する。^[3]

このようにランダムに生成されたグラフは、すべての選択を逆にすることで同時に補グラフを得ることができます。つまり、最初のグラフに同じエッジが含まれていなかった場合にそのエッジを含め、その逆も行います。この補グラフの構築は、各エッジを含めるかどうかをランダムかつ独立して選択する同じプロセスの例であるため、（確率 1 で）ラドグラフも生成します。したがって、ラドグラフは自己補グラフです。^[4]

アッカーマンの1937年のオリジナルの構成の1つでは、ラドグラフの頂点は遺伝的に有限な集合によってインデックス付けされ、対応する有限集合の1つがもう1つのメンバーであるときにのみ、2つの頂点の間に辺が存在する。同様の構成は、スコーレムのパラドックス、つまり集合の1階理論の可算モデルが存在するという事実に基づくことができる。このようなモデルからラドグラフを構成するには、各集合の頂点を作成し、そのペアの1つの集合がもう1つの集合のメンバーである各集合のペアを接続する辺を作成する。^[5]

ラドグラフは、ペイリーグラフと同様の構成で形成することもできます。つまり、グラフの頂点として1 を法として 4 に合同な素数をすべて取り、2 つの数のうちの 1 つがもう 1 つの数を法として平方剰余である場合に、2 つの頂点を辺で接続します。平方相互性と、頂点を 1 を法として 4 に合同な素数に制限することにより、これは対称関係となり、無向グラフを定義します。これはラドグラフと同型であることがわかります。^[6]

ラドグラフの別の構成は、それが無限循環グラフであり、その頂点が整数で、距離（それらの差の絶対値）が特定の集合に属する2つの整数の間に辺があることを示しています。この方法でラドグラフを構成するには、をランダムに選択するか、またはすべての有限バイナリシーケンスの連結となるようにの指示関数を選択します。^[7]${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

ラドグラフは、点の数と各ブロックのサイズが可算無限である無限ブロック設計のブロック交差グラフとして構築することもできます。^[8]また、有限グラフのクラスのフレセ限界として構築することもできます。 ^[9]

ラドグラフは、次の拡張プロパティを満たします。 と のすべての互いに素な有限頂点集合に対して、両方の集合の外側に、 のすべての頂点に接続されているが に隣接頂点を持たない頂点が存在する。^[2] たとえば、ラドグラフの2進数定義では、 とします。 すると、 の2進表現の非ゼロビットにより、はすべてに隣接します。 しかし、の2進表現には の頂点に対応する非ゼロビットがなく、は非常に大きいため、のすべての要素の 番目のビットはゼロです。したがって、は のどの頂点にも隣接しません。^[10]${\displaystyle U}$${\displaystyle V}$${\displaystyle x}$${\displaystyle U}$${\displaystyle V}$$${\displaystyle x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}.}$$${\displaystyle x}$${\displaystyle U}$${\displaystyle x}$${\displaystyle V}$${\displaystyle x}$${\displaystyle x}$${\displaystyle V}$${\displaystyle x}$${\displaystyle V}$

ラドーグラフのランダムグラフ定義では、と の和集合の外側の各頂点は、他の頂点とは独立に、拡張特性を満たす確率を持つ。選択できる頂点は無限にあり、それぞれが成功の確率が有限であるため、拡張特性を満たす頂点が存在する確率は 1 である。^[2]ペイリーグラフ定義では、任意の集合と について、中国剰余定理により、 内のすべての素数を法とする平方剰余数と 内のすべての素数を法とする非剰余数は周期的な数列を形成するため、等差数列の素数に関するディリクレの定理により、この数論グラフは拡張特性を持つ。 ^[6]${\displaystyle U}$${\displaystyle V}$${\displaystyle 1/2^{|U|+|V|}}$${\displaystyle U}$${\displaystyle V}$${\displaystyle U}$${\displaystyle V}$

拡張プロパティは、ラドグラフ内の任意の有限または可算無限グラフの同型コピーを誘導サブグラフとして構築するために使用できます。これを行うには、の頂点を順序付けし、同じ順序でラドグラフ内の の部分コピーに頂点を追加します。各ステップで、 の次の頂点は、頂点の順序付けで前の方にある の頂点の集合に隣接し、の前の頂点の残りの集合には隣接しません。拡張プロパティにより、ラドグラフには、のメンバーに対応する部分コピー内のすべての頂点に隣接し、 のメンバーに対応する部分コピー内のすべての頂点に隣接しない頂点も存在します。の部分コピーに追加すると、頂点が1つ多い、より大きな部分コピーが生成されます。^[11]${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle U}$${\displaystyle G}$${\displaystyle V}$${\displaystyle G}$${\displaystyle x}$${\displaystyle U}$${\displaystyle V}$${\displaystyle x}$${\displaystyle G}$

この方法は、 0頂点サブグラフを基本ケースとして、すべての有限または可算無限グラフがラドグラフの誘導サブグラフであるという帰納法による証明の基礎となります。 ^[11]

ラドグラフは、グラフ同型性を除いて、拡張性を持つ唯一の可算グラフです。たとえば、と を拡張性を持つ2つの可算グラフとし、と をそれぞれとの同型有限誘導サブグラフとし、 とをそれぞれとに属さない との頂点の列挙の最初の頂点とします。次に、拡張性を2回適用することで、 と を以前のサブグラフのすべての頂点と一緒に含む同型誘導サブグラフとを見つけることができます。このプロセスを繰り返すことで、最終的にと のすべての頂点を含む誘導サブグラフ間の同型性のシーケンスを構築できます。したがって、前後法により、 、、 は同型である必要があります。^[12] ランダムグラフ構築、2進数構築、および Paley グラフ構築によって構築されたグラフはすべて拡張性を持つ可算グラフであるため、この議論はそれらすべてが互いに同型であることを示しています。^[13]${\displaystyle G}$${\displaystyle H}$${\displaystyle G_{i}}$${\displaystyle H_{i}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle g_{i}}$${\displaystyle h_{i}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G_{i}}$${\displaystyle H_{i}}$${\displaystyle G_{i+1}}$${\displaystyle H_{i+1}}$${\displaystyle g_{i}}$${\displaystyle h_{i}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$

ラドグラフの任意の2つの同型有限部分グラフに前後構成を適用すると、それらの同型性がラドグラフ全体の自己同型性に拡張されます。有限部分グラフのすべての同型性がグラフ全体の自己同型性に拡張されるという事実は、ラドグラフが超同質であると言うことで表現されます。特に、隣接する頂点の任意の順序付きペアを他の任意の順序付きペアに取る自己同型性があるため、ラドグラフは対称グラフです。^[12]

ラドーグラフの自己同型群は、要素の数が連続体の濃度である単純群である。この群の、指数が連続体の濃度より小さいすべての部分群は、頂点の有限集合の点ごとの安定子を含み、さらに同じ集合の集合ごとの安定子内に含まれます。^[14]点ごとの安定子に関するステートメントは、小指数特性と呼ばれ、^[14]これを証明するには、すべての有限グラフ に対して、を誘導部分グラフとして含む有限グラフが存在し、 の誘導部分グラフ間のすべての同型が の自己同型に拡張されることを示す必要がありました。^[15]これは部分自己同型の拡張特性と呼ばれ、それ以来、小指数特性やその他の特性を示すためにさらなる構造に一般化されています。^[16]${\displaystyle X}$${\displaystyle Z}$${\displaystyle X}$${\displaystyle X}$${\displaystyle Z}$

ラドーグラフを無限巡回グラフとして構成すると、その対称群には推移的な無限巡回群を生成する自己同型が含まれることがわかる。この構成の差集合（隣接する頂点間の整数の距離の集合）は、差 1 を含むように制約することができ、この構成の正しさには影響しない。このことから、ラドーグラフには、対称性がグラフ全体の対称性のサブグループである無限ハミルトンパスが含まれることがわかる。^[17]

ラドグラフから有限個の辺や頂点を削除したり、有限個の辺を追加したりしてグラフを形成した場合、その変更はグラフの拡張特性に影響を与えません。 と の任意のペアに対して、の修正部分をに追加し、修正されていないラドグラフに拡張特性を適用することで、内のすべての要素に隣接し、 内のすべての要素に隣接しない頂点を修正グラフ内で見つけることは可能です。したがって、このタイプの有限の変更は、ラドグラフと同型のグラフをもたらします。^[18]${\displaystyle G}$${\displaystyle U}$${\displaystyle V}$${\displaystyle U}$${\displaystyle V}$${\displaystyle G}$${\displaystyle V}$

ラドグラフの頂点を 2 つの集合とに分割する場合、またはより一般的には有限個の部分集合に分割する場合、分割集合の 1 つによって誘導される部分グラフの少なくとも 1 つは、ラドグラフ全体と同型です。Cameron (2001) は、次のような短い証明を示しています。どの部分もラドグラフと同型の部分グラフを誘導しない場合は、それらはすべて拡張プロパティを持たないため、各部分グラフ内で拡張できない集合とペアを見つけることができます。しかし、その場合、集合の和集合と集合の和集合は、グラフ全体で拡張できない集合を形成し、ラドグラフの拡張プロパティと矛盾します。任意の分割の誘導された部分グラフの 1 つと同型であるというこのプロパティは、ラドグラフ、完全グラフ、および空グラフの 3 つの可算無限無向グラフによってのみ保持されます。^[19] Bonato、Cameron & Delić（2000）およびDiestelら（2007）は、同じ分割特性を持つ無限有向グラフを調査している。これらはすべて、完全グラフまたはラドグラフのエッジの方向を選択することによって形成される。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle U_{i}}$${\displaystyle V_{i}}$${\displaystyle U_{i}}$${\displaystyle V_{i}}$

関連する結果は、頂点分割ではなく辺分割に関するものである。ラドグラフの辺を有限個の集合に分割するたびに、最大で 2 色を使用するラドグラフ全体に同型なサブグラフが存在する。しかし、辺の 1 色のみを使用する同型サブグラフが必ずしも存在するとは限らない。^[20]より一般的には、すべての有限グラフに対して、ラドグラフ内ののコピーを有限個の集合に分割するたびに、最大で 色を使用するラドグラフ全体に同型な誘導サブグラフが存在するような数（ラドグラフでは の大ラムゼー次数と呼ばれる）が存在する。^{[21] [22]}${\displaystyle A}$${\displaystyle d_{A}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle d_{A}}$

フェイギン (1976) は、ラドー グラフを使用して、グラフの論理における一階述語のゼロ-一法則を証明しました。このタイプの論理ステートメントがラドー グラフに対して真または偽である場合、ほぼすべての有限グラフ に対しても真または偽になります。

グラフの第一階言語は、グラフの頂点を表す変数、全称・存在量指定子、論理接続子、頂点の等価性と隣接性を表す述語から構成される数学的論理における整形式の文の集合である。例えば、グラフに孤立した頂点が存在しないという条件は、 記号が2つの頂点の隣接関係を示す文で表現できる 。 ^[23] この文は、あるグラフでは真だが、他のグラフでは偽である。グラフはの頂点と隣接関係について が真である場合、 と書かれるをモデル化すると言われる。^[24]$${\displaystyle \forall u:\exists v:u\sim v}$$${\displaystyle \sim}$${\displaystyle S}$${\displaystyle G}$ ${\displaystyle S}$${\displaystyle G\models S}$${\displaystyle S}$${\displaystyle G}$

ラドグラフの拡張性は、集合 内の頂点と集合 内の頂点の任意の選択に対して、すべて異なる 内のすべての頂点に隣接し、 内のすべての頂点に隣接しない頂点が存在することを述べる一階文の集合によって表現される。^[25]たとえば、 は次のように書くことができる 。${\displaystyle E_{i,j}}$${\displaystyle i}$${\displaystyle A}$${\displaystyle j}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle E_{1,1}}$$${\displaystyle \forall a:\forall b:a\neq b\rightarrow \exists c:c\neq a\wedge c\neq b\wedge c\sim a\wedge \lnot (c\sim b).}$$

ガイフマン（1964）は、文 と、隣接関係が対称かつ反反射的である（つまり、これらの文をモデル化するグラフは無向であり自己ループを持たない）ことを述べた追加の文が、完全な理論の公理であることを証明した。これは、各一階文 について、 のちょうど1つとその否定がこれらの公理から証明できることを意味する。ラドーグラフは拡張公理をモデル化するため、この理論のすべての文をモデル化する。^[26]${\displaystyle E_{i,j}}$${\displaystyle S}$${\displaystyle S}$

論理学では、与えられた無限基数 を持つモデルを 1 つだけ持つ理論 (同型性を除く) は-カテゴリカルと呼ばれます。ラド グラフが拡張特性を持つ唯一の可算グラフであるという事実は、それがその理論の唯一の可算モデルでもあることを意味します。ラド グラフのこの一意性は、ラド グラフの理論がω-カテゴリカルであると言うことで表現できます。ŁośとVaught は1954 年に、理論が(ある無限基数に対して) -カテゴリカルであり、さらに有限モデルを持たない場合、理論は完全でなければならないことを証明しました。^{[27]したがって、ラド グラフの理論が完全であるという Gaifman の定理は}、Łoś–Vaught テストによるラド グラフの一意性から導かれます。^[28]${\displaystyle \lambda}$${\displaystyle \lambda}$${\displaystyle \lambda}$${\displaystyle \lambda}$

フェイギン (1976) が証明したように、拡張公理から証明可能でラドーグラフによってモデル化される一階の文は、ほぼすべてのランダムな有限グラフに対して真となる文とまったく同じである。つまり、ラベル付き頂点上のすべてのグラフから一様にランダムに -頂点グラフを選択した場合、その文が選択されたグラフに対して真となる確率は、 が無限大に近づくにつれて極限で 1 に近づく。対称的に、ラドーグラフによってモデル化されない文は、ほぼすべてのランダムな有限グラフに対して偽である。したがって、すべての一階の文は、ランダムな有限グラフに対してほぼ常に真か、ほぼ常に偽のいずれかであり、この 2 つの可能性は、ラドーグラフが文をモデル化しているかどうかを判断することによって区別できる。フェイギンの証明では、コンパクト性定理が使用されている。^[29]この同値性に基づいて、ラドーグラフによってモデル化された文の理論は、「ランダムグラフの理論」または「グラフのほぼ確実な理論」と呼ばれている。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

この 0-1 法則により、十分に大きな の値を選択し、その文をモデル化する - 頂点グラフの数を数えることによって、任意の特定の 1 階文が Rado グラフによってモデル化されるかどうかを有限時間でテストすることができます。ただし、ここでの「十分に大きい」とは、文のサイズに対して少なくとも指数関数的であるということです。たとえば、拡張公理は- 頂点クリークの存在を意味しますが、そのサイズのクリークは、 に対して指数関数的なサイズのランダムグラフにのみ高い確率で存在します。この問題はPSPACE 完全であるため、Rado グラフが特定の文をモデル化するかどうかの判定を指数時間よりも速く実行できる可能性は低いです。[ ^30]${\displaystyle n}$${\displaystyle n}$${\displaystyle E_{k,0}}$${\displaystyle (k+1)}$${\displaystyle k}$

ラドグラフは超同次であり、したがって有限部分構造のクラス、すなわち有限グラフのクラスのフレッセ極限である。 ^[31]また、有限関係言語であることを考えると、超同次性はその理論が量化子除去を持ち、ω-カテゴリカルであることと同値である。^[32]このようにラドグラフは可算ω-カテゴリ理論の可算モデルであるため、素数であり飽和でもある。^{[33] [34]}

ラドーグラフの理論は、独立性を持つ理論と、安定ではない単純な理論の典型的な例です。^[35]

ラドグラフは誘導サブグラフに対しては普遍的であるが、グラフの等長埋め込みに対しては普遍的ではない。等長埋め込みとは、距離を保存するグラフ同型である。ラドグラフの直径は2 であるため、より大きな直径を持つグラフはこれに等長的に埋め込まれない。モス (1989、1991) は、等長埋め込みの普遍グラフの族を、可能な有限グラフ直径ごとに 1 つずつ説明しており、その族の中で直径が 2 のグラフがラドグラフである。

ヘンソングラフは、頂点クリークを含まない可算グラフ（各正の整数に対して1つ）であり、クリークのないグラフに対して普遍的である。これらはラドーグラフの誘導部分グラフとして構築することができる。^[17]ラドーグラフ、ヘンソングラフとその補グラフ、可算無限クリークとその補グラフの非隣接和、同型有限クリークとその補グラフの非隣接和は、唯一の可能な可算無限同次グラフである。^[36]${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$

ラドグラフの普遍性特性は、辺色グラフに拡張できる。つまり、辺が異なる色クラスに割り当てられているが、各色クラスが対応する を形成するという通常の辺色要件がないグラフである。有限または可算無限数の色 に対して、一意の可算無限 -辺色グラフが存在し、 -辺色有限グラフのすべての部分同型は完全同型に拡張できる。この表記法では、ラドグラフは である。Truss (1985) は、このより一般的なグラフ族の自己同型群を調査している。 ${\displaystyle \chi}$${\displaystyle \chi}$${\displaystyle G_{\chi}}$${\displaystyle \chi}$${\displaystyle G_{1}}$

ラドグラフはすべてのグラフのクラスに対して可算普遍的であるが、すべてのグラフクラスが可算普遍的グラフを持つわけではない。例えば、4サイクルをサブグラフとして除外し、他のすべての可算グラフを（必ずしも誘導されない）サブグラフとして含む可算グラフは存在しない。^[37]

飽和モデルを構築する古典的モデル理論の考察から、連続体仮説CH のもとで、連続体の頂点数が であるユニバーサル グラフが存在することがわかります。もちろん、CH のもとでは、連続体は、つまり最初の非可算基数に等しくなります。Shelah (1984、1990) は、強制法を使用して多数の頂点を持つユニバーサル グラフを調査し、CH がない場合でも、サイズ のユニバーサル グラフが存在する可能性があることを示しています。彼は、より高い基数について同様の質問も調査しています。 ${\displaystyle \aleph_{1}}$${\displaystyle \aleph_{1}}$${\displaystyle \aleph_{1}}$