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

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

비유하느라 약간 문제 설명이 길어졌는데, 간단히 표현하자면 완전그래프 $K_n$ ( $n$ 개의 꼭지점이 있고 모든 쌍을 변으로 연결한 그래프)의 변들을 완전이분그래프 $K_p,q$ (각각 $p,q$ 개의 꼭지점으로 이루어진, 점집합의 서로 겹치지 않는 두 부분집합 $A,B$ 사이의 모든 변을 연결한 그래프, 단 $A$ 와 $B$ 의 내부에는 변이 없다)로 분할할 때 그 개수 $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_n$ 과 $y_1,y_2, \ldots,y_n$ 을 잡을 수 있다. 이 때 $z_i=x_i-y_i$ 들에 대해 앞 풀이의 식을 그대로 적용하면 모순이 된다. 결국 dimension에 대한 이야기를 degree에 대한 이야기로 바꿔 선형대수학의 언어를 없앴지만 사실상 앞 풀이와 거의 동일하다고 볼 수 있다.

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

Tait의 survey paper에서 소개된 증명은 다음과 같다. 점집합의 부분집합 $S$ 에 대해 $S$ 의 특성 벡터를, 점 $i$ 가 $S$ 에 속하면 $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^T$ 는 $i$ 번째 완전이분그래프의 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$ 로 둔다. $W$ 는 $m$ 개의 벡터로 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)

22. n명의 사람이 하루에 한 번씩, 한 명 이상이 모인 팀 두 개가 결성되어 서로 눈싸움을 한다. (하루에 n명 모두가 참가할 필요는 없다) 총 m일 동안, 어떤 두 사람도 정확히 한 번 적으로서 눈싸움을 했다고 한다. m의 최솟값은?
— Elegant Math (@elegant_math) March 5, 2017

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

월	화	수	목	금	토	일
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28

References

이 글 공유하기:

이것이 좋아요:

관련

답글 남기기 응답 취소