leejseo의 블로그

그래프 상의 고정된 크기의 클릭의 수에 대하여 아래와 같이 아름다운 관계식이 성립한다.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|$의 상한과 하한을 구해볼 것이다. 편의상, 두 ..

문제. $r < n$에 대하여 $r \times n$ 라틴 직사각형이 주어졌다고 하자. 이 때, 한 줄을 잘 추가해 $(r+1) \times n$ 라틴 직사각형으로 확장할 수 있다.증명.Hall's Theorem을 활용하기 위해 이분 그래프 $G = (V_1 \cup V_2 , E)$를- $V_1 = [n]$; 라틴 직사각형에 적히는 숫자들의 모임- $V_2 = [n]$; 새로 추가되는 $r+1$번째 행에 적히는 숫자들의 모임- 간산 $(v_1 , v_2)$는 $v_1 \in V_1$이 $r+1$번째 행의 $v_2 \in V_2$번째 칸에 적힐 수 있음을 의미함이렇게 정의하자. 그러면, $V_1$이나 $V_2$에 속하는 모든 점들의 차수는 $n-r$이다. 그렇기에, 임의의 $A \subseteq V_1$..

문제. 평면 상에 어느 세 점도 일직선 상에 있지 않은 $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 c..