[Graph Theory] Random graphs and the second moment method

$n$ 개의 vertex가 있다고 했을 때,  edge가 있을 확률을 $p$라고 주자. 이 자체가 probability space야.

edge가 있을 수도 있고 없을 수도 있다

Definition.

$q_n$: property $Q$ 가 probability space $\Omega_n$ 내에서 성립할 확률. 

Property $Q$ 는 $\lim_{n \rightarrow \infty} q_n = 1$일 때 거의 (almost always) 성립

probability space $G(n, p)$: $p$ 를 $n$에 대한 function 이라고 했을 때, edge가 $p$ 확률로 있을 확률 공간, independently at random. 그래프 자체를 하나의 probability space 로 본 것. 또, 이 probability space로 만들어지는 그래프는 그 자체로 random variable 이기도 하다.

$G(n, p)_{n \in \mathbf{N}}$: standard of binomial random graph model

uniform random graph model, $G(n, m)$: vertex set $[n]$ 이 $N = \binom{n}{2}$ 일 때, $m$개의 edge 가 $\binom{N}{m}^{-1}$ 의 확률로 존재하는 probability space. edge 가 있을 확률이 아닌, edge의 총 갯수를 even 하게 나눠서 보여주는 그래프.

 

우리는 binomial random graph model 에 집중해보자.

Graph property $Q$ 는 convex 하다 IF $G$ 가 $Q$를 만족하는데, $F \subseteq G \subseteq H$ 에 대해서 $F$랑 $H$가 $Q$를 만족하면.  convex의 의미는, 내 양옆이 만족하면 나도 만족한다는 거. 오목 함수를 떠올려보자.

 

Theorem

$Q$ 가 convex property 이고, $p(1-p)\binom{n}{2} \rightarrow \infty$ 면,

$G(n, p)$ 는 almost always satisfies $Q$ $\Leftrightarrow$  $G(n, m)$은 almost always satisfies $Q$ for fixed $x$ where $m = p\binom{n}{2} + x(p(1-p)\binom{n}{2})^{1/2}$.

 

그럼 이제 의문은, 어떤 property 들이 $G(n, p)$ 에 대해서 convex하게 먹히느냐.

 

Definition

monotone property: edge 가 추가되어도 유지되는 graph property. 예를 들어 Hamiltonian cycle 의 존재 유무 같은 경우에는 edge가 추가되어도 유지되지.

 

그러니까, $p$ 가 커지면 property 도 유지될 가능성이 크지. 그럼 monotone property 가 발생하게 되는 어느 임계점, 'threshold' 를 생각해보자.

 

Definition

A threshold probability function $t(n)$: 어떤 monotone property $Q$ in $G(n, p)$에 대해, $p(n)/t(n) \rightarrow 0$일 때에는 $Q$를 almost always do not satisfies 하고, $p(n)/t(n) \rightarrow \infity$ 일 때 almost always satisfies 하는 함수.

A sharp threshold probability function $t(n)$: 어떤 any $\esilon > 0$ 에 대해서, $p(n)/t(n) \leq (1-\epsilon) $이면  almost always do not satisfies $Q$ , $p(n)/t(n) \geq (1+\epsilon)$ 이면 almost always satisfies.

 

가장 쉬운 예시인 connectedness 를 예로 들어볼게.

일단 threshold function 은 $n$이 커질수록 infinity 로 가는 함수여야 한다는 걸 보여볼게

 

Theorem.

fixed $p \in (0, 1]$ 에 대해서

binomial random graph $G(n, p)$ 는 almost always connected.

일단 n이 무한으로 가면 웬만하면 연결되어있다.

$\textit{Proof}$

disconnect 만들려면, bipartite 하게 나누고, 둘 사이의 edge가 안생기게 하면 된다.

그러니까 $Pr([S, \overline{S}] = \emptyset)$ 을 생각해보자.

$|S| = k$ 라면, $k(n-k)$ 개의 edge가 $[S, \overline{S}]$ 사이에 있을 수 있다.

각각 edge가 없을 확률은 (1-p) 다. 그러니까, $G(n, p)$ 가 disconnecte 되어있을 확률 $q_n$ 은

$\begin{equation}

q_n \leq \frac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k} (1-p)^{k(n-k)} = \sum_{1 \leq k \leq n/2}\binom{n}{k} (1-p)^{k(n-k)}

\end{equation}$

여기서 $\binom{n}{k} \leq n^k$ 인걸 써먹고, $(1-p)^{n-k} \leq (1-p)^{n/2}$ 인걸 써먹으면, $q_n \leq \sum_{1 \leq k \leq \n/2}(n(1-p)^{n/2})^k$ 가 나온다.

$n$ 이 충분히 크면, $n(1-p)^{n/2} < 1$ 이어서 n이 커지면 0으로 수렴.

그러니까, $q_n$ 이 0으로 가면 $n \rightarrow \infty$

disconnect 될 확률이 0에 수렴하면, $n$ 은 무한대로 간다. $n$이 겁나게 많아지면 disconnect될 확률이 0으로 수렴한다.

 

이제 수렴한다, 연결되어있다, 유지된다. 이런 모호한 것 보다, 좀 더 정확한 threshold function 을 찾아보자.

 

Definition

random variable $X$ 의 rth moment: the expectaion of $X^r$. X 가 $r$ 차례 곱해졌을 때 생길 기댓값.

The variance of $X$, $Var(X)$: the quantity $\mathbf{E}[(X-\mathbf{E}[X])^2]$. X와 X 기댓값 차이의 2차 moment.

The standard deviation of $X$: $\sqrt{Var(X)}$.

 

Lemma <Markov's inequality>

$X$ 가 nonnegative random variable 이면, $Pr[X \geq t] \leq \frac{\mathbf[X]}{t}$.

어떤 기준치 $t$ 보다 random variable 이 크게 나올 확률은, $t$ 가 커질수록 작아진다.

if $X$ 가 discrete random variable 이라면,

$\mathbf{E}[X] \rightarrow 0$ 은 $Pr[X = 0] \rightarrow 1$ 을 의미한다.

기댓값이라는 건 결국 대다수의 RV 결과가 기댓값 근처에 몰려있다는 건데, 기댓값이 0으로 수렴한다는 건 X=0이 뜰 확률이 크다는 얘기다.

 

Lemma <Chebyshev's inequality>

$\begin{equation} Pr[|X-\mathbf{E}[X]| \geq t] \leq \frac{Var(X)}{t^2} \end{equation}$

기댓값에서 멀어질수록, 확률이 날아간다.

$\textit{Proof}$

Pr[(X-\mathbf{E}[X])^2 \geq t^2] \leq \frac{\mathbf{E}[(X-\mathbf{E}[X])^2}{t^2} = \frac{Var(X)}{t^2}

 

위에 Chebyshev's inequality 는 $Pr(X=0)$ 의 bound 를 정하는 데에 유용한데, 우린 이걸 second moment method라고 부르기로 했다.

 

Lemma <Second Moment method>

$Pr(X = 0) \leq \farc{\mathbf{E}[X^2] - \mathbf{E}[X]^2}{\mathbf{E}[X]^2}. 

Thus, $Pr(X=0) \rightarrow 0$ when $\frac{\mathbf{E}[X^2]}{\mathbf{E}[X]^2} \rightarrow 1$.

$\textit{Proof}$

일단 $\mathbf{E}[(X - \mathbf{E}[X])^2] = \mathbf{E}[X^2] - \mathbf{E}[X]^2$ 

여서 $Var(X)$에 위 식을 넣어줌. $t = \mathbf{E}[X]$ 를 넣어주면 위 부등식이 나온다.

 

$p$ 가 작다면, $G(n, p)$ 는 isolated vertices 가 생기겠지.

 

Theorem

$(n-1)p = \log{(n)} + c(n)$ 이다

$c(n) \rightarrow \infty$ 이면 $G(n, p)$ 는 almost always no isolated vertices 이고,

$c(n) \rightarrow -\infty$ 이면$G(n, p)$ 는almost always an isolated vertex 이다.

특히, $\frac{n}{\log{n}}$ 일 때 minimum degree가 최소 하나가 넘을 threshold 다.

$\textit{Proof}$

$I_v$ 는, $v$ 가 isloated 일 때 1, 아닐 때 0. $X_1 = \sum_v I_v$, 그러니까 isolated vertices 를 세는 random variable을 하나 만들면

$\mathbf{E}[X_1] = \sum_{v}(1-p)^{n-1} = n(1-p)^{n-1} \simeq e^{-c}$

가 나오는데, Markov's inequality 에 따라 $Pr[X_1 \geq 1] \leq e^{-c}$ 인데 $c \rightarrow \infty$에 따라 0으로 수렴한다.

$c$ 가 $-\infty$로 수렴한다고 치자. 그러면 second moment method 를 쓰기 위해 $\mathbf{E}[X^2]$를 계산해보자. $I_v^2 = I_v$니까,

$\mathbf{E}[X_1^2] = \mathbf{E}[X_1] + \sum_{v \neq u} \mathbf{E}[I_u I_v]$

니까, $I_uI_v$ 가 1이 되려면 $2(n-2)+1$ 개의 edge 가$u, v$에 선택이 안 되어야 하므로 $\mathbf{E}[I_uI_v] = (1-p)^{2n-3}$

하여간 뭐 요래저래 하면 $\frac{\mathbf{E}[X_1^2]}{\mathbf{E}[X_1]^2} \simeq 1 + \frac{\mathbf{E}[X_1]}{\mathbf{E}[X_1]^2} \rightarrow 1$ 이 나오면서

$Pr[X_1 = 0] \rightarrow 0$ 이 나온다.

 

Theorem

function $p = \frac{\log n}{n} 은 binomial random graph model $G(n, p)$가 connected 될 sharp threshold 다.