leejseo의 블로그

Theorem. 그래프 $G$가 이분그래프임과 $G$가 홀수 길이의 사이클을 포함하지 않음은 동치이다. Proof. $G$가 이분그래프이면 홀수 길이의 사이클을 포함하지 않음은 명백하다. $G$가 홀수 길이의 사이클을 포함하지 않는다고 하자. $G$가 여러개의 컴포넌트로 이루어져 있다면, 각 컴포넌트를 따로 고려해주면 된다. 따라서, $G$가 연결그래프임을 가정할 수 있다. 이제, $G$가 연결그래프이므로, $G$의 spanning tree $T$를 잡을 수 있다. $T$ 상의 아무 정점에서나 시작해서 dfs를 하며 2-coloring을 해줄 수 있다. 만약, $G$의 어느 간선이 색이 같은 두 정점 $u, v$를 잇는다면, $T$ 상의 $u, v$를 잇는 경로와 해당 간선으로 이루어진 사이클은 길이가 ..

그래프 상의 고정된 크기의 클릭의 수에 대하여 아래와 같이 아름다운 관계식이 성립한다. Theorem. 그래프 $G = (V, E)$에 대하여 크기가 $n$인 클릭의 수를 $a_n$으로 표기하고, $b_n = \sqrt[n]{n! a_n}$으로 정의하자. 이 때, $\{b_n\}_{n > 0}$은 감소수열이다. proof.$P(k)$를 임의의 $G$에 대하여 $b_1, b_2, \cdots , b_k$가 감소한다 로 정의하고, $k$에 대한 수학적 귀납법을 적용하자.먼저, $a_1 \geq a_2$가 됨은 매우 명확하다.$P(k)$가 참이라 가정하고, 임의의 $G = (V, E)$가 주어졌다고 하자.$|V| = n$이라 할 때, 각각의 정점을 $[n]$의 원소에 대응시켜 표현하자. 다음과 같이 표기법을 ..

문제. Order가 $n$인 Projective Plane $(\mathcal{P}, \mathcal{L})$이 주어졌다고 가정하자. 이 때, 몇몇 점들의 집합 $A$가 - 어떠한 직선도 포함하지 않고,- 모든 직선과 교차점을 가지면$A$를 $(\mathcal{P}, \mathcal{L})$의 Blocking Set이라 한다. $|A| = m$이라 할 때, $m \geq n + \sqrt{n} + 1$임을 보여라. 증명.집합 $S$를 $A$에 속하지 않는 점 $p$와 $A$에 속하는 서로 다른 두 점 $q, q^{\prime}$으로 이루어진 순서쌍 $(p, q, q^{\prime})$ 가운데 세 점이 일직선 상에 있는 것들의 모임으로 정의하자. 이제, $|S|$의 상한과 하한을 구해볼 것이다. 편의상, ..

문제. 평면 상에 어느 세 점도 일직선 상에 있지 않은 $2N$개의 점들이 있다. 이들 중 $N$개의 점은 빨간색, 나머지 $N$개의 점은 파란색으로 칠해져 있다고 한다. 빨간 점과 파란 점을 하나씩 짝지어 총 $N$개의 선분을 그으려 한다. 이 때, $N$개의 선분들이 서로 교차하지 않도록 하는 것이 가능함을 보여라. 풀이를 진행하기에 앞서, 그림의 퀄리티에 대한 양해를 부탁드립니다. 풀이 1. $N$에 대해 귀납법을 적용하자. $N=1$인 경우, 명확하다. $N=n-1$인 경우 성립한다고 가정하자.이제, $n$개의 빨간 점과 $n$개의 파란 점이 있다고 하자. 만약, 이들의 볼록껍질 상에 빨간 점과 파란 점이 모두 존재한다면, 인접한 빨간 점과 파란 점을 이어주면, 귀납 가설에 의해 증명이 종료된다...

문제. 평면 상에 놓인 $n$개의 점들로 구성된 집합 $A$가 있다. 다음을 증명하여라.$$ | \left \{ (a, b) \in A^2 : d(a, b) = 1 \right \} | \leq O(n^{3/2}) $$ 풀이.각각의 $a \in A$에 대하여 $a$로 부터 거리가 1인 점의 수를 $f(a)$로 정의하자. 그러면, 평면상에서 (서로 다른 두 점으로 부터) 거리가 모두 1인 점의 수가 많아야 2개라는 사실에 착안하여 다음의 부등식을 얻을 수 있다.$$ \sum_{a \in A} {f(a) \choose 2} \leq {n \choose 2} $$따라서,$$ \sum_{a \in A} f(a)^2 \leq n(n-1) + \sum_{a \in A} f(a)$$를 얻게 되고, 코시-슈바르츠 부등..

Theorem. $A$가 $[n]$의 몇몇 부분집합들로 이루어진 집합이라고 하자. 모든 $A$의 원소는 크기가 $r$이고, 임의의 두 $x, y \in A$에 대해 $x \cap y \neq \emptyset$이다. 이 때, $A$의 크기는 $\pmatrix{ n-1 \\ r-1 }$ 이하이다. (이 때, $ n \geq 2r$이다.) Proof. 이 정리에 대한 증명은 단순한 더블카운팅으로 가능하다. $[n]$과 $A$가 주어졌다고 가정하자. 이제, 우리는 원주상에 $[n]$의 원소들을 cyclic order로 배열을 하고, $A$에서 길이가 $r$인 구간들에 대해 생각할 것이다. 예를 들어, $n = 6$이고 $r = 2$이고, cyclic order $(1, 5, 4, 2, 3, 6)$을 택한 경우..

문제. 수직선 상에서 $n$개의 구간(interval) $I_1 , I_2 , \cdots , I_n$이 있는데, 그 가운데서 어떻게 $k$개를 뽑든지 교집합이 공집합이 아닌 2개의 구간이 존재한다고 한다. 이 때, $k-1$개의 실수들의 집합 $S$가 존재해서 모든 $1 \leq i \leq n$에 대하여 $I_i \cap S$가 공집합이 아니게 할 수 있음을 보여라. 풀이.먼저, 이 구간들 사이의 관계 $\prec$를 다음과 같이 정의하자: 두 구간 $I$, $J$에 대하여 $I \prec J$임은 $\forall x \in I , \forall y \in J, x < y$를 만족하는 것으로 정의하자. 문제의 조건으로 인해 우리는 길이가 $k$ 이상인 chain을 찾을 수 없다. 즉, maximal ..