Permutation $\pi : [n] \to [n]$에 대해 Displacement를 $D(\pi) = \sum_{i=1}^{n} \lvert i - \pi (i) \rvert$로 정의한다. 주어진 양수 $k$에 대해, $D(\pi) = 2k$를 만족하는 짝순열의 개수를 $E_{k}$, 홀순열의 개수를 $O_{k}$라 두면 $E_{k} - O_{k} = (-1)^{k}\binom{n-1}{k}$임을 보여라. ...
$[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가 존재하지 않음을 보인다. ...
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면 위 성질을 만족한다는 것을 보장하고 있다....
$\mathbb{C}$의 open unit disk $\mathbb{D}$에 대해, holomorphic function $f : \mathbb{D} \to \mathbb{D}$를 생각하자. Schwarz Lemma는 이러한 $f$의 성질에 대한 Lemma이고, 이는 $\mathbb{D}$의 Automorphism group을 characterize하는 데 큰 도움을 준다. Lemma (Schwarz) $f : \mb{D} \to \mb{D}$가 holomorphic이고, $f(0) = 0$을 만족한다고 하자. 다음 세 성질이 성립한다. $\abs{f(z)} \le \abs{z}$. 만약 $z_0 \neq 0$에 대해 $\abs{f(z_0)} = \abs{z_0}$가 성립한다면, $f$는 rotation. $\abs{f’(0)} \le 1$. 등호가 성립한다면 $f$는 rotation. 증명은 기초 복소해석을 공부했다면 크게 어렵지는 않다....