완전그래프의 완전이분그래프 분할문제

n명의 사람들로 이루어진 눈싸움 동아리가 있다. 이 동아리는 하루에 한 번씩, 한 명 이상이 모인 팀 두 개를 결성해 서로 눈싸움을 한다고 한다. (하루에 전원이 참가할 필요는 없다) 총 m일 동안 어떤 두 사람을 뽑아도 그들은 정확히 한 번 적으로서 눈싸움을 했다고 한다. m의 최솟값은?

비유하느라 약간 문제 설명이 길어졌는데, 간단히 표현하자면 완전그래프 K_n(n개의 꼭지점이 있고 모든 쌍을 변으로 연결한 그래프)의 변들을 완전이분그래프 K_p,q(각각 p,q개의 꼭지점으로 이루어진, 점집합의 서로 겹치지 않는 두 부분집합 A,B 사이의 모든 변을 연결한 그래프, 단 AB의 내부에는 변이 없다)로 분할할 때 그 개수 m의 최솟값이 무엇인지를 묻는 문제. 1971년 Graham과 Pollak의 네트워크에서의 루프 스위칭에 대한 논문[1]에 등장한 정리이다. 매우 기초적인 선형대수학을 이용해 짧게 증명하는 Tverberg의 풀이가 유명하다.[2]

답은 n-1이다. m=n-1일 때 실제로 가능한 예는, i번째 날 i번째 사람 한 명으로 이루어진 팀과 i+1,i+2, \ldots,n번째 사람으로 이루어진 팀이 눈싸움을 하는 것으로 잡을 수 있다.

귀류법 가정으로 m \leq n-2라고 가정한다. 먼저 사람들을 편의상 1,2, \ldots,n이라 하고, i번째 날의 두 팀을 각각 A_i,B_i란 집합으로 둔다. 그러면 임의의 실수 변수 x_1,x_2, \ldots ,x_n에 대해 다음과 같은 식이 성립하게 된다.

\displaystyle \sum_{1 \leq k<l \leq n} x_k x_l = \sum_{i=1}^m \left( \sum_{a \in A_i} x_a \right) \left( \sum_{b \in B_i} x_b \right)

왜냐하면, 우변의 두 시그마의 곱을 전개하면 i번째 날 싸우는 모든 쌍 a,b에 대해 x_a x_b란 항이 한 번씩 등장하게 되고 우변은 그런 항들을 전부 합한 것이 되어 임의의 두 사람 k,l에 대해 x_k x_l이 한 번씩 합해진 식이 되는데, 그게 바로 좌변과 같기 때문이다.

한 편, 귀류법 가정에 의해 m+1 < n이기 때문에 벡터공간 \mathbb{R}^n에서 다음의 m+1개의 식을 만족하는 (0,0, \ldots,0)이 아닌 해 (x_1,x_2, \ldots,x_n)을 잡을 수 있다. 흔히들 표현하는, 식의 개수가 변수의 개수보다 적으면 비자명해가 존재한다는 이야기.

\displaystyle \begin{aligned} x_1+x_2+\cdots+x_n =& 0 \\ \sum_{a \in A_1} x_a =& 0 \\ \vdots & \\ \sum_{a \in A_m} x_a =& 0 \end{aligned}

위 연립방정식을 만족하는 x_1,x_2, \ldots,x_n을 잡는다. 그러면 다음과 같이 모순이 발생하게 되어 증명이 끝난다.

\displaystyle \begin{aligned} 0 =& \sum_{i=1}^m \left( \sum_{a \in A_i} x_a \right) \left( \sum_{b \in B_i} x_b \right) = \sum_{1 \leq k<l \leq n} x_k x_l \\ =& \frac{1}{2} \left( \sum_{k=1}^n x_k \right)^2 - \frac{1}{2} \left( \sum_{k=1}^n x_k^2 \right) = - \frac{1}{2} \left( \sum_{k=1}^n x_k^2 \right) < 0 \end{aligned}

참고로 이 풀이를 변형하면 조합적인 풀이로 바꿀 수 있다.[3] 역시 마찬가지로 m \leq n-2를 가정한다. 1 이상 k 이하인 자연수 x_1,x_2, \ldots,x_n에 대해 앞에서 잡은 합들로 이루어진 (m+1)-tuple (x_1+x_2+\cdots+x_n,\sum_{a \in A_1}x_a,\ldots,\sum_{a \in A_m}x_a)을 생각한다. x_1,x_2, \ldots,x_n을 택하는 경우의 수는 k^n인데, 이 tuple은 각각의 항이 1 이상 kn 이하이므로 나타날 수 있는 경우의 수는 (kn)^{m+1} \leq (kn)^{n-1}보다 작거나 같게 된다. 그런데 충분히 큰 k에 대해 k^n > (kn)^{n-1}이므로, 비둘기집 원리에 의해 같은 tuple을 갖는 서로 다른 x_1,x_2, \ldots,x_ny_1,y_2, \ldots,y_n을 잡을 수 있다. 이 때 z_i=x_i-y_i들에 대해 앞 풀이의 식을 그대로 적용하면 모순이 된다. 결국 dimension에 대한 이야기를 degree에 대한 이야기로 바꿔 선형대수학의 언어를 없앴지만 사실상 앞 풀이와 거의 동일하다고 볼 수 있다.

이 문제는 Witsenhausen이 발견한 정리의 한 따름 정리인데, 애초에 [1]에서도 소개됐었다. 일반적인 그래프 G에 대해, 그 adjacency matrix A의 eigenvalue들 중 양수의 개수를 n_+, 음수의 개수를 n_-라 하면 Gm개의 완전이분그래프로 분할했을 때m \geq \max(n_+,n_-)이라는 정리. 완전그래프의 경우 eigenvalue는 n-1 하나와 n-1개의 -1이므로 m \geq n-1을 얻을 수 있다.

Tait의 survey paper에서 소개된 증명은 다음과 같다. 점집합의 부분집합 S에 대해 S의 특성 벡터를, 점 iS에 속하면 i번째 좌표가 1, 아니면 0이 되도록 정의된 \mathbb{R}^n의 벡터로 정의한다. A_i, B_i의 특성 벡터를 각각 u_i, v_i로 두면 D_i = u_i v_i^T+v_i u_i^Ti번째 완전이분그래프의 adjacency matrix가 되므로 A = \sum_{i=1}^m D_i가 된다.

이제 모든 u_i들과 수직인 벡터 w \in \mathbb{R}^n들로 span된 subspace를 W로 두고, (즉 w^T u_i=0) A의 양수 eigenvalue에 해당되는 eigenvector들로 span된 subspace를 P로 둔다. Wm개의 벡터로 span되는 subspace의 orthogonal subspace이므로 \dim (W) \geq n-m이다. 한 편, 0 \neq p \in P에 대해 p^T A p>0이 성립하므로, 만약 p \in W였다면 p^T u_i = u_i^T p =0이므로 p^T A p = \sum_{i=1}^m p^T u_i v_i^T p + p^T v_i u_i^T p = 0에서 모순이어야 한다. 즉 W \cap P = \{0\}이므로 \dim (W) \leq n-\dim(P) = n-n_+를 얻어 n-m \leq \dim(W) \leq n-n_+, 즉 m \geq n_+가 된다. 마찬가지로 m \geq n_-도 얻을 수 있어 증명이 끝난다. Tverberg의 증명의 일반화가 된다는 것을 알 수 있다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/03/04)

References

[1] R. L. Graham and H. O. Pollak, “On the Addressing Problem for Loop Switching” Bell System Tech. J., 50 (1971), pp. 2495-2519. http://www.math.ucsd.edu/~ronspubs/71_05_loop_switching.pdf

[2] H. Tverberg, “On the decomposition of K_n into complete bipartite graphs” J. Graph Theory, Vol. 6, 1982, pp. 493-494. DOI: 10.1002/jgt.3190060414

[3] S. Vishwanathan, “A Counting Proof of the Graham Pollak Theorem” arXiv preprint arXiv:1007.1553

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중