본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대68. 허준이 교수 필즈상 수상 기념 문제
수학동아 2022.08.01 10:04 조회 2196

 

대한수학회 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$가지가 되어, 곱의 법칙에 의하여, 경우의 수는 5   imes 4   imes 3으로 총 $60$가지가 됩니다.

 

 

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

 

 

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

 

 

와 같이 표현합니다.

 

 

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

 

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

 

(1) \chi_{\overline{K_{n}}}(x)=x^n

(2 )\chi_{K_{n}}(x)=x(x-1)(x-2)\cdots (x-n+1)

(3) \chi_{P_{n}}(x)=x(x-1)^{n-1}

(4) \chi_{C_{n}}(x)=(x-1)^{n}+(-1)^{n}(x-1)

 

 

사실 삼각형 모양의 그래프는 $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$를 만족하는 i<j<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.

 

 

끝.

  •  
    부분해결
    Amath Lv.8 2022.08.01 12:56

    1번은 쉬워요. 

     

     

    (1) 모든 꼭짓점들은 아무 관련이 없으므로 각 꼭짓점은 항상 x가지의 색이 가능하다. 따라서 x^{n}

     

     

    (2) 모든 꼭짓점들은 서로 색이 달라야 한다. 한 꼭짓점을 선택하고, 그 꼭짓점은 x가지, 각 경우에 다른 꼭짓점은 x-1가지, 각 경우에 또 다른 꼭짓점은 x-2가지... 로 계산하는데, 꼭짓점은 총 n개이므로 x(x-1)(x-2)...(x-n+1)이다. 

     

     

    (3) 직선 형태에서, 한쪽 끝점(차수가 1인 점)을 1, 그 옆의 점을 2, 그 옆의 점을 3, ..., 가장 마지막인 다른 쪽 끝점을 n으로 이름붙이고 생각하면, 1번 정점은 색이 x가지가 가능하고, 각 경우에 2번 정점은 x-1가지 색이, 각 경우에 3번 정점은 2번 정점의 색을 제외한 x-1가지 색이, ..., 각 경우에 n번 정점은 n-1번 정점의 색을 제외한 x-1가지의 색이 가능하므로, 가능한 가짓수는 x(x-1)^{n-1}이다. 

     

     

    (4) 점화식을 세우는데, 3에서 한 과정에서 제외하는 방법으로 세우면 된다. 우선 어떤 한 정점을 선택해 1번 정점이라 하고, 시계 반대 방향으로 돌아가며 숫자 순서대로 n번 정점까지 이름을 붙이자. 3의 방식대로 하면, 4에서 구하는 것보다 많은 경우가 생기는데, 서로 붙어 있는 1번 정점과 n번 정점의 색이 겹치는 경우들이다. 이 경우는, 1번과 n번 정점의 색이 같고, 다른 서로 이웃한 정점은 서로 다른 색을 칠하는 경우인데, 이것을 생각해 보면 정점이 n-1개일 때의 경우의 수와 같다는 것을 알 수 있다. 여기서 \chi C_{n}(x) = x(x-1)^{n-1}-\chi C_{n-1}(x)라는 점화식을 얻을 수 있다. 따라서, \chi C_{n}(x) = x(x-1)^{n-1}-x(x-1)^{n-2}+...+(-1)^{n-2}x(x-1)^{3}+(-1)^{n-1}\chi C_{3}(x)이다.

     

    이것은 정리하면 \chi C_{n}(x)=(-1)^{n}x(x-1)^{3}\cdot \frac{(1-x)^{n-3}-1}{(1-x)-1}+(-1)^{n+1}x(x-1)(x-2)=(-1)^{n+1}(x-1)^{3}[(1-x)^{n-3}-1]+(-1)^{n+1}x(x-1)(x-2)=(x-1)^{n}+(-1)^{n}[(x^{3}-3x^{2}+3x-1)-(x^{3}-3x^{2}+2x)]이 된다.

     

    따라서 \chi C_{n}(x)=(x-1)^{n}+(-1)^{n}(x-1)

    댓글 작성하기 좋아요0 댓글수1
  •  
    부분해결
    RedoC Lv.5 2022.08.03 16:51 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      조영준 멘토 Lv.3 2022.08.11 03:29

      3번과 이를 이용하여 2번까지 잘 풀었습니다!

      좋아요0
    •  
      RedoC Lv.5 2022.08.12 21:53

      부분해결 딱지가 붙었기 때문에 공개합니다.

      ---

      문제3의 풀이를 이용해 문제2의 풀이를 유도하는 서술입니다.

      문제 3 풀이

      ---

      (1) 계수가 1밖에 없으므로 성립

      (2) 계수가 제 1종 스털링수, 즉 s(n,n), s(n,n-1), ..., s(n,1), s(n,0)이다.

      n=1, 2의 경우에는 log-concave를 보일 수 없으므로 성립한다 가정.

      (3) 계수의 절대값이 \binom{n-1}{n-1},\binom{n-1}{n-2},...,\binom{n-1}{0}이다.

      위 계수들의 절대값이 log-concave, 즉 \binom{n}{m} \geq \binom{n}{m-1} \binom{n}{m+1}임을 보이자.

      \binom{n}{m} \geq \binom{n}{m-1} \binom{n}{m+1} \Leftrightarrow \left ( \frac{n!}{m!(n-m)!}\right )^2 \geq \frac{n!}{(m-1)!(n-m+1)!}\frac{n!}{(m+1)!(n-m-1)!}

      이때 (m!)^2 \leq (m-1)!(m+1)! \Leftarrow m^2 \leq m(m+1)임을 생각하면

       \left ( \frac{n!}{m!(n-m)!}\right )^2 \geq \frac{n!}{(m-1)!(n-m+1)!}\frac{n!}{(m+1)!(n-m-1)!} \\ \Leftrightarrow \frac{1}{(m!)^2}\frac{1}{((n-m)!)^2} \geq \frac{1}{(m-1)!(m+1)!}\frac{1}{(n-m-1)!(n-m+1)!}

      은 참이다.

      (4) 계수의 절대값이  \binom{n}{n},\binom{n}{n-1},...,\binom{n}{2}, \binom{n}{1}-1이다.

      이항계수에 대해서 log-concave가 성립함은 위에서 이미 보였기 때문에 마지막 항에 대한 log-concave만 검사해주면 된다.

      \binom{n}{2}^2 \geq \left ( \binom{n}{1} -1 \right ) \binom{n}{3} . 근데 \binom{n}{2}^2 \geq \binom{n}{1} \binom{n}{3}가 성립하므로 자명하게 성립한다. @

       

      문제 2 풀이

      ---

      그리고 이 log-concave가 성립한다는 것은 a_n^2 \geq a_{n-1}a_{n+1} \Leftrightarrow \frac{a_n}{a_{n-1}} \geq \frac{a_{n+1}}{a_n}을 만족한다는 것이고 단봉형도 성립한다는 것을 알 수 있으므로 문제 2 역시 해결된다. @

      좋아요0
  •  
    부분해결
    pure math Lv.7 2022.08.03 22:20 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      pure math Lv.7 2022.08.03 22:23 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      조영준 멘토 Lv.3 2022.08.11 03:31

      잘 풀었습니다~

      좋아요0
  •  
    부분해결
    Amath Lv.8 2022.08.04 11:58 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
  •  
    RedoC Lv.5 2022.08.04 14:33

    4번 문제의 \chi_{9-Paley-Graph}(x)에 대한 표입니다.

    x \chi_{9-Paley-Graph}(x)
    1,2 0
    3 12
    4 1056
    5 27480
    6 317760
    7 2212980
    8 10997952
    9 43038576

    프로그래밍으로 돌린거라 틀릴 가능성이 낮긴 하지만 그래도 오류가 있을 수 있으니 참고용으로만 쓰세요

     

     

    댓글 작성하기 좋아요0 댓글수7
    •  
      RedoC Lv.5 2022.08.05 01:11

      참고로 이걸 이용해서  \chi_{9-Paley-Graph}(x)를 구해보면 1x^9-18x^8+147x^7-711x^6+2220x^5-4545x^4+5878x^3-4308x^2+1336x이 나옵니다.

      그리고 이 계수들의 절대값은 log-concave 수열입니다.

      좋아요0
    •  
      Amath Lv.8 2022.08.06 12:07

      그런데, x가 7 이상인 경우들만 넣어서 식을 만들어 보셨어요? 그러면 식이 달라질 수도 있을 것 같아요. 

      좋아요0
    •  
      RedoC Lv.5 2022.08.06 12:12

      아니요. x에 1~9까지 전부 대입해서 만든 식입니다. 근데 왜 7 이상의 x를 대입해야 한다고 이야기하시는 건가요?

      좋아요0
    •  
      RedoC Lv.5 2022.08.06 12:47

      그래도 혹시 모르니까 한번 확인은 해보겠습니다.

      좋아요0
    •  
      RedoC Lv.5 2022.08.06 13:47

      @Amath 음 식이 달라지지는 않습니다.

      좋아요0
    •  
      Amath Lv.8 2022.08.06 19:56

      아 7이 아니라 5네요. 한 점에 최대 4개의 점이 연결되어서, 그것 때문에 식이 달라질 수 있다는 생각이었어요. 

      좋아요0
    •  
      RedoC Lv.5 2022.08.06 20:20

      아 넵. 아마 이 식이 틀리지는 않을 것 같네요

      13-Paley-Graph에 대해서도 돌리고 있습니다

      좋아요0
  •  
    RedoC Lv.5 2022.08.06 23:29

    4번 문제의 \chi_{13-Paley-Graph}(x)에 대한 표입니다.

    x \chi_{13-Paley-Graph}(x)
    1,2,3,4 0
    5 45240
    6 4502160
    7 131531400
    8 1943497920
    9 18313298640
    10 125102184480
    11 671055905520
    12 2981550686400
    13 11392482970440

    이 계산 결과를 이용해서 \chi_{13-Paley-Graph}(x)를 구해보면

     1x^{13}-39x^{12}+715x^{11}-8138x^{10}+63895x^{9}-363311x^{8}+1527006x^{7}-4752657x^{6}+10796396x^{5}-17314245x^{4}+18424159x^{3}-11537630x^{2}+3163848x가 나오고

    계수들의 절댓값은 log-concave 수열입니다.

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    부분해결
    RedoC Lv.5 2022.08.09 21:46 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      RedoC Lv.5 2022.08.11 00:33 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      조영준 멘토 Lv.3 2022.08.11 03:36

      요약하자면 결국 코딩을 통해 색의 종류가 적을 때 몇 가지가 나오는지 확인하고,

      이를 이용해 각각 9차다항식과 13차다항식이 유일하게 나옴을 이용한 방법인 것 같습니다.

      답이 맞는지는 제가 확인하기 어렵지만 사용하신 방법은 맞는 것 같습니다.

      좋아요0
  •  
    신희성 교수 Lv.4 2022.08.11 15:49

    비밀댓글들을 볼 수는 없지만, 마지막 문제에서 Deletion–contraction formula 을 이용하여 채색다항식을 계산을 해 보아 교차 검증을 해 보면 좋겠습니다.
    https://en.wikipedia.org/wiki/Deletion%E2%80%93contraction_formula

    댓글 작성하기 좋아요0 댓글수1
    •  
      RedoC Lv.5 2022.08.11 16:45

      오오 감사합니다. 식은 공개하겠습니다.

      9-Paley-Graph)

      1x^9-18x^8+147x^7-711x^6+2220x^5-4545x^4+5878x^3-4308x^2+1336x

       

      13-Paley-Graph)

      1x^{13}-39x^{12}+715x^{11}-8138x^{10}+63895x^{9}-363311x^{8}+1527006x^{7}-4752657x^{6}+10796396x^{5}-17314245x^{4}+18424159x^{3}-11537630x^{2}+3163848x

       

      좋아요0
  •  
    벡터공간 Lv.1 2022.08.12 21:43 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    벡터공간 Lv.1 2022.08.12 21:53 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911