Radoグラフ

同義語:Rado graph可算ランダムグラフcountable random graph

概要

Radoグラフ(Rado graph)とは、互いに交わらない有限個の頂点の組 $U,V$ をどう選んでも、$U$ のすべてと隣接し $V$ のどれとも隣接しない頂点があるという拡大性をもつ可算グラフで、同型を除いてただ 1 つに定まるので $R$ と書く。可算個の頂点の各対を独立に確率 $\frac12$ で結ぶと確率 $1$ で $R$ になるので、可算ランダムグラフともよばれる。遺伝的有限集合の帰属関係、$4$ で割って $1$ 余る素数の平方剰余、普遍集合による整数の差などからも構成できる。すべての可算グラフを誘導部分グラフとして含み、有限個の頂点の除去・辺の変更・補グラフをとる操作で変わらず、頂点を有限個に分けるとどれかの部分が $R$ になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 誘導部分グラフ, 往復論法

Radoグラフ(Rado graph)とは、次の 拡大性 をもつ可算無限グラフのことである。互いに交わらない有限個の頂点 $u_1,\dots,u_m$、$v_1,\dots,v_n$ をどう選んでも、$u_1,\dots,u_m$ のすべてと隣接し、$v_1,\dots,v_n$ のどれとも隣接しない頂点 $z$ がある。拡大性をもつ可算グラフは同型を除いてただ 1 つなので、これを $R$ と書く。可算ランダムグラフ(countable random graph)ともよばれる。
この名の由来は、Erdős と Rényi が 1963 年に示した次の逆説的な事実にある。可算個の頂点の各対を、硬貨を投げて独立に確率 $\frac12$ で辺で結ぶと、得られるグラフは確率 $1$ で $R$ と同型になる(Cam13 p. 1 の Theorem 1)。でたらめに作ったはずのグラフが、確率 $1$ でただ 1 つの決まったグラフになる。Rado は翌年、2 進法による具体的な構成を与えた(同 p. 3)。
この記事では、$R$ が作り方によらず現れること(thm-rado-random、thm-rado-constructions)、有限個の頂点や辺をいじっても $R$ のままであること(prop-rado-robust)、頂点を有限個に分けるとどれかの部分が $R$ になり、この性質が $R$ と完全グラフ・空グラフを特徴づけること(thm-rado-pigeonhole)を証明する。

結果内容この記事での扱い
thm-rado-unique存在と一意性、均質性往復論法 の証明を引用
thm-rado-random無作為な可算グラフは確率 $1$ で $R$証明する
thm-rado-constructions集合の帰属・平方剰余・差による構成証明する
prop-rado-robust有限の変更に対する安定性証明する
thm-rado-pigeonhole鳩の巣性とその特徴づけ証明する
rem-rado-aut自己同型群の性質主張だけ

定義と一意性

グラフはループも多重辺もない単純グラフとし、頂点の集合も同じ記号で書く。グラフ $\Gamma$ の頂点 $z$ が、互いに交わらない有限集合 $U,V$ に対して 正しくつながる とは、$z\notin U\cup V$ で、$z$ が $U$ のすべての頂点と隣接し、$V$ のどの頂点とも隣接しないことをいう。

拡大性

グラフ $\Gamma$ が 拡大性(extension property)をもつとは、互いに交わらない任意の有限集合 $U,V\subset\Gamma$ について、$U,V$ に正しくつながる頂点があることをいう。拡大性をもつ可算グラフを Rado グラフ という。

拡大性は文献によって拡張性ともよばれ、一階の文の列(拡大公理)で表せる(有限モデル理論 の定義「拡大公理」)。拡大性をもつグラフは無限である。有限なら $U$ を頂点全体、$V=\emptyset$ とすると、外に頂点がないからである。

存在・一意性・均質性
  1. Rado グラフは存在する。
  2. Rado グラフ $\Gamma_1,\Gamma_2$ の有限個の頂点の間の部分同型(誘導部分グラフの間の同型)は、同型 $\Gamma_1\to\Gamma_2$ に延びる。とくに Rado グラフは同型を除いてただ 1 つで、$R$ の有限の誘導部分グラフの間の同型はすべて $R$ の自己同型に延びる($R$ は 均質 である)。
  3. すべての可算グラフ(有限でもよい)は $R$ の誘導部分グラフと同型である。
証明の所在

1 と 2 の証明は 往復論法 の定理「拡張性をもつ可算なグラフ」にある。部分同型を、片方の拡大性で前へ、もう片方の拡大性で後ろへ 1 点ずつ延ばし、両方の頂点を番号順に使い尽くす。3 は前へ延ばすだけで足り、無限グラフ の定理「可算グラフの普遍性」にある(Cam13 p. 2、p. 6 の Proposition 6、p. 7 の Proposition 9)。存在は、無限グラフ の定義「拡大性と 2 進法によるグラフ」の 2 進法のグラフでも、次の thm-rado-random でも示せる。

均質性から、$R$ の自己同型群は頂点の集合、辺の集合、辺でない 2 点の組の集合のそれぞれに推移的に働く。

無作為な可算グラフ

Erdős–Rényi の定理

$\mathbb N$ を頂点集合とし、各対 $\{x,y\}$ を辺にするかを互いに独立に決め、その確率 $p_{xy}$ がある $\varepsilon>0$ について $\varepsilon\le p_{xy}\le1-\varepsilon$ を満たすとする。このとき、得られる無作為なグラフは確率 $1$ で拡大性をもち、したがって確率 $1$ で $R$ と同型である。とくに $p_{xy}=p$($0< p< 1$)の場合にそうである。

可算個の零集合の和は零集合

互いに交わらない有限集合 $U,V\subset\mathbb N$ の組 $(U,V)$ は可算個しかないので、各組について「$U,V$ に正しくつながる頂点がない」事象 $F_{U,V}$ の確率が $0$ であることを示せば、その可算和も確率 $0$ である(確率の可算劣加法性)。
$|U|=m$、$|V|=n$ とし、$U\cup V$ に属さない頂点 $z_1,z_2,\dots$ をとる。$z_i$ が正しくつながるかどうかは、$z_i$ と $U\cup V$ を結ぶ $m+n$ 個の対だけで決まるので、$i$ ごとに独立であり、
$$ P(z_i\text{ が正しくつながる})=\prod_{u\in U}p_{z_iu}\prod_{v\in V}(1-p_{z_iv})\ge\varepsilon^{m+n} $$
である。よって、すべての $N$ について
$$ P(F_{U,V})\le P(z_1,\dots,z_N\text{ のどれも正しくつながらない})\le\bigl(1-\varepsilon^{m+n}\bigr)^N $$
で、$N\to\infty$ とすると $P(F_{U,V})=0$ である。拡大性をもつ可算グラフは thm-rado-unique の 2 により $R$ と同型である。$\square$

この証明は Rado グラフが存在することの確率論的な証明にもなっている。$p=\frac12$ の場合が Erdős と Rényi の定理で、確率 $p$ を一定にしなくてもよいことは Cam13 p. 2 にも注意がある。有限のグラフについては、$G(n,\frac12)$ の拡大公理の確率の同じ評価から、一階の文が成り立つ確率が $0$ か $1$ に近づく 0-1 法則 が導かれ、極限が $1$ になるのは $R$ でその文が成り立つときである(有限モデル理論 の定理「グラフの 0-1 法則」、Cam13 p. 10 の Theorem 6)。
拡大性を確かめるときは、次の言い換えが便利である。

正しくつながる頂点は無限にあり、$R$ をなす

$R$ の互いに交わらない有限集合 $U,V$ について、$U,V$ に正しくつながる頂点の集合 $Z$ は無限集合で、$Z$ が誘導する部分グラフは $R$ と同型である。

$Z$ が拡大性をもつことを示せば、$Z$ は無限で、可算なので thm-rado-unique の 2 により $R$ と同型である。$U',V'\subset Z$ を互いに交わらない有限集合とする。$R$ の拡大性により、$U\cup U'$ のすべてと隣接し $V\cup V'$ のどれとも隣接しない頂点 $z\notin U\cup U'\cup V\cup V'$ がある($U\cup U'$ と $V\cup V'$ は交わらない。$Z$ は $U\cup V$ と交わらないからである)。$z$ は $U,V$ に正しくつながるので $z\in Z$ で、$Z$ の中で $U',V'$ に正しくつながる。$\square$

いろいろな構成

$R$ の 3 つの構成

次のグラフはどれも $R$ と同型である。

  1. 遺伝的有限集合. 遺伝的有限集合(空集合から有限集合をとる操作を有限回繰り返して得られる集合)の全体 $V_\omega$ を頂点とし、$x\in y$ または $y\in x$ のとき $x,y$ を結ぶ。
  2. 平方剰余. $4$ で割って $1$ 余る素数の全体を頂点とし、$p$ が $q$ を法として平方剰余のとき $p,q$ を結ぶ。
  3. 差のグラフ. $S$ を正の整数の集合で、すべての $k\ge1$ と $T\subset\{1,\dots,k\}$ について、$N+i\in S\iff i\in T$($1\le i\le k$)となる $N\ge0$ があるもの(普遍集合)とする。$\mathbb Z$ を頂点とし、$|x-y|\in S$ のとき $x,y$ を結ぶ。
正しくつながる頂点を書き下す

どれも可算なので、拡大性を示せばよい。$U=\{u_1,\dots,u_m\}$、$V=\{v_1,\dots,v_n\}$ を互いに交わらない有限集合とする。
1. $V_\omega$ はグラフである(基礎の公理 により $x\in x$ はない)。$x:=\{v_1,\dots,v_n\}$、$z:=\{u_1,\dots,u_m,x\}$ とおく。$u_i\in z$ なので $z$ は $u_i$ と隣接する。$z$ が $v_j$ と隣接すると仮定する。$v_j\in z$ なら、$v_j\notin U$ なので $v_j=x$ で、$x\in x$ となり基礎の公理に反する。$z\in v_j$ なら $x\in z\in v_j\in x$ となり、これも基礎の公理に反する。同じ理由で $z\notin U\cup V$ である($z=u_i$ なら $u_i\in u_i$、$z=v_j$ なら $x\in z=v_j\in x$)。
2. 平方剰余の相互法則 により、$4$ で割って $1$ 余る相異なる素数 $p,q$ について「$p$ は $q$ を法として平方剰余」と「$q$ は $p$ を法として平方剰余」は同値なので、隣接の関係は対称である。各 $v_j$ について、$v_j$ を法とする平方非剰余 $b_j$ を 1 つとる。中国剰余定理 により、
$$ x\equiv1\pmod4,\qquad x\equiv1\pmod{u_i},\qquad x\equiv b_j\pmod{v_j} $$
を満たす $x$ が $M:=4u_1\cdots u_mv_1\cdots v_n$ を法としてただ 1 つ定まる。$x$ は $M$ と互いに素なので、Dirichletの算術級数定理 により $z\equiv x\pmod M$ となる素数 $z$ が無限に多くあり、$U\cup V$ に属さないものがとれる。$z\equiv1\pmod4$ で、$z$ は $u_i$ を法として $1$ と合同なので平方剰余、$v_j$ を法として $b_j$ と合同なので平方非剰余である。
3. $l,L$ を $U\cup V$ の最小元と最大元とし($U\cup V=\emptyset$ なら頂点 $0$ が正しくつながる)、$k:=L-l+1$、$T:=\{u-l+1\mid u\in U\}$ とおく。普遍集合の $N$ をとり、$z:=l-1-N$ とする。$z< l$ なので $z\notin U\cup V$ で、$w\in U\cup V$ について $|w-z|=N+(w-l+1)$、$1\le w-l+1\le k$ である。よって $|w-z|\in S$ は $w-l+1\in T$、すなわち $w\in U$ と同値である。$\square$

1 は Ackermann の符号 $x\mapsto\sum_{y\in x}2^{\,\text{(}y\text{ の符号)}}$ で $\mathbb N$ に移すと、無限グラフ の 2 進法のグラフ($i< j$ で $j$ の 2 進法の第 $i$ 桁が $1$ なら結ぶ)とそのまま一致する(Cam13 p. 3)。普遍集合は、長さ $1,2,3,\dots$ のすべての $0$-$1$ 列を順につないだ列の $1$ の位置として作れる(同 p. 4)。差のグラフでは平行移動 $x\mapsto x+1$ が自己同型なので、$R$ にはすべての頂点を 1 つの巡回に並べる自己同型があることがわかる(同 p. 14)。

有限の変更に対する安定性

有限の変更に対する安定性

$R$ に次のどの操作を施しても、得られるグラフは $R$ と同型である。

  1. 有限個の頂点を除く。
  2. 有限個の対について、辺と非辺を入れ替える。
  3. 有限集合 $X$ についての 切り替え:$X$ の頂点と $X$ の外の頂点の間の辺と非辺をすべて入れ替え、$X$ の中どうし・外どうしはそのままにする。
  4. 補グラフをとる。
変更に関わる頂点を避けて証人をとる

どれも可算グラフなので、拡大性を示せばよい。$U,V$ を新しいグラフの互いに交わらない有限集合とする。
1・2. 変更に関わった有限個の頂点(除いた頂点、入れ替えた対の端点)の集合を $Y$ とする。lem-rado-witness により、$R$ で $U,V$ に正しくつながる頂点は無限にあるので、$Y$ に属さないものがとれる。その頂点の $U\cup V$ との隣接は変更で変わらないので、新しいグラフでも正しくつながる。
3. $R$ で $U\setminus X$ と $V\cap X$ のすべてと隣接し、$U\cap X$ と $V\setminus X$ のどれとも隣接しない頂点 $z\notin X\cup U\cup V$ をとる(lem-rado-witness で $X$ を避ける)。$z\notin X$ なので、切り替えで $z$ と $X$ の頂点の隣接だけが反転し、新しいグラフで $z$ は $U$ のすべてと隣接し $V$ のどれとも隣接しない。
4. 補グラフで $U,V$ に正しくつながる頂点は、$R$ で $V,U$ に正しくつながる頂点である。$\square$

4 から $R$ は自己補グラフ(補グラフ と同型)である(Cam13 p. 6 の Proposition 5)。一方、無限集合についての切り替えでは $R$ が保たれないことがある。頂点 $x$ の近傍の全体について切り替えると、$x$ は孤立点になる(同 p. 5)。

2 進法のグラフでの証人

頂点を $\mathbb N$ とし、$i< j$ で $j$ の 2 進法の第 $i$ 桁($2^i$ の位)が $1$ のとき $i,j$ を結ぶグラフで、$U=\{0,2\}$、$V=\{1\}$ とする。$U\cup V$ の最大元より大きい $3$ を使って
$$ z=2^0+2^2+2^3=13=1101_{(2)} $$
とおく。$z$ は $U\cup V$ のどの元より大きいので、$w\in U\cup V$ との隣接は $z$ の第 $w$ 桁で決まり、第 $0$・$2$ 桁が $1$、第 $1$ 桁が $0$ だから $z$ は $U,V$ に正しくつながる。一般に $z=\sum_{u\in U}2^u+2^M$($M$ は $U\cup V$ の最大元より大きい)が証人になる。$2^M$ の項は $U=\emptyset$ のときも $z\notin U\cup V$ にするためにある。

鳩の巣性

グラフ $\Gamma$ が 鳩の巣性(pigeonhole property)をもつとは、頂点の集合を空でない 2 つの部分に分けると、どちらかの部分の誘導部分グラフが $\Gamma$ と同型になることをいう。名前は 鳩の巣原理 による。可算無限の完全グラフと空グラフ(辺のないグラフ)は鳩の巣性をもつ。2 つに分けるとどちらかは無限集合で、その誘導部分グラフはまた可算無限の完全グラフ・空グラフだからである。$2$ 個以上の頂点をもつ有限グラフは、分けた部分がどちらも小さいので鳩の巣性をもたない。

鳩の巣性による特徴づけ
  1. $R$ の頂点の集合を空でない有限個の部分 $X_1,\dots,X_k$ に分けると、どれかの $X_i$ の誘導部分グラフは $R$ と同型である。
  2. 鳩の巣性をもつ可算無限グラフは、完全グラフ、空グラフ、$R$ のどれかと同型である。
拡大性が成り立たない組から矛盾を出す

1. $k=2$ の場合は 無限グラフ の命題「分割に対する安定性」である。$k\ge3$ のときは $k$ についての帰納法による。$X_1$ と $X_2\cup\dots\cup X_k$ に分けると、$X_1$ が $R$ と同型であるか、$X_2\cup\dots\cup X_k$ の誘導部分グラフが $R$ と同型である。後者なら、それを $k-1$ 個の部分 $X_2,\dots,X_k$ に分けて帰納法の仮定を当てはめればよい。
2. $\Gamma$ が鳩の巣性をもち、完全グラフでも空グラフでもないとする。
まず $\Gamma$ には孤立点がない。孤立点の集合 $I$ が空でなければ、$I\ne\Gamma$ なので $\Gamma=I\sqcup(\Gamma\setminus I)$ と分けられる。$I$ は空グラフを誘導するので $\Gamma$ と同型でなく、よって $\Gamma\setminus I$ が $\Gamma$ と同型である。ところが孤立点を除いても新しい孤立点はできないので $\Gamma\setminus I$ に孤立点はなく、$I\ne\emptyset$ と食い違う。補グラフで同じ議論をすると、$\Gamma$ には他のすべての頂点と隣接する頂点もない。
$\Gamma$ が $R$ と同型でないとすると、拡大性をもたない。$\Gamma$ の互いに交わらない有限集合 $U,V$ で、正しくつながる頂点がないもののうち、$|U|+|V|$ が最小のものをとる。$U=V=\emptyset$ ならどの頂点も正しくつながるので $|U|+|V|\ge1$ で、$|U|+|V|=1$ なら $U=\{u\}$ の $u$ が孤立点か、$V=\{v\}$ の $v$ が他のすべてと隣接する頂点になり、前段に反する。よって $|U|+|V|\ge2$ で、$U\cup V$ を空でない 2 つの集合 $A,B$ に分けられる。頂点 $w$ が $A$ に正しくつながるとは、$w\notin A$ で、$w$ が $A\cap U$ のすべてと隣接し $A\cap V$ のどれとも隣接しないことをいう($B$ も同様)。
$$ X:=A\cup\{w\notin U\cup V\mid w\text{ は }A\text{ に正しくつながらない}\},\qquad Y:=\Gamma\setminus X $$
とおく。$B\subset Y$ で、$Y\setminus B$ の頂点は $A$ に正しくつながるので、$B$ に正しくつながらない。もしつながれば $U,V$ に正しくつながってしまうからである。よって $X$ の中には $A\cap U,A\cap V$ に正しくつながる頂点がなく、$Y$ の中には $B\cap U,B\cap V$ に正しくつながる頂点がない。$|A|,|B|< |U|+|V|$ なので、$X$ が $\Gamma$ と同型なら $\Gamma$ の中に、正しくつながる頂点がなく頂点数がより少ない組ができて最小性に反する。$Y$ も同じである。$X,Y$ は空でないから、これは鳩の巣性に反する。$\square$

1 で分ける個数が有限であることは欠かせない。頂点を 1 点ずつに分けると、どの部分も $1$ 点のグラフである。2 は Cam13 pp. 5–6 の Proposition 4 で、1 は同 p. 5 の Proposition 3 である。

均質性と自己同型群

thm-rado-unique の 2 は、$R$ が有限グラフの全体を年齢とする Fraïssé 極限 であることを意味する(Fraïssé極限、Cam13 p. 8)。また拡大公理の全体は $R$ の完全な理論を公理化し、その理論は可算モデルが同型を除いて 1 つしかない($\aleph_0$-範疇的である)。$R$ の頂点の $n$ 個の組の自己同型群による軌道は、組の頂点の間の隣接の仕方と等号のパターンで決まるので有限個であり、Ryll-Nardzewskiの定理 の条件と合う(Cam13 p. 9 の Proposition 11)。

自己同型群について知られていること

次の事実はこの記事では証明しない。

  1. $R$ の自己同型群 $\mathrm{Aut}(R)$ の濃度は $2^{\aleph_0}$ である(Cam13 p. 12 の Proposition 13)。
  2. $\mathrm{Aut}(R)$ は 単純群 である(Truss、1985。Cam13 p. 12 の Theorem 8)。

反例

主張反例外れること
無作為な可算グラフは確率 $1$ で $R$(thm-rado-random)頂点 $x,y\in\mathbb N$ を確率 $2^{-(x+y)}$ で結ぶ。辺の本数の期待値は $\sum_{x< y}2^{-(x+y)}=\frac43$ なので、辺は確率 $1$ で有限本しかなく、$R$ ではない($R$ では各頂点の近傍が無限)確率が $\varepsilon$ 以上であること
同上すべての対を確率 $1$ で結ぶと完全グラフになる確率が $1-\varepsilon$ 以下であること
頂点を除いても $R$(prop-rado-robust の 1)頂点 $x$ と隣接しない頂点をすべて除くと、$x$ が残りのすべてと隣接し、$V=\{x\}$、$U=\emptyset$ の証人がない除く頂点が有限個であること
切り替えても $R$(prop-rado-robust の 3)$x$ の近傍の全体について切り替えると $x$ が孤立点になる切り替える集合が有限であること
分けた部分のどれかが $R$(thm-rado-pigeonhole の 1)頂点を 1 点ずつに分ける分ける個数が有限であること
すべての可算グラフを誘導部分グラフに含む可算グラフは $R$$R$ に孤立点を 1 つ加えたグラフは $R$ を含むので普遍だが、孤立点があるので拡大性をもたない拡大性(普遍性は $R$ を特徴づけない)

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する