라도 그래프

1. 개요

라도 그래프는 각 변이 독립적인 확률 변수이고 각 변이 존재할 확률이 p인 무작위 그래프에서 거의 확실하게 나타나는 가산 무한 개의 정점을 가진 그래프이다. 이 그래프는 자기 여 그래프이며, 이진수를 사용하여 정의할 수 있다. 라도 그래프는 확장 속성을 만족하며, 모든 가산 그래프를 유도 부분 그래프로 포함하는 보편성을 가진다. 또한, 라도 그래프는 확장 성질을 갖는 유일한 가산 그래프이며, 유한 개의 꼭짓점이나 변을 삭제해도 동형이다. 라도 그래프는 모델 이론에서 0-1 법칙을 증명하는 데 사용되며, 이 그래프의 자기 동형 사상 군은 단순군이며, 초동질적이고 대칭 그래프이다. 라도 그래프는 유한 개의 꼭짓점이나 변을 추가 또는 삭제하는 변화에 영향을 받지 않으며, 분할 속성을 갖는다. 빌헬름 아커만, 에르되시 팔, 레니 얼프레드, 리하르트 라도 등의 연구를 통해 정의되었으며, 헨슨 그래프, 무한 순환 그래프 등과 관련이 있다.

2. 정의

라도 그래프는 여러 가지 방법으로 정의할 수 있다.

* 무작위 그래프를 통한 정의: 가산 무한 집합을 이용하여 정의한다.
* 이진수를 통한 정의: 이진수를 사용하여 정의한다. 아커만(1937)과 라도(1964)는 비트 연산을 사용하여 라도 그래프를 구성하였다.

2.1. 무작위 그래프를 통한 정의

집합 $V$ 위에, 각 $\backslash \{\backslash \{u,v\backslash \}\backslash colon\; u,v\backslash in\; V,\backslash ;u\backslash ne\; v\backslash \}$에 변이 존재하는지 여부를 무작위로 결정한다. 각 변은 독립 확률 변수이며, 각 변이 존재할 확률은 $p\backslash in(0,1)$이다.

만약 $V$가 가산 무한 집합이라면, 이렇게 하여 얻는 그래프는 $p$의 값에 관계없이, 거의 확실하게 하나의 그래프와 동형이다. 이 그래프를 라도 그래프 $R$라고 한다.

라도 그래프는 가산 무한 개의 정점을 갖는 무작위 그래프의 에르되시-레니 모형에서 거의 확실하게 나타난다. 구체적으로, 두 정점 쌍에 대해 독립적으로 각각 1/2의 확률로 두 정점을 변으로 연결할지 여부를 선택하여 무한 그래프를 형성할 수 있다. 확률 1로, 결과 그래프는 라도 그래프와 동형이다. 이 구성은 1/2 대신 0 또는 1이 아닌 고정된 확률 $p$를 사용할 경우에도 작동한다.

이러한 방식으로 무작위로 생성된 모든 그래프에 대해, 모든 선택 사항을 반대로 하여 여 그래프를 동시에 얻을 수 있다. 즉, 첫 번째 그래프에 동일한 변이 포함되지 않은 경우 변을 포함하고, 그 반대의 경우도 마찬가지이다. 이러한 여 그래프 구성은 각 변을 포함할지 여부를 무작위적이고 독립적으로 선택하는 동일한 과정의 예시이므로, (확률 1로) 라도 그래프를 생성한다. 따라서, 라도 그래프는 자기 여 그래프이다.

2.2. 이진수를 통한 정의

라도 그래프는 이진수를 사용하여 정의할 수 있다.

라도 그래프 $R$의 꼭짓점 집합은 자연수의 집합이다.
:$V(R)=\backslash mathbb\; N=\backslash \{0,1,2,\backslash dots\backslash \}$

두 꼭짓점 $m,n\backslash in\backslash mathbb\; N$ (
* $n$의 이진수 표기법에서 $m$번째 자릿수가 1이라면, $(m,n)\backslash in\; E(R)$이다. 여기서 자릿수는 오른쪽부터 세며, 가장 오른쪽의 자릿수를 0번째로 간주한다.

아커만(1937)과 라도(1964)는 비트 연산을 사용하여 라도 그래프를 구성했는데, 그래프의 정점을 0, 1, 2, ... 자연수로 식별했다.

그래프에서 정점 $x$와 $y$ ()의 $y$의 이진법 표현의 $x$번째 비트가 0이 아닐 때, 두 정점 사이에 간선이 연결된다. 예를 들어, 정점 0의 이웃은 모든 홀수 정점으로 구성되는데, 0번째 비트가 0이 아닌 숫자가 정확히 홀수이기 때문이다. 정점 1은 1이 홀수이고 정점 0은 모든 홀수 정점과 연결되어 있으므로 더 작은 이웃인 정점 0을 갖는다. 정점 1의 더 큰 이웃은 4로 나눈 나머지가 2 또는 3인 모든 정점인데, 그들이 인덱스 1에서 0이 아닌 비트를 갖는 숫자이기 때문이다.

3. 성질

라도 그래프는 지름(diameter^영어)이 2이다. 즉, 임의의 두 꼭짓점 사이에 길이 2 이하의 경로가 존재한다.

라도 그래프에서 유한 개의 꼭짓점이나 변을 삭제하여도 원래 그래프와 동형이다.

3.1. 확대 성질 (Extension Property)

그래프 $G$가 다음 조건을 만족시키면, 확대 성질(extension property^영어)을 갖는다고 한다.

* 임의의 두 유한 집합 $S,T\backslash subset\; V(G)$에 대하여, 만약 $S\backslash cap\; T=\backslash varnothing$이라면, 모든 $s\backslash in\; S$에 대하여 $sx\backslash in\; E(V)$이며 모든 $t\backslash in\; T$에 대하여 $tx\backslash not\backslash in\; E(V)$인 $x\backslash in\; V(G)\backslash setminus(S\backslash cup\; T)$가 존재한다.

라도 그래프는 확대 성질을 갖는 유일한 가산 그래프이다.

라도 그래프는 다음과 같은 확장 속성을 만족한다. 모든 두 개의 서로소인 유한 정점 집합 $U$와 $V$에 대해, 두 집합 밖에 있는 정점 $x$가 존재하여 $U$의 모든 정점과 연결되지만 $V$에는 이웃이 없다.

예를 들어, 라도 그래프의 이진수 정의를 사용하면 다음과 같다.

:$x=2^\{1+\backslash max(U\backslash cup\; V)\}\; +\; \backslash sum\_\{u\backslash in\; U\}\; 2^u.$

그러면 $x$의 이진 표현에서 0이 아닌 비트는 $x$를 $U$의 모든 것과 인접하게 만든다. 그러나 $V$의 정점에 해당하는 $x$의 이진 표현에는 0이 아닌 비트가 없으며, $x$는 매우 커서 $V$의 모든 요소의 $x$번째 비트가 0이다. 따라서 $x$는 $V$의 어떤 정점과도 인접하지 않다.

3.2. 유도 부분 그래프 (Induced Subgraph)

확대 성질을 갖는 그래프는 임의의 가산 그래프를 유도 부분 그래프로 포함한다. 이는 수학적 귀납법으로 쉽게 보일 수 있다.

확장 속성은 유한 또는 가산 무한 그래프 $G$의 동형 복사본을 유도 부분 그래프로 라도 그래프 내에서 구성하는 데 사용될 수 있다.

이렇게 하려면 $G$의 정점을 정렬하고, 라도 그래프 내의 $G$의 부분 복사본에 동일한 순서로 정점을 추가한다. 각 단계에서 $G$의 다음 정점은 정점의 정렬에서 더 앞선 $G$의 정점 집합 $U$에 인접하고, $G$에서 이전 정점의 나머지 집합 $V$에는 인접하지 않는다. 확장 속성에 의해, 라도 그래프는 또한 $U$의 구성원에 해당하는 부분 복사본의 모든 정점에 인접하고, $V$의 구성원에 해당하는 부분 복사본의 모든 정점에 인접하지 않은 정점 $x$를 갖게 된다. $x$를 $G$의 부분 복사본에 추가하면 정점이 하나 더 있는 더 큰 부분 복사본이 생성된다.

이 방법은 0-정점 부분 그래프를 기본 사례로 하여 모든 유한 또는 가산 무한 그래프가 라도 그래프의 유도 부분 그래프라는 귀납법 증명의 기초를 형성한다.

3.3. 동형 (Isomorphism)

라도 그래프에서 유한 개의 꼭짓점을 삭제하여도 라도 그래프와 동형이다. 유한 개의 변을 삭제하는 경우도 마찬가지이다.

라도 그래프는 그래프 동형까지, 확장 성질을 갖는 유일한 가산 그래프이다. 예를 들어, $G$와 $H$를 확장 성질을 가진 두 개의 가산 그래프라고 하고, $G\_i$와 $H\_i$를 각각 $G$와 $H$의 동형 유도 부분 그래프라고 하자. 또한 $g\_i$와 $h\_i$를 각각 $G$와 $H$의 정점 열거에서 $G\_i$와 $H\_i$에 속하지 않는 첫 번째 정점이라고 하자. 그러면, 확장 성질을 두 번 적용하여, 이전 부분 그래프의 모든 정점과 함께 $g\_i$와 $h\_i$를 포함하는 동형 유도 부분 그래프 $G\_\{i+1\}$과 $H\_\{i+1\}$을 찾을 수 있다. 이 과정을 반복함으로써, 결국 $G$와 $H$의 모든 정점을 포함하는 유도 부분 그래프 간의 일련의 동형 사상을 구성할 수 있다. 따라서, 전후 방법에 의해 $G$와 $H$는 동형이어야 한다.

랜덤 그래프 구성, 이진수 구성, 그리고 Paley 그래프 구성을 통해 생성된 그래프는 모두 확장 성질을 가진 가산 그래프이므로, 이 논증은 그것들이 서로 동형임을 보여준다.

3.4. 대칭성 (Symmetry)

라도 그래프에서 상호 동형인 두 개의 유한 부분 그래프에 왕복 구성을 적용하면, 그 동형 사상을 전체 라도 그래프의 자기 동형 사상으로 확장할 수 있다. 유한 부분 그래프의 모든 동형 사상이 전체 그래프의 자기 동형 사상으로 확장된다는 사실은 라도 그래프가 초동질적임을 의미한다. 특히, 인접한 정점의 정렬된 쌍을 다른 인접한 정점의 정렬된 쌍으로 옮기는 자기 동형 사상이 존재하므로, 라도 그래프는 대칭 그래프이다.

라도 그래프의 자기 동형 사상 군은 단순군이며, 그 원소의 수는 연속체의 기수와 같다. 이 군의 모든 부분군 중 지수가 연속체의 기수보다 작은 것은 유한한 정점 집합의 점별 고정자를 포함하며, 동일한 집합의 집합별 고정자에도 포함된다.

3.5. 견고성 (Robustness)

라도 그래프에서 유한 개의 꼭짓점을 삭제하여도 라도 그래프와 동형이다. 마찬가지로, 유한 개의 변을 삭제하여도 라도 그래프와 동형이다. 그래프 $G$가 라도 그래프에서 유한 개의 변이나 정점을 삭제하거나, 유한 개의 변을 추가하여 형성된 경우, 이러한 변경은 그래프의 확장 속성에 영향을 미치지 않는다. 수정된 그래프에서 $U$와 $V$ 집합 쌍에 대해, 수정된 $G$의 부분을 $V$에 추가하고 수정되지 않은 라도 그래프에서 확장 속성을 적용함으로써 $U$의 모든 것과 인접하고 $V$의 모든 것과 인접하지 않은 정점을 찾을 수 있다. 따라서 이러한 유형의 유한 변경은 라도 그래프와 동형인 그래프를 생성한다.

3.6. 분할 (Partition)

라도 그래프의 정점을 두 집합 $A$와 $B$로 분할하거나, 더 일반적으로 유한 개의 부분 집합으로 분할할 경우, 분할 집합 중 적어도 하나가 유도한 부분 그래프는 전체 라도 그래프와 동형이다. 카메론(Cameron)은 다음의 짧은 증명을 제시한다. 만약 어느 부분도 라도 그래프와 동형인 부분 그래프를 유도하지 못한다면, 그들 모두 확장 속성을 갖지 못하며, 각 부분 그래프 내에서 확장될 수 없는 집합 쌍 $U\_i$와 $V\_i$를 찾을 수 있다. 그러나 이 경우, 집합 $U\_i$의 합집합과 집합 $V\_i$의 합집합은 전체 그래프에서 확장될 수 없는 집합을 형성하게 되며, 이는 라도 그래프의 확장 속성에 모순된다. 모든 분할의 유도된 부분 그래프 중 하나와 동형인 이 속성은 세 개의 가산 무한 무방향 그래프, 즉 라도 그래프, 완전 그래프, 그리고 빈 그래프만 가지고 있다.

정점 분할 대신 가장자리 분할에 관한 관련된 결과가 있다. 라도 그래프의 가장자리를 유한 개의 집합으로 분할할 때마다, 최대 두 개의 색상을 사용하는 전체 라도 그래프와 동형인 부분 그래프가 존재한다. 그러나 반드시 한 가지 색상의 가장자리만 사용하는 동형 부분 그래프가 존재하지 않을 수도 있다.

4. 모델 이론 및 0-1 법칙

파긴은 라도 그래프를 사용하여 그래프 논리에서 일계 논리 명제에 대한 영-일 법칙을 증명했다. 이 법칙에 따르면, 특정 유형의 논리적 명제가 라도 그래프에 대해 참 또는 거짓이면, 이는 거의 모든 유한 그래프에 대해서도 각각 참 또는 거짓이다.

파긴은 콤팩트성 정리를 사용하여, 확장 공리로부터 증명 가능하고 라도 그래프에 의해 모델링되는 일계 논리 문장이 정확히 거의 모든 무작위 유한 그래프에 대해 참인 문장임을 보였다. 이는 *n*개의 레이블이 지정된 정점을 가진 그래프 중 *n*개의 정점을 가진 그래프를 무작위로 선택했을 때, 해당 문장이 참이 될 확률이 *n*이 무한대로 갈수록 1에 수렴한다는 의미이다. 반대로, 라도 그래프에 의해 모델링되지 않는 문장은 거의 모든 무작위 유한 그래프에서 거짓이다. 따라서 모든 일계 논리 문장은 무작위 유한 그래프에 대해 거의 항상 참이거나 거의 항상 거짓이며, 이는 라도 그래프가 해당 문장을 모델링하는지 여부로 판별할 수 있다. 이러한 특성 때문에 라도 그래프에 의해 모델링된 문장의 이론은 "무작위 그래프의 이론" 또는 "그래프의 거의 확실한 이론"이라고 불린다.

0-1 법칙에 따라, 충분히 큰 *n* 값을 선택하고 해당 문장을 모델링하는 *n*개의 정점을 가진 그래프의 수를 세어, 특정 일계 논리 문장이 라도 그래프에 의해 모델링되는지 유한한 시간 안에 확인할 수 있다. 그러나 "충분히 큰" 값은 문장 크기에 대해 적어도 지수적이다.

라도 그래프가 주어진 문장을 모델링하는지 여부를 결정하는 문제는 PSPACE-완비이므로, 지수 시간보다 더 빨리 해결될 가능성은 낮다.

4.1. 1차 논리 (First-order logic)

그래프의 1차 언어는 그래프의 정점을 나타내는 변수, 전칭 기호와 존재 기호, 논리 연결사, 그리고 정점의 같음과 인접성을 위한 술어로 구성된 수학적 논리의 잘 구성된 문장들의 모음이다. 예를 들어, 그래프에 고립된 정점이 없다는 조건은 다음과 같은 문장으로 표현될 수 있다.

:∀u:∃v: u∼v

여기서 ∼ 기호는 두 정점 사이의 인접 관계를 나타낸다.

이 문장 S는 어떤 그래프에서는 참이고, 다른 그래프에서는 거짓이다. 그래프 G가 S가 G의 정점과 인접 관계에 대해 참일 경우, S를 "모델링"한다고 하며, G|=S로 표기한다.

라도 그래프의 확장 속성은 일련의 1차 문장 E_i,j로 표현될 수 있으며, 이는 집합 A의 i개의 정점과 집합 B의 j개의 정점(모두 서로 다름)을 선택할 때마다, A의 모든 것과 인접하고 B의 모든 것과는 인접하지 않은 정점이 존재함을 나타낸다. 예를 들어, E_1,1은 다음과 같이 쓸 수 있다.

:∀a:∀b:a≠b→∃c:c≠a∧c≠b∧c∼a∧¬(c∼b)

4.2. 완전성 (Completeness)

Gaifman^영어은 문장 $E\_\{i,j\}$가 대칭적이고 비반사적(즉, 이 문장을 모델링하는 그래프가 무방향이고 자체 루프가 없다는 의미)이라는 추가 문장과 함께, 완전한 이론의 공리임을 증명했다. 이는 각 일계 논리 문장 $S$에 대해, $S$와 그 부정 중 정확히 하나가 이 공리에서 증명될 수 있음을 의미한다. 라도 그래프는 확장 공리를 모델링하므로 이 이론의 모든 문장을 모델링한다.

논리학에서, 주어진 무한 기수 $\backslash lambda$에 대해 (동형 사상을 제외하고) 하나의 모델만 갖는 이론을 $\backslash lambda$-범주적이라고 한다. 라도 그래프가 확장 속성을 가진 유일한 가산 그래프라는 사실은 또한 라도 그래프가 해당 이론의 유일한 가산 모델임을 의미한다. 라도 그래프의 이러한 고유성은 라도 그래프의 이론이 ω-범주적이라고 말함으로써 표현될 수 있다. 워쉬와 보트는 1954년에 이론이 $\backslash lambda$-범주적이고 (어떤 무한 기수 $\backslash lambda$에 대해) 유한 모델이 없는 경우, 해당 이론은 완전해야 함을 증명했다. 따라서 라도 그래프의 이론이 완전하다는 가이프만의 정리는 워쉬-보트 테스트에 의해 라도 그래프의 고유성으로부터 도출된다.

4.3. 유한 그래프와의 관계

파긴(Ronald Fagin)은 라도 그래프를 사용하여 그래프 논리에서 일계 논리 명제에 대한 영-일 법칙을 증명했다. 이러한 유형의 논리적 명제가 라도 그래프에 대해 참 또는 거짓이면, 이는 거의 모든 유한 그래프에 대해서도 각각 참 또는 거짓이다.

파긴이 증명했듯이, 확장 공리로부터 증명 가능하고 라도 그래프에 의해 모델링되는 일계 논리 문장은 정확히 거의 모든 무작위 유한 그래프에 대해 참인 문장이다. 이는 *n*개의 레이블이 지정된 정점을 가진 모든 그래프 중에서 *n*개의 정점을 가진 그래프를 균일하게 무작위로 선택하면, 그러한 문장이 선택된 그래프에 대해 참이 될 확률이 *n*이 무한대로 갈 때 극한에서 1에 접근한다는 것을 의미한다. 대칭적으로, 라도 그래프에 의해 모델링되지 않는 문장은 거의 모든 무작위 유한 그래프에 대해 거짓이다. 따라서 모든 일계 논리 문장은 무작위 유한 그래프에 대해 거의 항상 참이거나 거의 항상 거짓이며, 이 두 가지 가능성은 라도 그래프가 해당 문장을 모델링하는지 여부를 결정함으로써 구별될 수 있다. 파긴의 증명은 콤팩트성 정리를 사용한다. 이러한 등가성에 기반하여, 라도 그래프에 의해 모델링된 문장의 이론을 "무작위 그래프의 이론" 또는 "그래프의 거의 확실한 이론"이라고 부른다.

이 0-1 법칙 때문에, 충분히 큰 *n* 값을 선택하고 해당 문장을 모델링하는 *n*개의 정점을 가진 그래프의 수를 세어, 특정 일계 논리 문장이 라도 그래프에 의해 모델링되는지 유한한 시간 내에 테스트할 수 있다. 그러나 여기서 "충분히 큰"은 문장의 크기에 대해 적어도 지수적이다. 예를 들어 확장 공리 E_k,0은 (k+1)개의 정점을 가진 클리크의 존재를 의미하지만, 해당 크기의 클리크는 *k*에서 지수적으로 커지는 크기의 무작위 그래프에서 높은 확률로 존재한다.

라도 그래프가 주어진 문장을 모델링하는지 여부를 결정하는 것이 지수 시간보다 더 빨리 수행될 가능성은 낮으며, 이 문제는 PSPACE-완비이기 때문이다.

5. 역사

빌헬름 아커만(Wilhelm Ackermann^독일어)이 1937년에 라도 그래프를 정의하였다. 1963년에 에르되시 팔과 레니 얼프레드(Rényi Alfréd^헝가리어)는 이 그래프가 유일한 무작위 그래프라는 것을 증명하였다. 1964년에 리하르트 라도는 라도 그래프를 재발견하였으며, 모든 가산 그래프를 유도 부분 그래프로 포함한다는 것을 보였다.

5.1. 빌헬름 아커만 (Wilhelm Ackermann)

빌헬름 아커만(Wilhelm Ackermann^독일어)이 1937년에 라도 그래프를 처음 정의하였다.

5.2. 에르되시 팔 (Erdős Pál)과 레니 얼프레드 (Rényi Alfréd)

에르되시 팔과 레니 얼프레드(Rényi Alfréd^헝가리어)가 1963년에 이 그래프가 유일한 무작위 그래프라는 것을 증명하였다.

5.3. 리하르트 라도 (Richard Rado)

리하르트 라도는 1964년에 라도 그래프를 재발견하고, 모든 가산 그래프를 유도 부분 그래프로 포함한다는 보편 그래프 성질을 증명하였다. 라도는 자연수를 꼭짓점 집합으로 하는 명시적인 구성을 제시하였는데, 이는 빌헬름 아커만의 구성 중 하나와 본질적으로 동일하다.

6. 관련 개념

라도 그래프는 스콜렘의 역설에 기초하여 구성할 수 있다. 1차 집합 이론에 대한 가산 모델이 존재한다는 사실을 이용하여, 각 집합에 대한 꼭짓점을 만들고 한 집합이 다른 집합의 구성원인 경우 간선으로 연결하여 라도 그래프를 구성한다.

라도 그래프는 페일리 그래프와 유사하게 구성될 수 있는데, 그래프의 꼭짓점으로 4를 모듈로 1과 합동인 모든 소수를 취하고, 두 숫자 중 하나가 다른 숫자를 모듈로 하는 제곱 잔여일 때 두 꼭짓점을 간선으로 연결한다.

라도 그래프는 초제차이며, 유한 부분 구조의 종류, 즉 유한 그래프의 프레세 극한이다. 이는 해당 이론이 양자 소거를 가지며 ω-범주적이라는 것과 동치이다. 라도 그래프는 가산 ω-범주적 이론의 가산 모형이므로, 소수이자 포화이다.

라도 그래프의 이론은 독립성 성질을 가진 이론과 단순 이론이 안정적이지 않은 이론의 전형적인 예이다.

6.1. 무한 순환 그래프 (Infinite circulant graph)

라도 그래프는 정수를 꼭짓점으로 하고, 두 정수 사이의 거리(절댓값 차이)가 특정 집합 $S$에 속하면 두 정수 사이에 간선을 연결하는 무한 순환 그래프로 구성할 수 있다. 이때, 집합 $S$는 무작위로 선택하거나, $S$의 지시 함수를 모든 유한 이진 시퀀스의 연결로 선택하여 구성할 수 있다.

6.2. 기타 관련 개념

라도 그래프는 페일리 그래프와 유사하게 구성될 수 있다. 이 그래프의 꼭짓점은 4를 모듈로 1과 합동인 모든 소수로 구성되며, 두 숫자 중 하나가 다른 숫자를 모듈로 하는 제곱 잔여일 때 두 꼭짓점을 간선으로 연결한다. 제곱 상호 법칙과 꼭짓점을 4 모듈로 1과 합동인 소수로 제한함으로써, 이는 대칭 관계이며, 라도 그래프와 동형인 무방향 그래프를 정의한다.

라도 그래프는 무한 순환 그래프로도 구성될 수 있는데, 정수를 꼭짓점으로 하고 거리(두 정수의 절댓값 차이)가 특정 집합 $S$에 속하는 각 두 정수 사이에 간선이 있는 방식이다. $S$는 무작위로 선택되거나, $S$의 지시 함수를 모든 유한 이진 시퀀스의 연결로 선택하여 구성할 수 있다.

라도 그래프는 또한 무한 블록 디자인의 블록 교차 그래프로 구성될 수 있으며, 여기서 점의 수와 각 블록의 크기는 가산 무한이다. 또한 유한 그래프의 한 종류인 프래세 극한으로 구성될 수도 있다.