티스토리 뷰

관심을 가지고 있는 조합기하 분야의 전형적인 극단(Extremal) 문제들을 모아보았다. 전부 open problem이다. 아직 잘 정리된 글은 아니다.

1. Happy Ending Problem

Problem. 평면 상의 점들의 집합 $P$가 general position 에 있다. 이는, $P$의 어느 세 점도 하나의 직선 위에 있지 않음을 의미한다. 이 때, $P$가 볼록 $n(\ge 3)$각형이 포함함이 보장되는 $|P|$의 최솟값을 구하여라.

 

이 문제에서 $|P|$의 최솟값을 $ES(n)$이라 표기하자. 작은 $n$에 대해 $ES(n)$의 값을 구해보자. $ES(3) = 3$이고, $ES(4) = 5$, $ES(5) = 9$이다. 사실, $ES(4)$와 $ES(5)$의 값 또한 자명한 결과는 아니다. $ES(4) = 5$임에 대한 증명을 간략히 언급하도록 하겠다.

 

Proposition. $ES(4) = 5$.

 

Proof. $ES(4) > 4$임은 정삼각형과 그의 외심, 이렇게 4개의 점을 생각해보면 명백하다. 이제, 임의의 5개의 점이 주어졌을 때, 볼록 사각형을 포함함을 보이자.

1) 볼록껍질이 삼각형인 경우: 삼각형을 이루는 세 점을 $P, Q, R$이라 하고, 나머지 두 점을 $A, B$라 하자. $P, Q, R$ 중 두 개의 점은 직선 $AB$에 의해 생기는 반평면 중 같은 쪽에 있다. 이 두 개의 점과 $A, B$는 볼록 사각형을 이루므로 성립한다.

2) 볼록껍질이 사각형인 경우: 자명하다.

 

그렇다면, $ES(n)$의 값은 얼마나 될까? 사실, 모든 양의 정수 $n \ge 3$에 대해 $ES(n) < \infty$임 또한 명백해보이지 않는다. $ES(n) < \infty$임은 램지수를 활용하여 확인해볼 수 있다.

 

Proposition. $ES(n) < \infty$

 

Proof. $N = R_4(n, 5) < \infty$개의 general position에 있는 평면 상의 점들이 주어졌다고 하자. $N$의 각각의 $4$-부분집합에 대해 이들이 convex 하다면 빨간색, 아니면 파란색으로 칠하자. 그러면, 어떠한 $5$개의 점도 이들의 $4$-부분집합이 모두 파란색으로 칠해질 수는 없다. ($\because ES(4) = 5$) 따라서, 램지수의 정의에 의해 $n$개의 점이 존재해 이들의 모든 $4$-부분집합이 convex하다. 이는, 이러한 $n$개의 점이 볼록 $n$각형을 이룸을 말한다.

 

그렇다면, $ES(n)$은 얼마나 빠르게 증가할까? $ES(n) \ge 2^{n-2}+1$임은 construction에 의해 증명된 바 있고, 현재까지 $ES(n)$의 상한 중 가장 optimal 한 것은 $ES(n) \le O(2^{n+(4 \sqrt{2} +\epsilon) \sqrt{n \log n}})$ 이고, 증명은 링크에서 확인할 수 있다.

2. Crossing Number

그래프 $G$를 평면에 그리는 상황을 생각해보자. $G$의 정점을 general position 상에 있는 점으로 표현하고, 간선을 선분으로 표현할 때, 교차하는 간선의 쌍의 수의 최솟값을 $cr(G)$로 표기하자. 예를 들어, $cr(K_4) = 0$이고, $cr(K_5) = 1$이다. 또한, $cr(K_{3, 3}) = 1$이다.

 

Problem. $cr(K_n)$은 얼마일까?

 

쉽게 다음과 같은 사실을 확인할 수 있다.

$$ cr(K_n) = \min_{\text{over all }|P|=n \\ P \subseteq \mathbb{R}^2 \\ P\text{: general position}} (\text{# of 4-subset of } P \text{ in convex position}).$$

 

이에 대해 다음과 같은 추측이 있다.

 

Conjecture. $cr(K_n) = \frac{1}{4} \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$.

 

이 추측이 $n \le 10$에 대해 참임은 잘 알려져 있고, $n = 11$에 대해 참임은 링크에서 증명을 확인할 수 있다. 이에 대한 레퍼런스들은 다음 링크에서도 자세히 확인해볼 수 있다.

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

테셀레이션  (2) 2019.11.22
두 가지 조합기하 문제들  (0) 2019.11.15
이분그래프가 될 조건  (0) 2019.09.06
고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
2N개의 점들  (0) 2018.01.01
댓글
댓글쓰기 폼