$[n] = \set{1, \cdots, n}$과 $2 \le 2k \le n$에 대해, Kneser graph $\mar{KG}(n, k)$는 $\binom{[n]}{k}$를 정점 집합으로 하고, $S \cap S’ = \emptyset$인 모든 $S, S’$에 대해 간선을 이어준 그래프로 정의된다. Lovasz-Kneser Theorem (Kneser’s conjecture)란 이 그래프의 chromatic number $\chi(\mar{KG}(n, k)) \ge n - 2k + 2$가 성립한다는 정리이다. 이 글에서는 Tucker’s lemma를 이용한 J. Matousek의 증명을 소개한다. ...
Space-filling curve는 일반적으로 $I := [0,1]$에서 $I \times I$로 가는 continuous onto function을 말한다. Hilbert’s curve, Sierpinski’s curve 등 여러 가지가 알려져 있다. 이런 curve들의 특징은 uniformly converge하는 연속함수열의 극한으로 정의된다는 점인데, 그렇지 않고는 Space Filling Curve를 만들기 굉장히 어렵기 때문이다. 이 포스팅에서는 $C^{1}$ class의 space-filling curve가 존재하지 않음을 보인다. ...
rkm0959, jhhope1이랑 진행한 문제풀이의 간략한 풀이. 스포일러에 주의하자. BOJ 15313. 정과프 해적단 $[l, r]$ 값이 없는 문제는 좌표압축 + 세그먼트 트리를 이용한 dp로 $O(n\log n)$에 해결할 수 있다. 이 때 $l$이 증가할수록 조건을 만족하기 위해 필요한 최소의 $r$도 증가하므로 inchworm을 얹어주면 $O(n^{2}\log n)$이 된다. BOJ 15504. 프로그래밍 대결 제일 실력이 높은 선수를 제외하고, 각 선수마다 ‘자신을 이기는 선수’를 정해주면 스패닝 트리가 유일하게 결정된다. 해당 작업을 mcmf로 모델링하면 $O(n^{4})$. 늘 그렇듯 플로우 문제에서 시간복잡도는 아무 의미 없다....
교육용으로 사용한 10문제의 풀이입니다. 용어가 원본 문제와 다를 수 있습니다. BAPC 2021 F. “Fair Play” $n$이 홀수인 경우는 당연히 불가능하고, 짝수인 경우 $(b, p)$를 std::pair 와 같은 방식으로 정렬한 것을 $(b_{1}, p_{1}), \cdots, (b_{n}, p_{n})$이라고 둡시다. 이 때 유일하게 가능한 매칭 방법은 $(b_{1}, p_{1})$을 $(b_{n}, p_{n})$과, $(b_{2}, p_{2})$를 $(b_{n-1}, p_{n-1})$과 … 매칭해주는 것입니다. 이렇게 해서 벡터합이 모두 균일하다면 possible, 그렇지 않다면 impossible 입니다. BAPC 2021 I “Implementation Irregularities” $s_{i}$가 증가하는 순서대로 원소들을 배열하고, $s_{i} = -1$인 원소들을 제외합시다....
Riemann Mapping은 $\mathbb{C}$의 모든 simply connected proper subset $\Omega$에 대해, Conformal map $f : \mathbb{D} \to \Omega$가 존재한다는 매우 강력한 정리이다. 여기서는 짧고 아름다운 nonconstructive한 증명을 다룬다. Ref: Stein & Shakarchi, Complex Analysis Ch.8 Montel’s theorem 어떤 함수열 $\ev{f_n}$이 수렴하는 부분수열 $\ev{f_{n(k)}}$를 갖는다는 사실은 매우 유용하다. 물론 여기서 수렴은 모든 cpt subset에 대한 uniform convergence를 의미한다. Arzela-Ascoli Theorem의 경우, 정의역이 cpt set인 연속함수들의 함수족 $\mc{F}$가 uniformly bdd, equicontinuous면 위 성질을 만족한다는 것을 보장하고 있다....