ラドグラフ

アッカーマン (1937)とラドー (1964)によって番号が付けられたラドー グラフ。

数学のグラフ理論分野において、ラドグラフ、エルデシュ・レーニグラフ、あるいはランダムグラフとは、各頂点のペアについて、それらの頂点を辺で結ぶかどうかを独立にランダムに選択することによって（確率1で）構築できる可算無限グラフである。このグラフの名前は、 1960年代初頭にこのグラフを研究した数学者、リチャード・ラド、ポール・エルデシュ、アルフレッド・レーニにちなんで付けられている。このグラフは、さらに古く、ヴィルヘルム・アッカーマン （1937 ）の研究にも登場している。ラドグラフは、頂点が遺伝的に有限な集合（要素が遺伝的に有限である有限集合）で辺が集合のメンバーシップを表すグラフとして、頂点が自然数で辺が 2 つの数値のうち小さい方をもう一方の数値の 2進表現のインデックスとして使用するBIT 述語によって指定されるグラフとして、または 1 つの数値が別の数値を法とする平方数である場合に辺で接続される特定の素数のグラフとして、非ランダムに構築することもできます。

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

ラドグラフは高い対称性を持つ。その有限誘導部分グラフの任意の同型性は、グラフ全体の対称性に拡張できる。ラドグラフに真となる一階述語論理文は、ほぼすべてのランダム有限グラフにも真であり、ラドグラフに偽となる文は、ほぼすべての有限グラフにも偽である。モデル理論において、ラドグラフはω-カテゴリカル理論の唯一の可算モデルの例である。

歴史

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

建設

2進数

アッカーマン (1937)とラドー (1964) は、BIT 述語を用いてラドーグラフを次のように構築した。彼らはグラフの頂点を自然数0、1、2、…で識別した。 のバイナリ表現の 番目のビットが 0 以外の場合、グラフ ( )内の頂点と を辺が接続する。したがって、たとえば、頂点 0 の近傍はすべて奇数番号の頂点で構成される。これは、0 番目のビットが 0 以外の数がちょうど奇数であるためである。頂点 1 には、1 が奇数であり、頂点 0 がすべての奇数頂点に接続されているため、頂点 0 という小さい近傍が 1 つある。頂点 1 の大きい近傍はすべて、2 または 3 を法として 4 と同値となる数を持つ頂点である。これは、それらの数がちょうど、インデックス 1 に 0 以外のビットを持つ数であるためである。^{[ 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年のオリジナルの構成の一つでは、ラドグラフの頂点は遺伝的有限集合でインデックス付けされる。遺伝的有限集合は、要素が遺伝的有限集合である有限集合として再帰的に定義され、有限レベルの再帰のみを許す。2つの頂点の間には、対応する有限集合の一方が他方のメンバーである場合にのみ辺が存在します。この構成は、遺伝的有限集合を2進数としてアッカーマン符号化した場合のBIT述語構成と等価です。同様の構成は、スコレムのパラドックス、すなわち一階集合論の可算モデルが存在するという事実に基づくことができます。このようなモデルからラドグラフを構成するには、各集合に頂点を作成し、一方の集合がもう一方の集合のメンバーである集合の各ペアを辺で接続します。^{[ 5 ]}

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

ラドグラフの別の構成は、整数を頂点とし、距離（差の絶対値）が特定の集合に属する2つの整数の間に辺を持つ無限循環グラフであることを示す。このようにラドグラフを構成するには、 をランダムに選択するか、の指示関数をすべての有限2進数列の連結として選択する。^{[ 7 ]}${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

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

プロパティ

拡大

ラドグラフの拡張性：2つの互いに素な有限頂点集合とに対して、その中のすべての頂点に接続され、その中のどの頂点にも接続されない別の頂点が存在する。${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle V}$

ラドグラフは、次の拡張プロパティを満たします。 と のすべての互いに素な有限頂点集合に対して、両方の集合の外側に、 のすべての頂点に接続されているが、 には隣接頂点を持たない頂点が存在する。^{[ 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進数構築、およびペイリーグラフ構築によって構築されるグラフはすべて拡大特性を持つ可算グラフであるため、この議論はそれらがすべて互いに同型であることを示している。^{[ 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}}$

モデル理論と0-1法則

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

その他のモデル理論的特性

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

ラドグラフ理論は、独立性を持つ理論の典型的な例であり、安定していない単純な理論の例でもある。^{[ 35 ]}

関連概念

ラドグラフは誘導部分グラフに対しては普遍的であるが、グラフの等長埋め込みに対しては普遍的ではない。等長埋め込みとは、距離を保存するグラフ同型性である。ラドグラフの直径は2であるため、より大きな直径を持つグラフは、ラドグラフに等長的に埋め込まれない。モス（1989、1991 ）は、等長埋め込みのための普遍グラフの族を記述しており、これは有限グラフの直径それぞれに対応する。この族の中で直径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}}$

注記

1. アッカーマン（1937）；ラドー（1964） .
2. Cameron (1997)の「事実1」とその証明を参照。
3. エルデシュ＆レーニ（1963）。
4. キャメロン（1997）、命題5。
5. Cameron (1997)、定理2。
6. キャメロン（1997年、2001年）
7. Cameron (1997)、セクション1.2。
8. ホースリー、パイク、サナエイ（2011）
9. ホッジス（1997）、350ページ。
10. 本質的に同じ構成が、2進数ではなく集合論的な用語で記述され、 Cameron (1997)の定理2として与えられている。
11. キャメロン（1997）、命題6。
12. キャメロン（2001） .
13. キャメロン（1997）、事実2。
14. Cameron (1997)、第1.8節：自己同型群。
15. フルショフスキー（1992）
16. Macpherson (2011)、セクション5.2および5.3。
17. ヘンソン（1971） .
18. Cameron (1997)、セクション1.3：破壊不能性。
19. キャメロン (1990) ;ディーゼルら。 (2007)。
20. Pouzet & Sauer (1996) .
21. ザウアー（2006）
22. ドブリンネン（2023）
23. スペンサー（2001）、第1.2節、「第一階理論とは何か？」、 15～17ページ。
24. 例えば、 Grandjean (1983)、p. 4 を参照。 184.
25. Spencer (2001)、セクション1.3、「拡張ステートメントとルート付きグラフ」、 pp.17–18。
26. Gaifman (1964) ; Marker (2002)、定理2.4.2、p.50。
27. ウォシュ (1954) ;ヴォート (1954) ;エンダートン (1972)、 p. 147 .
28. Marker (2002)、定理2.2.6、p.42。
29. Fagin (1976) ; Marker (2002)、定理2.4.4、pp.51–52。
30. グランジャン (1983) .
31. Macpherson (2011)、定理2.1.3、例2.2.1。
32. Macpherson (2011)、系3.1.3、命題3.1.6。
33. Rothmaler (2000)、定理13.3.1、定理13.2.1。
34. McNulty (2016)、p.71およびp.75。
35. ボールドウィン（2018）
36. ラクラン＆ウッドロー（1980）。
37. Cherlin (2011)、事実1.3

参考文献

• Ackermann、Wilhelm (1937)、「Die Widerspruchsfreiheit der allgemeinen Mengenlehre」、Mathematische Annalen、114 (1): 305–315、doi : 10.1007/BF01594179、S2CID  120576556
• ボナト、アンソニー；キャメロン、ピーター；デリッチ、デヤン（2000）「ピジョンホール特性を持つトーナメントと順序」、カナダ数学速報、43（4）：397–405、doi：10.4153/CMB-2000-047-6、MR  1793941。
• ボールドウィン、ジョン・T.（2018）、モデル理論と数学実践の哲学：基礎主義のない形式化、ケンブリッジ大学出版局、doi：10.1017 / 9781316987216、ISBN 978-1-107-18921-8、MR  3793636、S2CID  126311148。
• キャメロン、ピーター・J.（1990）、Oligomorphic permutation groups、ロンドン数学会講演ノートシリーズ、第152巻、ケンブリッジ：ケンブリッジ大学出版局、ISBN 0-521-38836-8、MR  1066691。
• キャメロン, ピーター J. (1997)、「ランダムグラフ」、ポール・エルデシュの数学 II、アルゴリズムと組合せ論、第14巻、ベルリン: シュプリンガー、pp.  333– 351、arXiv : 1301.7544、Bibcode : 2013arXiv1301.7544C、MR  1425227。
• キャメロン, ピーター J. (2001)、「ランダムグラフの再考」(PDF)、ヨーロッパ数学会議、第1巻 (バルセロナ、2000年)、Progr. Math.、第201巻、バーゼル: Birkhäuser、pp.  267– 274、doi : 10.1007/978-3-0348-8268-2_15、MR  1905324。
• チャーリン、グレゴリー（2011）、「禁制部分構造と組み合わせ二分法：WQOと普遍性」、離散数学、311（15）：1543–1584、doi：10.1016/j.disc.2011.03.014、MR  2800977。
• Diestel, Reinhard; Leader, Imre ; Scott, Alex; Thomassé, Stéphan (2007)「ラドグラフの分割と配向」アメリカ数学会誌、359 (5): 2395– 2405, doi : 10.1090/S0002-9947-06-04086-4 , MR  2276626。
• ドブリンネン、ナターシャ（2023）「均質構造のラムゼー理論：現在の動向と未解決問題」、ICM—国際数学者会議。第3巻、セクション1–4、ベルリン：EMS Pres、pp.  1462– 1486、arXiv：2110.00655、ISBN 978-3-98547-061-7、MR  4680287。
• エンダートン、ハーバート・B.（1972）『論理学への数学的入門』、アカデミック・プレス、ニューヨーク・ロンドン、MR  0337470。
• エルデシュ、P. ; Rényi, A. (1963)、「非対称グラフ」、Acta Mathematica Academiae Scientiarum Hungaricae、14 ( 3–4 ): 295–315、doi : 10.1007/BF01895716、MR  0156334。
• Fagin, Ronald (1976)、「有限モデル上の確率」(PDF)、The Journal of Symbolic Logic、41 (1): 50– 58、doi : 10.1017/s0022481200051756、JSTOR  2272945、MR  0476480、S2CID  2563318 、 2016年3月4日にオリジナル(PDF)からアーカイブ、 2014年9月5日取得。
• ガイフマン、ハイム（1964）、「第一階計算における測度について」、イスラエル数学ジャーナル、2：1-18、doi：10.1007/BF02759729、MR  0175755。
• グランジャン、エティエンヌ（1983）「ほぼすべての有限構造の第一階理論の複雑性」、情報制御、57（2-3）：180-204、doi：10.1016/S0019-9958（83）80043-6、MR  0742707。
• ヘンソン、C. ワード (1971)、「可算同次グラフの族」、パシフィック・ジャーナル・オブ・マスマティクス、38 : 69–83、doi : 10.2140/pjm.1971.38.69、MR0304242 。
• ホッジス、ウィルフリッド（1997年）、『A Shorter Model Theory』、ケンブリッジ大学出版局、ISBN 0-521-58713-1、OCLC  468298248
• ホースリー、ダニエル; パイク、デイビッド・A.; サナエイ、アシエ (2011)、「無限ブロックサイズを持つ無限デザインのブロック交差グラフの存在閉包」、Journal of Combinatorial Designs、19 (4): 317– 327、doi : 10.1002/jcd.20283、MR  2838911、S2CID  120707836。
• フルショフスキー、エフード（1992）、「グラフの部分同型性の拡張」、コンビナトリカ、12（4）：411-416、doi：10.1007/BF01305233、MR  1194731、S2CID  19939702。
• Lachlan, AH; Woodrow, Robert E. (1980)、「可算超同質無向グラフ」、アメリカ数学会誌、262 (1): 51– 94、doi : 10.2307/1999974、JSTOR  1999974、MR  0583847。
• Łoś, J. (1954), 「初等演繹体系の力の圏論性といくつかの関連問題について」, Colloquium Math. , 3 : 58– 62, doi : 10.4064/cm-3-1-58-62 , MR  0061561。
• マクファーソン、ダガルド（2011）、「均質構造の概観」、離散数学、311（15）：1599–1634、doi：10.1016/j.disc.2011.01.024、MR  2800979。
• マーカー、デイヴィッド（2002）、モデル理論、Graduate Texts in Mathematics、第217巻、Springer-Verlag、ニューヨーク、ISBN 0-387-98760-6、MR  1924282。
• McNulty, George F. (2016),初等モデル理論(PDF)、pp.  71– 75 、 2023年4月5日閲覧。。
• モス、ローレンス S. (1989)、「ユニバーサル グラフの存在と非存在」、Polska Akademia Nauk。 Fundamenta Mathematicae、133 (1): 25–37、doi : 10.4064/fm-133-1-25-37、MR  1059159。
• モス、ローレンス・S. (1991)、「有限直径固定のユニバーサルグラフ」『グラフ理論、組合せ論、および応用』第2巻（ミシガン州カラマズー、1988年）、Wiley-Intersci. Publ.、ニューヨーク：Wiley、pp.  923– 937、MR  1170834。
• Pouzet, Maurice; Sauer, Norbert (1996), 「Radoグラフの辺分割」, Combinatorica , 16 (4): 505– 520, doi : 10.1007/BF01271269 , MR  1433638 , S2CID  206793062。
• Rado、Richard (1964)、「ユニバーサル グラフとユニバーサル関数」(PDF)、Acta Arith。、9 (4): 331–340、土井: 10.4064/aa-9-4-331-340。
• ロスマーラー、フィリップ（2000）、モデル理論入門、代数、論理、応用、第15巻、ゴードン・アンド・ブリーチ・サイエンス・パブリッシャーズ、ISBN 90-5699-287-2、MR  1800596。
• Sauer, Norbert (2006)、「Radoグラフの部分グラフの色付け」、Combinatorica、26 (2): 231– 253、doi : 10.1007/s00493-006-0015-0、MR  2223636、S2CID  19251747。
• シェラ、サハロン（1984）「CHのインスタンスを持たない普遍グラフについて」、純粋・応用論理学会誌、26（1）：75-87、doi：10.1016/0168-0072（84）90042-3、MR  0739914。
• シェラ、サハロン（1990）、「CHインスタンスのないユニバーサルグラフ：再考」、イスラエル数学ジャーナル、70（1）：69-81、doi：10.1007/BF02807219、MR  1057268。
• スペンサー、ジョエル（2001）「ランダムグラフの奇妙な論理」、アルゴリズムと組合せ論、第22巻、シュプリンガー・フェアラーク、ベルリン、doi：10.1007 / 978-3-662-04538-1、ISBN 3-540-41654-4、MR  1847951、S2CID  118026950。
• トラス, JK (1985)、「可算普遍グラフの群」、ケンブリッジ哲学協会数学紀要、98 (2): 213– 245、Bibcode : 1985MPCPS..98..213T、doi : 10.1017/S0305004100063428、MR  0795890、S2CID  122772888。
• Vaught, Robert L. (1954)、「レーヴェンハイム・スコーレム・タルスキ定理の完全性と決定可能性の問題への応用」、Indagationes Mathematicae、16 : 467– 472、doi : 10.1016/S1385-7258(54)50058-2、MR  0063993。