티스토리 뷰

그래프 상의 고정된 크기의 클릭의 수에 대하여 아래와 같이 아름다운 관계식이 성립한다.


Theorem. 그래프 $G = (V, E)$에 대하여 크기가 $n$인 클릭의 수를 $a_n$으로 표기하고, $b_n = \sqrt[n]{n! a_n}$으로 정의하자. 이 때, $\{b_n\}_{n > 0}$은 감소수열이다.


proof.

$P(k)$를 임의의 $G$에 대하여 $b_1, b_2, \cdots , b_k$가 감소한다 로 정의하고, $k$에 대한 수학적 귀납법을 적용하자.

먼저, $a_1 \geq a_2$가 됨은 매우 명확하다.

$P(k)$가 참이라 가정하고, 임의의 $G = (V, E)$가 주어졌다고 하자.

$|V| = n$이라 할 때, 각각의 정점을 $[n]$의 원소에 대응시켜 표현하자. 다음과 같이 표기법을 정의하자:

- 정점 $i$와 모든 정점이 인접한 $t$-클릭의 수를 $f(i, t)$로 표기한다.

- 정점 $i$와 인접한 정점들의 집합을 $V_i$로 표기한다.

- 집합 $E_i$를 $E_i = \{ (u, v) \in E : u, v \in V_i \}$로 정의하자.

- $G_i = (V_i, E_i)$로 정의하자.

$f(i, k)$의 상한을 생각해보면, 귀납 가설로 부터 $f(i, k)^{(k-1)/k} \leq (k-1)! f(i, k-1)/(k!)^{k-1/k}$를 얻을 수 있고, $f(i, k) \leq a_i$임 또한 명확하다. 

$(k+1)a_{k+1} = \sum_{i \in [n]} f(i, k)$에 이 사실들을 적용하면, $(k+1) a_{k+1} \leq (k!)^{1/k} a_k^{k+1/k}$를 얻으며, 양변에 $k!$을 곱하고, $(k+1)$-제곱근을 취해주면, $$b_{k+1} = \sqrt[k+1]{(k+1)!a_{k+1}} \leq \sqrt[k]{k!a_k} = b_k \leq b_{k-1} \cdots \leq b_2 \leq b_1$$이 되어 $P(k+1)$을 얻는다. 따라서, 수학적 귀납법에 의해 보이고자 하는 명제는 참이다.


이렇게 간단하게 얻을 수 있는 bound는 과연 tight 할까? 놀랍게도, tight 하다! $K_n$에서 $n \to \infty$인 경우를 생각해보면 알 수 있다.

'수학 > 이산수학' 카테고리의 다른 글

두 가지 조합기하 문제들  (0) 2019.11.15
이분그래프가 될 조건  (0) 2019.09.06
고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
2N개의 점들  (0) 2018.01.01
그들 사이의 거리  (0) 2017.09.18
댓글
댓글쓰기 폼