폴리매스

대한수학회 68번

허준이 교수 필즈상 수상 기념 문제

신희성 인하대학교 수학과 교수

 허준이 교수의 필즈메달 수상을 기념하여 허준이 교수의 연구 성과가 어떤 것이 있는지 알아보는 문제를 만들어 보았습니다.

1974년에 리드-호가 추측(Read–Hoggar conjecture)이 제시되었습니다. "모든 채색다항식(chromatic polynomial)의 계수의 절댓값은 로그-오목(log-concave) 수열이다."는 명제인데 2012년 허준이 교수가 증명을 하였습니다.[Huh12]

이 문제가 왜 어려웠던 난제였는지, 명제에 사용된 용어들에 대해 확인하기 위한 문제를 풀어 보겠습니다.

1. 채색다항식

다음과 같이 삼각형 $ABC$ 모양의 그래프가 있다고 합시다.

이 그래프의 꼭짓점에 $5$개의 색을 붙이는 방법은 간단하게 $5^3$으로 총 $125$가지 입니다. 여기에 선으로 이웃한 꼭짓점은 다른 색을 붙이는 규칙이 있다고 할 때는 색 붙이는 방법의 개수는 어떻게 될까요? 꼭짓점 $A$에 색을 부여하는 방법은 $5$가지, 꼭짓점 $B$에 색을 부여하는 방법은 $A$와 다르게 부여하기에 방법은 $4$가지, 꼭짓점 $C$에 색을 부여하는 방법은 $A$와 $B$ 모두 다르게 부여하기에 방법은 $3$가지가 되어, 곱의 법칙에 의하여, 경우의 수는 으로 총 $60$가지가 됩니다.

처음에 주어진 색이 $5$개가 아니라 $x$개라고 하면, 이웃한 꼭짓점에 다른 색을 부여하는 방법의 개수는 어떻게 될까요? 같은 이유에서 가 되어 $x^3-3x^2+2x$ 과 같은 다항식으로 표현됩니다. 이 다항식을 삼각형 모양의 그래프의 채색다항식이라고 합니다. 삼각형 모양의 그래프를 $C_3$이라고 이름을 붙인다면, 채색다항식은

$$\chi_{C_3}(x)=x^3-3x^2+2x$$

와 같이 표현합니다.

그래프 은 $n$개의 꼭짓점 사이에 선이 하나도 없는 그래프, 그래프 $K_n$은 $n$개의 꼭짓점이 모두 서로 이어진 그래프, 그래프 $P_n$은 $n$개의 꼭짓점이 직선 형태로 이어진 그래프, 그래프 $C_n$은 $n$개의 꼭짓점이 다각형 형태로 이어진 그래프라고 합시다.

이 그래프의 채색다항식이 다음과 같음을 증명하세요.

(1) 

(2 )

(3) 

(4) 

사실 삼각형 모양의 그래프는 $K_3$이자 $C_3$이므로, $\chi_{K_3}(x)$와 $\chi_{C_3}(x)$의 값은 

$$x(x-1)(x-2)=(x-1)^3 +(-1)^3(x-1)=x^3-3x^2+2x$$

로 같음을 확인할 수 있습니다.

2. 단봉형 (Unimodal)

단봉형 수열(Unimodal Sequence)이란 감소했다가 커지는 부분이 없는 수열을 말합니다. 즉 수열 $\left\{a_n\right\}$에서 $a_i > a_j < a_k$를 만족하는 가 존재하지 않는다면, 이 수열 $\left\{a_n\right\}$을 '단봉형'이라고 합니다.

단봉형 수열의 대표적인 것은 이항계수 ${n \choose k}={}_n{C}_k$ 입니다. $${n \choose 0} < {n \choose 1} < \dots < {n \choose \left\lfloor \frac{n}{2} \right\rfloor} = {n \choose \left\lceil \frac{n}{2} \right\rceil} > \dots > {n \choose n-1} > {n \choose 0}$$ (여기서 $\left\lfloor x \right\rfloor$는 $x$를 넘지 않는 최대 정수, $\left\lceil x \right\rceil=-\left\lfloor -x \right\rfloor$를 의미합니다.)

채색 다항식에서도 수열의 계수를 보면 음수와 양수가 섞여서 등장합니다. 이 때 이 계수들의 절대값을 나열해 보면 단봉형이 됩을 확인할 수 있습니다. 예를 들어 삼각형 모양의 채색다항식 $$\chi_{C_3}(x)=x^3-3x^2+2x$$에서 계수의 절대값은 $1, 3, 2$로서 단봉형 수열이 됩니다.

문제1 에서 증명한 $\overline{K_n}$, $K_n$, $P_n$, $C_n$의 채색다항식의 계수의 절댓값이 단봉형임을 증명하세요.

3. 로그-오목 (log-concave)

오목(concave)은 볼록(convex)과 반대되는 개념입니다. 어떤 매끄러운 함수 혹은 다항식이 (아래로) 볼록이라는 것은, 이차도함수의 값이 정의역 영역에서 항상 양수일 때를 말합니다. (미분이 불가능한) 일반적인 함수 전체로 확장을 한다면, 모든 $x$, $y$에 대하여 다음 부등식을 만족할 때 볼록이라고 합니다.

$$f\left(\frac{x+y}{2}\right) \leq \frac{f(x)+f(y)}{2}$$

비슷하게 수열이 볼록이라는 것은 모든 $n$에 대하여 다음을 만족하는 수열입니다.

$$a_n \leq \frac{a_{n-1} + a_{n+1}}{2}$$

즉, 수열에서 이웃한 두 수의 평균이 원래 항보다 큰 형태입니다. (아래로) 오목 수열은 반대로 이웃한 두 수의 평균이 원래 항보다 작은 형태입니다.

$$a_n \geq \frac{a_{n-1} + a_{n+1}}{2}$$

로그-오목(log-concave)은 로그(log)를 취했을 때에 다음과 같이 오목(concave) 성질을 만족할 때를 말합니다. 

$$\log a_n \geq \frac{\log a_{n-1} + \log a_{n+1}}{2}$$

위의 식을 정리해서 다시 표현하면 

$${a_n}^2 \geq a_{n-1} a_{n+1}$$

이 됩니다. 즉, 로그-오목 수열은 모든 $n$에 대해서 ${a_n}^2 \geq a_{n-1} a_{n+1}$을 만족하는 수열입니다.

산술-기하 평균 부등식을 생각해 보면, 오목 수열은 로그-오목 수열이라고 말할 수 있지만, 로그-오목이라고 오목 수열은 되지 않는 예가 존재합니다. 따라서 로그-오목을 만족하면 오목 이라고 말할 수 없지만, 만약 수열 중간에 $0$이 등장하지 않는 음이 아닌 로그-오목 수열(nonnegative log-concave sequence with no internal zeros)은 항상 단봉형이 된다고 알려져 있습니다.

문제1 에서 증명한 $\overline{K_n}$, $K_n$, $P_n$, $C_n$의 채색다항식의 계수의 절댓값이 로그-오목임을 증명하세요.

4. 일반적인 그래프

다시 언급하겠지만, 허준이 교수는 "모든 채색다항식의 계수의 절댓값은 로그-오목수열이다."임을 증명하였습니다. 우리가 다루었던 $4$가지 형택의 그래프 이외에 모든 그래프의 채색다항식의 계수의 절댓값으로 만든 수열은 로그-오목이라는 것입니다.

다음 인터넷 주소를 통해서 Paley 그래프를 확인해 봅시다.

https://mathworld.wolfram.com/PaleyGraph.html

Paley 그래프의 정의는 복잡하지만, 그래프의 구조는 다른 기회에 이해하기로 합시다.

여러 Paley 그래프 중에서 다음 그림처럼 차수가 $9$ 그리고 $13$인 그래프에 대해서 채색다항식을 구하고, 이 다항식의 계수의 절댓값이 단봉형이고 로그-오목임을 확인하세요.

참고 문헌

[Huh12] June Huh. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. J. Amer. Math. Soc., 25(3):907–927, 2012.

끝.