인상 깊었던 MO 문제 #3: RMM 2019 3번

문제

임의의 주어진 양의 실수 \(\epsilon\)에 대하여, 모든 충분히 큰 \(v\)에 대하여 다음이 성립함을 보여라.

\(v\)개의 정점을 가진 그래프가 \((1+\epsilon)v\)개 이상의 간선을 가진다면, 같은 길이를 가지는 두 distinct simple cycle을 갖는다.  

스포 방지선

__________________________________________________________________________________________________________

___________________________________________________________________________________________________________

아는 풀이만 3개다. 각자 다른 맛을 가지고 있으니 다 읽어보자.

풀이 1. (Probabilistic)

서로 다른 simple cycle of equal length가 없는 그래프에 대해서 \(|E|\)를 bound시키면 된다. 

간선들의 집합 \(B\)를 뽑았다고 가정하고, \(B\)에 속한 간선들을 삭제하자. 만약 남은 cycle의 개수가 \(f(B)\)개라면, \(|B|+f(B)\)개의 간선을 삭제하여 cycle-free 그래프를 만들 수 있고, 그러면 \(|E| \le |V|+|B|+f(B)\)를 얻는다. 

문제는 적당한 \(B\)를 뽑는 것이다. Probabilistic한 방법이 이런 경우에 도움이 될 수 있다. 

\(B\)를 뽑기 위해서, 각 간선이 추가될 확률을 \(\frac{1}{\sqrt{|E|}}\)로 고정하자. 각 간선의 선택 여부는 독립적이다.

기댓값의 선형성에 의해 \(E\left(|B|+f(B)\right) = E(|B|)+E(f(B))\)이다. \(E(|B|)=\sqrt{|E|}\)는 자명하다. 

각 cycle이 \(B\)에서 속한 간선을 모두 제거했을 때에도 살아남은 조건은 그 cycle에 속한 모든 간선이 \(B^C\)에 속할 경우이다. 

각 길이를 가지는 cycle은 최대 하나이므로, 결국 \(\displaystyle E(f(B)) \le \sum_{k=3}^\infty \left(1-\frac{1}{\sqrt{|E|}} \right)^k \le \sqrt{|E|}-1\)이다. 

종합하면 \(E \left(|B|+f(B)\right) \le 2\sqrt{|E|}-1\)이다. 그러니 \(|B|+f(B) \le 2\sqrt{|E|}-1\)인 집합 \(B\)가 있다.

이 \(B\)를 통해서, \(|E| \le |V|+2\sqrt{|E|}-1\)를 얻을 수 있고 정리하면 \(|E| \le |V|+2\sqrt{|V|}+1\)를 얻는다.

이제 증명을 마무리시키는 것은 어렵지 않다. 증명 끝. 

풀이 2. (Algorithmic #1)

이 풀이에서는 \(f(B)=0\)을 만족하는 크기가 작은 \(B\)를 더욱 explicit하게 construct한다. 

먼저, 주어진 그래프에서는 최소 \(|E|-|V|\)개의 cycle이 존재하고, 그 길이는 서로 다르므로 \(|E|-|V| \le |V|\)다.

이제 \(B\)를 greedy하게 construct하자. 각 간선 중 가장 많은 cycle에 존재하는 간선을 하나 선택하고, 그 간선을 삭제하는 것을 반복한다. 이 알고리즘이 최대 \(10\sqrt{|V|}\)번의 삭제를 함을 보이자. 즉, \(|B| \le 10\sqrt{|V|}\)를 보이자.

현재 \(x\)개의 cycle이 있다면, 그 길이의 합은 최소 \(\sum_{i=1}^x (i+2) > \frac{1}{2}x^2\)이다.

그러므로, 더블카운팅 느낌으로 생각하면 \(\frac{x^2}{2|E|} \ge \frac{x^2}{4|V|}\)개 이상의 cycle에 존재하는 간선이 있다. 

즉, 한 번 간선을 삭제할 때마다 최소 \(\text{min}(\frac{x^2}{4|V|},1)\)개의 cycle이 삭제된다. 물론 처음에 \(x \le |V|\)이다. 

이제 이 문제는 대수문제다. 알고리즘을 진행하면서, cycle의 개수가 \([k\sqrt{|V|}, (k+1)\sqrt{|V|})\)에 속한 횟수를 \(c_k\)라 하자. 

\(k \ge 1\)이면 \(c_k \le \frac{\sqrt{|V|}}{k^2/4}+1 = \frac{4 \sqrt{|V|}}{k^2}+1\)이고, \(c_0 \le \sqrt{|V|}+1\)이다. (cycle의 개수가 최소 \(\frac{k^2}{4}\) 또는 1개씩 감소)

가능한 \(k\)의 범위는 \(1 \le k \le \lfloor \sqrt{|V|} \rfloor\)이므로, 전체 삭제 횟수는 $$ -1+\sum_{k=0}^{\lfloor \sqrt{|V|}\rfloor} c_k  \le \sqrt{|V|} + \sum_{k=1}^{\lfloor \sqrt{|V|} \rfloor} \left( \frac{4\sqrt{|V|}}{k^2} + 1 \right) \le 2\sqrt{|V|} + 4 \sum_{k=1}^\infty \frac{\sqrt{|V|}}{k^2} \le 10 \sqrt{|V|} $$다. 이제 풀이 1과 똑같은 방법으로 마무리할 수 있다. 증명 끝.

풀이 3. (Algorithmic #2)

접근 방법이 많이 다른 풀이다. 앞서 cycle의 길이가 최대 \(|V|\)인 것을 활용하여 \(|E|-|V| \le |V|\)임을 유도했다. 

만약 그래프의 일부 간선을 삭제하여 diameter가 작은 그래프 여러 개로 분할하면, 그 그래프들에서 나올 수 있는 cycle의 길이는 더욱 tight하게 bound된다. 특정 길이를 가지는 cycle이 최대 하나이므로, 여기서 쪼개진 그래프들이 가질 수 있는 간선의 개수를 bound시킬 수 있을 것이다. 문제는 어떻게 적은 수의 간선을 제거해 diameter가 작은 그래프를 만드냐는 것이다. 

Theorem. (Low Diameter Decomposition) 

\(N\)개의 정점과 \(M\)개의 간선을 가지는 그래프 \(G\)가 있다고 가정하자. 

\(\delta M\)개의 간선을 삭제하여, 남은 connected component의 diameter가 전부 \(\mathcal{O}(\delta^{-1} \log N)\)이도록 할 수 있다. 

(증명) 다음 알고리즘을 반복한다. 

정점 \(v\)를 고정하고, \(B_r\)을 \(\text{dist}_G(v,w) \le r\)인 정점 \(w\)의 집합이라 한다.

또한, \(E(B_r)\)을 \(B_r\) 내부에 존재하는 간선의 개수라고 정의한다. 

\(E(B_r) \le (1+\delta)E(B_{r-1})\)을 만족하는 최소의 \(r\)을 선택한다. 

만약 모든 \(1 \le t \le R\)에 대하여 \(E(B_t) > (1+\delta)E(B_{t-1})\)이 성립한다면, $$ M \ge E(B_R) > (1+\delta)^{R-1} E(B_1) \ge (1+\delta)^{R-1} $$이므로 \(R \le 1+\frac{\log M}{\log (1+\delta)}\)이다. 즉, 최소의 \(r\)은 최대 \(1+\frac{\log M}{\log (1+\delta)} = \mathcal{O}(\delta^{-1} \log N)\)이다. 

이제 \(E(B_r)-E(B_{r-1})\)개의 간선을 삭제하여 \(B_{r-1}\)을 새로운 connected component로 받아들인다.

이를 계속해서 반복한다. 각 stage에서 삭제되는 간선은 최대 \(\delta E(B_{r-1})\)개이다. 

\(B_{r-1}\)은 서로 disjoint한 집합들이므로, 이들의 합은 최대 \(\delta M\)이다. 증명 끝. 

적당히 작은 \(\epsilon\)에 대해서만 생각해도 좋다. 

\(\delta = \frac{\epsilon}{2}\)라 하고 위 알고리즘을 적용하자. 삭제된 간선은 최대 \( \frac{\epsilon}{2} (1+\epsilon)v < \frac{2}{3} \epsilon v\)개다. 

그 후, 각 connected component의 spanning tree를 하나씩 잡아주자. 

그러면 삭제되지도 않았고, spanning tree에도 포함되지 않은 간선은 최소 \(\frac{1}{3}\epsilon v\)개다.

이러한 간선들은 해당 connected component에서 cycle을 만들어주며, 그 길이는 최대 \(\mathcal{O}(\epsilon^{-1} \log v)\)이다. 

cycle의 개수는 최소 \(\frac{1}{3}\epsilon v\)개다. \(\frac{1}{3} \epsilon v >> \epsilon^{-1} \log v\)라면, 비둘기집의 원리에서 같은 길이를 가진 cycle이 생긴다. 

\(v\)가 충분히 큰 값을 가지면, 위 부등식이 성립하게 된다. 증명 끝. 이 방식은 \(v+\mathcal{O}(\sqrt{v \log v})\) 정도의 bound를 준다.

cf. 참고로 풀이 1, 2에서 얻은 \(v+\mathcal{O}(\sqrt{v})\)의 bound는 tight하다. 

길이가 \(3,4, \cdots n\)인 cycle을 준비한 뒤, 하나의 chain으로 붙여주면 된다.