⬡이산수학
VII. 확률적 방법 · 16/16

확률적 방법

기대값 논법, 램지 수 하계 — 현대 조합론의 다리

읽음 0/0 갱신 2026-07-05

개요 — 동기·문제의식

확률적 방법은 무작위성을 써서 결정론적 존재 명제를 증명하는 방법이다. 어떤 대상이 존재함을 보이고 싶은데 직접 만들기 어렵다면, 큰 확률공간에서 무작위 대상을 뽑고 원하는 성질이 양의 확률로 일어남을 보인다. 그러면 그런 대상은 적어도 하나 존재한다.

그래프이론에서 이 방법은 특히 강력하다. 무작위 그래프는 명시적으로 그리기 어려운 그래프, 예를 들어 큰 girth와 큰 chromatic number를 동시에 갖는 그래프나 큰 Ramsey 수 하한을 주는 coloring을 자연스럽게 만들어 낸다.1

중요한 점은 결론이 확률적이라는 뜻이 아니다. 증명에 확률을 썼을 뿐, 결론은 "그런 그래프가 존재한다"는 완전히 결정론적인 문장이다.

직관

동전을 던져 간선을 넣거나 빼는 그래프 $G(n,p)$ 를 생각하자. 어떤 나쁜 구조의 기대 개수가 1보다 작다면, 그 나쁜 구조가 하나도 없는 그래프가 존재할 가능성이 있다. 더 정확히는 기대값이 작으면 나쁜 구조가 너무 많은 그래프가 대부분일 수 없다.

Ramsey 하한에서는 완전그래프의 간선을 빨강/파랑으로 무작위 칠한다. 단색 $K_k$ 의 기대 개수가 1보다 작으면, 단색 $K_k$ 가 하나도 없는 coloring이 존재한다. 그러면 $R(k)$ 가 그 정점 수보다 크다는 하한이 나온다.

Erdős의 큰 girth·큰 색수 정리는 더 섬세하다. 무작위 그래프는 짧은 cycle을 조금 갖지만, 그 cycle마다 정점 하나씩 지워도 여전히 큰 independent set이 없도록 만들 수 있다. 그러면 짧은 cycle은 없고 색수는 큰 그래프가 남는다.

정의

Erdős-Rényi random graph $G(n,p)$: 정점집합 $[n]$ 위에서 각 가능한 간선을 독립적으로 확률 $p$ 로 선택한 그래프.2

random variable: 무작위 그래프마다 숫자를 대응하는 함수. 예: triangle 수, 독립수, 색수, 짧은 cycle 수.

indicator variable: 사건 $A$ 가 일어나면 1, 아니면 0인 확률변수 $1_A$.

기댓값: $\mathbb E[X]$ 는 확률변수 $X$ 의 평균값이다. 선형성 $$\mathbb E[X+Y]=\mathbb E[X]+\mathbb E[Y]$$ 은 독립성 없이도 성립한다.

Markov 부등식: $X\ge0$ 이면 $$\mathbb P(X\ge a)\le \mathbb E[X]/a.$$

방법 핵심 문장
positive probability 원하는 사건의 확률이 $>0$ 이면 존재
first moment 나쁜 구조의 기대 개수가 $<1$ 이면 없는 예가 존재
deletion method 나쁜 구조를 조금 만든 뒤 지워서 제거
second moment 분산을 제어해 거의 항상 성립을 보임
Lovász local lemma 약한 의존성이 있는 나쁜 사건들을 동시에 피함

주요 정리

정리 1 (기댓값에 의한 존재). 비음수 정수값 확률변수 $X$ 에 대해 $\mathbb E[X]<1$ 이면 $X=0$ 인 대상이 존재한다.

증명 보기

증명. 모든 대상에서 $X\ge1$ 이면 기대값도 적어도 1이다. 따라서 기대값이 1보다 작으면 어떤 대상에서는 $X=0$ 이어야 한다. ∎

정리 2 (Ramsey 하한). 대각 Ramsey 수는 지수적으로 크다. 특히 $k\ge3$ 에 대해 $$R(k)>2^{k/2}$$ 형태의 하한이 성립한다.3

증명 보기

증명 스케치. $K_n$ 의 각 간선을 독립적으로 빨강/파랑으로 칠한다. 고정된 $k$-정점 집합이 단색 clique가 될 확률은 $2\cdot 2^{-\binom k2}$ 이다. 따라서 단색 $K_k$ 의 기대 개수는 $$\binom nk 2^{1-\binom k2}.$$ 이 값이 1보다 작도록 $n$ 을 고르면 단색 $K_k$ 가 없는 coloring이 존재한다. 그러면 $R(k)>n$ 이다. 적절한 계산으로 $n$ 을 $2^{k/2}$ 규모까지 잡을 수 있다.

정리 3 (Erdős, 큰 girth와 큰 색수). 임의의 $k$ 에 대해 girth가 $>k$ 이고 chromatic number가 $>k$ 인 그래프가 존재한다.4

증명 보기

증명 스케치. $p=n^{\alpha-1}$, $0<\alpha<1/k$ 로 $G(n,p)$ 를 고른다. 짧은 cycle의 기대 개수는 $o(n)$ 이고, 큰 independent set이 존재할 확률은 0으로 간다. 따라서 어떤 $G$ 는 짧은 cycle이 $n/2$개 미만이고 큰 independent set이 없다. 각 짧은 cycle에서 정점 하나씩 지워 $H$ 를 만들면 $H$ 는 girth $>k$ 이고, 독립수가 $|H|/k$ 보다 작으므로 $k$색으로 칠할 수 없다.

정리 4 (Markov 부등식). $X\ge0$ 이고 $a>0$ 이면 $\mathbb P(X\ge a)\le\mathbb E[X]/a$.

증명 보기

증명. 기대값의 합에서 $X\ge a$ 인 경우들만 보아도 적어도 $a\mathbb P(X\ge a)$ 만큼 기여한다. ∎

정리 5 (Lovász local lemma, 안내). 나쁜 사건들의 확률이 작고 각 사건이 의존하는 다른 사건 수가 제한되어 있으면, 모든 나쁜 사건을 동시에 피할 양의 확률이 있다.5

의미. first moment는 모든 나쁜 사건의 기대 총합이 작아야 한다. local lemma는 나쁜 사건이 많아도 서로 거의 독립이면 동시에 피할 수 있게 해 준다.

예제

예제 1 (무작위 triangle 수). $G(n,p)$ 에서 triangle 기대 개수는 $\binom n3 p^3$ 이다. 각 3정점 집합이 triangle일 indicator를 더하면 된다.

예제 2 (무작위 edge 수). $G(n,p)$ 의 간선 수 기대값은 $\binom n2 p$ 이다.

예제 3 (Ramsey coloring). $K_5$ 의 red/blue random coloring에서는 단색 triangle 기대값이 $\binom53\cdot 2^{1-3}=10/4=2.5$ 라서 기대값만으로 단색 triangle 없는 coloring을 보장하지 못한다. 실제로는 특별한 5-cycle coloring이 필요하다.

예제 4 (큰 $k$의 Ramsey 하한). $k$ 가 커지면 $\binom nk 2^{1-\binom k2}$ 이 1보다 작아지는 $n$ 이 지수적으로 커진다. 이것이 $R(k)$ 의 지수 하한이다.

예제 5 (삭제 방법). 짧은 cycle이 조금 있는 그래프에서 cycle마다 정점 하나를 지우면 girth를 키울 수 있다. 단, 너무 많이 지우면 색수가 낮아질 수 있으므로 independent set 제어가 함께 필요하다.

예제 6 (Petersen 그래프와 확률적 예). Petersen 그래프는 명시적 small example이고, 확률적 방법은 보통 훨씬 큰 비구성적 예를 만든다. 둘은 반례를 제공한다는 역할은 비슷하지만 증명 철학이 다르다.

예제 7 (random graph evolution). $p$ 가 커짐에 따라 고립 정점이 사라지고, giant component가 생기며, 연결성과 Hamiltonicity가 차례로 나타난다. 이는 threshold function 주제다.

예제 8 (local lemma의 전형적 상황). 변수들이 많고 각 제약이 일부 변수에만 의존하는 coloring 문제에서, 각 bad event는 가까운 제약들과만 의존한다. 이때 local lemma가 first moment보다 강하다.

흔한 오해와 함정

큰 그림 / 연결

extremal and ramsey에서 Ramsey 수의 하한은 확률적 방법의 대표적 첫 사례다. 상한은 조합적 귀납으로, 하한은 무작위 coloring으로 얻는 비대칭이 Ramsey 이론의 전형적 모습이다.

그래프 채색에서는 Erdős의 정리가 큰 색수가 반드시 큰 clique나 작은 cycle에서 오는 것이 아님을 보여준다. 국소적으로 tree처럼 보여도 전역적으로는 많은 색이 필요할 수 있다.

graphs basics and trees의 girth, cycle, independent set 같은 기본 용어가 확률적 방법의 계산 대상이 된다. 고급 확률론의 조건부확률, 독립성, concentration은 probability 위키의 언어로 더 체계화된다.

network flows나 graph minors frontier에서도 무작위 construction과 probabilistic existence는 sparse structure와 obstruction을 만드는 데 자주 쓰인다.

연습문제

  1. $G(n,p)$ 의 기대 간선 수를 계산하라.
  2. $G(n,p)$ 의 기대 triangle 수를 계산하라.
  3. 고정 그래프 $H$ 의 copy 기대 개수를 어떻게 세는지 설명하라.
  4. Markov 부등식을 기대값 정의에서 증명하라.
  5. 단색 $K_k$ 기대 개수 $\binom nk2^{1-\binom k2}$ 를 유도하라.
  6. 기대 단색 $K_k$ 수가 1보다 작으면 $R(k)>n$ 임을 설명하라.
  7. deletion method가 왜 큰 girth를 만드는지 설명하라.
  8. 독립수 상계가 왜 색수 하계를 주는지 보이라.
  9. local lemma가 first moment보다 필요한 상황을 예로 설명하라.
힌트 / 정답
  1. 가능한 간선마다 indicator를 두면 각 기대값이 $p$ 이므로 $\binom n2p$.
  2. 가능한 3정점 집합마다 triangle indicator를 두면 각 기대값이 $p^3$ 이므로 $\binom n3p^3$.
  3. $H$ 의 labeled embedding 후보 수를 세고, 필요한 간선들이 모두 선택될 확률 $p^{e(H)}$ 를 곱한다. automorphism 중복을 조심하라.
  4. $\mathbb E[X]=\sum X(\omega)P(\omega)\ge\sum_{X\ge a} aP(\omega)=aP(X\ge a)$.
  5. 고정 $k$-집합의 모든 간선이 빨강일 확률은 $2^{-\binom k2}$, 모두 파랑도 같으므로 두 배다.
  6. 단색 $K_k$ 수를 $X$ 라 하면 $\mathbb E[X]<1$ 이므로 $X=0$ 인 coloring이 존재한다.
  7. 각 짧은 cycle에서 정점 하나를 제거하면 그 cycle은 사라진다. 모든 짧은 cycle을 한 번씩 처리하면 남은 그래프에는 짧은 cycle이 없다.
  8. $k$색칠이 있으면 가장 큰 색 class 크기가 적어도 $|V|/k$ 다. 따라서 $\alpha(G)<|V|/k$ 이면 $k$색칠 불가능.
  9. bad event가 많아 전체 기대 개수는 크지만, 각 event가 제한된 이웃 event와만 의존하는 constraint coloring 문제가 전형적이다.

관련 개념

각주

  1. diestel §11.2 [synthesis] — probabilistic method의 기본 아이디어와 Erdős의 large girth high chromatic theorem. ↩

  2. diestel §11.1 [synthesis] — random graph $G(n,p)$, 확률변수, 기댓값, Markov 부등식. ↩

  3. diestel §11.1, Theorem 11.1.3 [synthesis] — Erdős의 Ramsey number lower bound $R(k)>2^{k/2}$. ↩

  4. diestel §11.2, Theorem 11.2.2 and Corollary 11.2.3 [synthesis] — 큰 girth와 큰 chromatic number를 갖는 그래프의 확률적 존재 증명. ↩

  5. [synthesis] — Lovász local lemma는 Diestel raw text grep에서 별도 정리로 확인되지 않아 표준 확률적 방법의 안내 수준으로만 언급했다. ↩