Processing math: 100%

문제

(Graham, Pollak 1972) Prove that the edge set of Kn cannot be partitioned into the edge-disjoint union of less than n1 complete bipartite subgraphs. Also, prove that this bound is tight.


스포 방지선

________________________________________________________________________________________________________________________















________________________________________________________________________________________________________________________


(증명) Kn의 각 정점을 1,2,,n이라 하자. 우선 n1개의 완전 이분 그래프로 Kn을 분할하는 것은 쉽다. 

귀류법으로, 완전 이분 그래프 B1,B2,BmKn을 분할한다고 하자. (단, mn2다.)

또한, 각 완전 이분 그래프 Bk 안에서 두 disjoint independent set을 Lk,Rk라고 부르자.

즉, Bk의 간선은 Lk의 정점과 Rk의 정점 사이를 모두 연결한 것이다.


다음 조건을 만족하도록 Kn의 정점 v에 실수 xv를 놓자. 


조건 1: 모든 1km에 대하여, vLkxv=0이고, nv=1xv=0 

조건 2: nv=1x2v0이다. 즉, 모든 v에 대해 xv가 전부 0은 아니다.


이것이 가능함을 보이자. 기초적인 선형대수학을 알면 쉽게 보일 수 있다.

조건 1은 식의 개수가 m+1개인 하나의 Homogeneous한 연립방정식을 이룬다. 

변수의 개수가 n개이고 m+1<n이므로, 이 연립방정식은 non-trivial 해를 가진다. 

그러므로 조건 1, 2를 만족하도록 정점 v에 실수 xv를 놓을 수 있다. 


이제 B1,B2,BmKn의 edge set을 완벽하게 분할하므로, 다음 식이 성립한다.


1i<jnxixj=mk=1(iLkxi)(jRkxj)


이제 조건 1에 의해, 우변은 0이다. 그러면 결국 1i<jnxixj=0인데, 다시 조건 1에서 nv=1xv=0이다.
이 식을 제곱하고 정리하면 nv=1x2v=0을 얻고, 이는 조건 2와 모순이다.


'수학 > 기타 재밌는 것들' 카테고리의 다른 글

Ramsey Number of a Tree and a Complete Graph  (0) 2019.12.14