크기가 $n \times n$인 실대칭행렬 $A = (a_{ij})$에 대해 $i \neq j \implies a_{ij} \le 0$을 만족하고, $A$의 모든 고윳값이 음이 아닌 실수이다. (positive-semidefinite) $n \ge 2$라고 할 때, 다음 물음에 답하여라. $\ker A = \set{v \in \mathbb{R}^{n} : v^{t}Av = 0}$ $[n] = \set{1, \cdots, n}$의 nonempty partition $I, J$에 대해, 항상 $a_{ij} < 0$인 $i \in I$, $j \in J$가 존재한다고 하자. 이 때, $\dim \ker A \le 1$임을 보여라....
Simplicial Complex에서 Alexander Duality는 다음과 같다. $ \tilde{H_{i}}(A) \simeq \tilde{H}^{n-i-1}(S^{n} \setminus A) $ 이 글에서는 그 Combinatorial Variant와 Björner & Tancer (2007)의 증명을 다룬다. 모든 set은 finite set이라고 가정한다. 또한, Alexnader Duality의 응용 등에 대해서는 다루지 않는다. 기본적으로 공부 도중에 기록을 위해 만든 post이기 때문에 내용이 추후 가감될 수 있다. Alexander Dual Vertex set $V$ 위에 정의된 Simplicial Complex $\Delta$ 에 대해, Alexander Dual $\Delta^{\ast}$는 같은 Vertex Set 위에서 다음과 같이 정의된다....
수직선상에 깃발 $N$개를 놓되, $i$번째 깃발은 $x_i$ 또는 $y_i$에 놓아야 한다. 이 때 깃발들 사이의 최소 거리의 최댓값을 구하는 문제이다. 문제 링크 Solution sketch 일단 파라메트릭 + 2-SAT을 해야 한다는 것 까지는 자명한 관찰이다. 즉, “가장 가까이 있는 깃발이 $d$ 이상 떨어져 있게 할 수 있는가?”에 관한 문제를 풀자. 그런데 2-SAT에 사용할 그래프 에지를 단순하게 만들면 $O(N^2)$개가 된다. Idea 1. 2-SAT Segment Tree 편의상 $x$좌표들을 정렬된 순서대로 $p_{1}, p_{2}, \cdots, $라 두자....
Arzela-Ascoli theorem을 따로 알아야 할 상황이 생겨서, 해석개론에서 약간의 지름길을 타서 이 정리를 건드려보기로 했다. Compactness에 대한 통찰을 요구한다. Ref: 김성기, 김도한, 계승혁 - 해석개론 $N_{\varepsilon}(x) := \set{y \mid \norm{x - y} < \varepsilon }$. 무엇의 부분집합인지는 context에 의존한다. Uniformly continuous function 함수 $f$가 정의역 $X$에서 uniformly continuous하다는 말은, given $\varepsilon > 0$에 대해 $ \exists \delta ; \forall x, y \in X \quad \norm{x-y} < \delta \implies \norm{f(x) - f(y)} < \varepsilon $ 를 만족한다는 것을 말한다....
조합론에서의 Cayley’s theorem은 완전그래프 $K_{n}$의 서로 다른 spanning tree가 $n^{n-2}$개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다. Reference : Miklos Bona - [A Walk through Combinatorics] cf : $[n] := \set{1,\dots,n}.$ Proof of the theorem (By A. Joyal) $K_{n}$의 spanning tree의 개수를 $t_{n}$이라고 두고, $n^{2}t_{n} = n^{n}$임을 보인다. Definition. 정점 $n \ge 1$개의 트리 $T$에서 정점 $a, b$를 골라 $a$를 start, $b$를 end로 부르자....