포크만 수

포크만 수(Folkman's number)는 그래프 이론의 문제에서 나온 큰 수로, 존 포크만이 고안하였다.

역사

포크만 수는 특정 조건을 만족하는 그래프의 최소 꼭짓점의 개수를 구하는 문제에서 나온다.

어떤 그래프가 주어져 있고, 여기서 꼭짓점 4개를 어떻게 골라도 네 점이 완전히 이어져 있지 않다고 가정한다. 즉 완전그래프 [math]\displaystyle{ K_4 }[/math]를 부분그래프로 가지지 않는다. 이제 이 그래프의 모든 변을 두 가지 색으로 칠한다. 전체 꼭짓점의 수가 적다면, 완전히 이어진 꼭짓점 3개를 어떻게 골라도 [math]\displaystyle{ K_3 }[/math]의 변이 언제나 두 색으로 이루어지도록 변을 칠할 수 있다. 그런데 꼭짓점이 특정 개수 이상이 되면, 어떤 방식으로 칠해도 단색 [math]\displaystyle{ K_3 }[/math]가 반드시 나오는 그래프가 존재한다. 이러한 조건을 만족하는 그래프의 최소 꼭짓점의 수는 얼마인가?

포크만은 이 문제의 답이 자신이 제시한 어떤 수 이하라는 사실을 보였고, 그 수가 바로 포크만 수이다.

크기

포크만 수는 십진법 전개나 거듭제곱 중첩으로 표현할 수 없을 정도로 크다. 물론 그레이엄 수보다는 훨씬 작다.

커누스 윗화살표 표기법으로 나타내면 포크만 수는 [math]\displaystyle{ 2 \uparrow\uparrow\uparrow (2^{901}) }[/math]이다. 가운데 윗화살표 3개는 하이퍼 연산 중 펜테이션에 해당한다. 이는 그라할인 [math]\displaystyle{ 3 \uparrow\uparrow\uparrow\uparrow 3 }[/math]보다는 작다.

같이 보기

• 램지의 정리
• 그레이엄 수 - 마찬가지로 그래프 이론과 관련이 있는 큰 수이다.