티스토리 뷰

문제. 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|$의 상한과 하한을 구해볼 것이다. 편의상, 두 점 $x, y$를 지나는 직선을 $l(x, y)$로 표기하자.


Claim 1. $|S| \geq m(m-1)(2n+1-m)$이다.

먼저, $q$와 $q^{\prime}$을 잡는 경우의 수는 $m(m-1)$이다. 이제, $l(q, q^{\prime})$ 상에 있는 $A$의 원소가 몇 개인지에 대하여 생각해보자. $A$에 속하는 $m$개의 점들은 모두 $n^2 + n + 1$개의 직선과 만나야 하기에, $l(q, q^{\prime})$이 아닌 다른 직선과 만나는 점은 최소 $n$개가 된다. (Note: $n = \frac{n^2 + n}{n + 1}$) 그렇기 때문에, $l(q, q^{\prime})$ 상에는 $m-n$개의 $A$의 원소가 있음을 알 수 있고, 이것으로 부터 $p$를 고르는 경우의 수는 이것을 $n+1$에서 빼준 $2n + 1 - m$ 이상이 된다. 따라서, $|S| \geq m (m-1)(2n+1-m)$이 된다.


Claim 2. $|S| \leq (n^2 + n + 1 - m) (m - n - 1)(m-n)$이다.

$p$를 고르는 경우의 수는 $n^2 + n + 1 - m$이다. 이제, $q$를 고를텐데, $q$가 될 수 있는 점들은 $p$와 같은 직선 상의 원소인데, 이는 $m - n(n+1-1)/(n+1)$개 이하가 되고, 이것은 $m-n$ 이하 이므로 $m-n$개 이하가 됨을 알 수 있다. $q^{\prime}$이 될 수 있는 점들은 $l(p, q)$ 상에 있는 $q$가 아니면서 $A$에 속하는 점들인데, 이는 $m - (n+1 - 1) - 1 = m - n - 1$개 이하가 된다. 따라서, 위의 결과를 얻게 된다.


이제, 두 가지 사실로 부터 $m(m-1)(2n+1-m) \leq (n^2 + n + 1 - m)(m-n-1)(m-n)$을 얻게 되는데, 이것을 적절히 이항하고 인수분해 하여 부등식을 해결하면, $m \geq n + \sqrt{n} + 1$을 얻게 된다.

'수학 > 이산수학' 카테고리의 다른 글

이분그래프가 될 조건  (0) 2019.09.06
고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
2N개의 점들  (0) 2018.01.01
그들 사이의 거리  (0) 2017.09.18
Erdős–Ko–Rado 정리  (0) 2017.07.29
댓글
댓글쓰기 폼