재미없는 블로그

유사 수학 블로그입니다.

지난 두 달 반 동안 유럽에 다녀왔습니다

with 6 comments

프랑스, 독일에서 열린 워크샵과 윈터(?) 스쿨에 참가하고 돌아왔습니다.

나름 험난한 일정이었네요. 후… 살아돌아온게 다행.

뭐 그러나 나름 유익한 시간이었던 것 같기도 합니다. 사실 현실 도피

뭔가 중구난방인듯한, 제가 참여한 이벤트들은 다음과 같습니다.

1.Workshop on interactions between algebraic and discrete geometry

근래 이산 기하 분야에서 대수 기하적 방법을 이용해서 그 동안 난제로 여겨져 온 문제들에서 큰 진보가 있었습니다. Joint 문제가 그 신호탄인데…

d-차원 공간에서 점과 n개의 직선들이 주어졌을 때, 어떤 주어진 점 p가 같은 hyperplane 상에 있지 않은 d개의 직선 l_{i_1}, l_{i_2},ldots, l_{i_d}의 교점과 일치할 때 tuple (p, l_{i_1}, l_{i_2,}ldots, l_{i_d})를 joint라고 합니다. Joint 문제는 이러한 joint의 개수가 몇 개까지 가능한가를 묻는 문제입니다.

그동안 이 갯수가 O(n^{d/d-1})일 것이라는 강한 추측만이 있었을 뿐 이 상한에 근접하는 결과는 없었습니다만 (심지어 3차원에서조차도), 근래 Guth, Katz의 대수 기하적 방법론에 의해 이 추측이 결국 증명되었습니다. 이는 본래 György Elekes에 의해 제안된 방법론인데, 정작 본인은 이 결과를 보지 못하고 세상을 떠났군요. 이 결과는 Sharir[1],[2]등에 의해서 좀 더 쉽게 다듬어지게 되어 한 시간의 강의로도 충분히 설명가능한 정도까지 되었습니다. 참고로 Sharir등의 결과에서는 Elekes에 대한 추모의 의미로 그의 이름이 저자 리스트에 들어가 있군요.

Joint

기본 아이디어는 주어진 점들에서 0이 되는 polynomial, 즉 algebraic variety가 있으면 이와 직선과의 incidence의 상한을 쉽게 알 수 있다는 것에 바탕을 두고 있습니다. 가령 어떤 직선이 주어진 점 중에서 몇 개를 지나는지 알고 싶다면, 구한 algebraic variety와의 교점의 갯수만 세면 이것을 상한이 되겠지요. 이 결과에서는 이런 상한이 실제에서 그리 크게 멀지 않다는 것을 시사하고 있습니다.

어렵다고 여겨져 온 문제가 이렇게 풀렸으니 이산 기하 커뮤니티에서 이 방법론에 대한 관심사가 높아지는 것은 당연한 일이지요. 지난 9월에 프랑스에서 있었던 워크샵은 이러한 방법론에 대한 워크샵이었습니다.

이 방법론의 주역 중 하나인 Sharir등을 초청했고, 대수 기하…라기보다는 계산 대수하시는 연구자들을 초청한 나름 의미있는 자리였던 것 같으나, 사실 끝으로 갈수록 뭔가 본래 목적이 흐릿해진 용두사미가 되어버린 워크샵이었던 것 같습니다. -_-;;; 막판에는 다들 자신분야의 문제를 풀고 있더라는…

뭐 그래도 좋은 음식 배불리 먹어서 좋았군요. 이게 워크샵의 의의가 되면 곤란하겠지만.

참고로 불과 며칠전에 Guth, Katz가 또다시 이 대수 기하적 방법론으로 Erdős distance problem을 ‘거의’ 풀어내는 쾌거를 달성하였습니다. 이 분들은 이 방법론으로 스타가 된 것 같군요.

그동안 이산기하는 아마추어도 쉽게 접근할 수 있는 수학(?)이었는데 앞으로는 이 분야도 점점 복잡한 기교가 요구되는 방향으로 발전되어가지 않을까 싶습니다.

2. Differential Equation Methods for Stochastic Processes

베를린에서는 Freie University 및 TU Berlin에서 주최된 Doc-Course에 참가하였습니다. 첫 주제이자 메인 토픽이었던 주제는 랜덤 그래프 프로세스에서의 미분 방정식을 이용한 방법. (한글로 쓰니 참 없어보이네 -_-;;;)

랜덤 그래프 프로세스는, 어떤 그래프의 성질을 유지하면서 edge를 임의로 그 성질이 만족하는 한계까지 더해나가는 프로세스입니다. 가장 쉬운 예로 그래프의 maximum degree가 k 이하가 되도록 하는 프로세스를 생각할 수 있겠죠. 프로세스 자체는 매우 간단한 것이, 모든 vertex의 degree가 k가 넘지 않도록 edge를 추가해나가면 되는데, 그 분석은 매우 복잡합니다.

이 랜덤 그래프 프로세스를 쉽게 분석할 수 있는 툴로써 미분 방정식을 이용한 방법론이 요 근래 몇년새에 크게 조명받고 있습니다. 기본 아이디어는 프로세스를 어떤 연속적인 프로세스로 근사해 생각한 뒤에, 나중에 근사한 결과로 발생하는 에러를 martingale을 이용해 그 상한을 얼마 이하로 보장할 수 있다는 것입니다. 물론 계산은 여전히;;; 복잡합니다.

이 방법론이 크게 각광받는 이유라면, Ramsey number R(3, k)의 하한 Omega(k^2/log k)가 이 방법을 이용해서 Tom Bohman에 의해 다시 증명되었다는 것에 있겠지요. 이 결과는 잘 알려다시피 김정한 박사님에 의해 이미 증명된(link), 그리고 Fulkerson prize를 수상한 extremal combinatorics의 대표적인 결과 중 하나입니다. 김정한 박사님의 본래 결과는 매우 복잡하여서 사실 많은 사람들이 이를 이해하지 못했는데, Bohman의 새로운 결과는 직관적으로 매우 쉬워보입니다.

Bohman이 분석한 것은 triangle이 생기지 않는 프로세스입니다. Triangle은 물론 크기 3의 clique이지요. 분석해놓고 보니 Omega(k^2/log k)의 하한이 얻어졌고 (물론 적절한 스케일링과 함께), 게다가 independence number도 적어지더라는, 어찌보면 참 운 좋게 발견한 결과라고 할 수 있습니다. (R(3, k)는 triangle 혹은 크기 k의 independent set이 나타날 수 밖에 없는 최소 갯수의 vertex 개수라는 것을 주지.) 거기에 ‘높은 확률’로 이것이 성립한다는 것을 보였으니 본래 결과보다도 어떤 의미에서 더 강력하다고도 할 수 있군요.

이 코스의 참가자가 대부분 이와 관련된 전공을 하고 있었고, 기간도 제일 길었던, 이번 Doc-Course의 가장 주가 되었던 방법론이라고 할 수 있습니다.

계산은 아직도 복잡하지만, 아이디어는 간단한 방법론이기도 하고 또한 강력하기도 하니, 앞으로 extremal combinatorics에서 한동안 많은 결과를 가져다 줄 방법론으로 보입니다. 그러나 사실 이쯤 되면 그리 조합론 같아 보이지는 않네요. 차라리 해석학의 범주에 있다고 보는 편이… :)

3. Analytic Combinatorics

Generating function은 어떤 object를 세는 enumerative combinatorics의 주요한 툴로 사용되고 있습니다. 즉, G.F.를 알면 미분을 한다던지 아니면 다른 해석학의 도구를 이용해서 각각의 계수들을 쉽게 알 수 있기 때문이죠. Bijection을 이용한 증명 방법에 비하면 기계적이고 덜 조합적이지만, 많은 경우 더 쉽게 결과를 알 수 있는 강력한 방법입니다.

하지만 G.F.의 계수조차도 정확히 알기 힘든 경우가 다반사인데, 해석적 조합론 코스에서는 complex analysis의 툴을 이용해서 이를 asymptotic하게 알 수 있는 방법을 배웠습니다. 좀 더 정확하게는 Cauchy’s Integral Theorem을 이용하는 방법을 배웠다고 할 수 있겠네요.

역시 이것도 계산, 계산, 계산입니다.;;; 점화식만 구하고 나면 그 다음부터는 해석학, 아니 그냥 미적 문제가 되어버리는군요.

4. Combinatorics in Statistical Physics

의외로 기대와는 달리 가장 조합적인 내용을 배웠던 코스였습니다. 통계 물리에서의 많은 모델들이 그래프의 특징들에 대한 generating function이 연관있다는 것이 통계 물리와 조합론의 접점입니다. Ising model등이 연관있다고 하는데 정작 본래 물리에서 어떤 의미인지는 잘 모르겠군요. 사실 알 수 있을리가;;;

그래프 이론 및 matroid와 큰 연관이 있고, 많은 open problem들이 역시 흥미로웠던, 개인적으로는 가장 인상 깊었던 코스였습니다. 아마 며칠안에 이 분야의 open problem에 대한 포스팅을 할 것 같군요. 이지만 이전 포스팅 시리즈도 결말을 못 냈

음 뭐 사실 2달 반 동안 도피 생활 잘 하고 왔다는 느낌입니다. 이제 졸업을 해야 되는데(…) 후 아직도 먼 것 같군요.

About these ads

Written by misfit

12/01/2010 at 4:51 오후

잡담에 게시됨

6개의 답글

Subscribe to comments with RSS.

  1. 오오, 오랫만의 포스트군요. :)
    제목들이 모두 흥미와 궁금증을 자아내는군요. ㅎㅎ
    Erdős distance problem이 풀렸다는 이야기는 테렌스 타오의 버즈에서 소식 들었습니다. 뭐, 저하고는 거리가 먼 분야 같습니다만… ㅎㅎ

    zariski

    12/02/2010 at 12:14 오전

  2. 위에 joint 정의가 잘못되어서 수정합니다. 원래 씌여진대로라면 3차원공간만 생각해도 되는 것이었죠;;;

    pedantry

    12/02/2010 at 1:50 오후

  3. 그런데 1번에서 ‘거의’풀어냈다는건 무슨뜻이죠? 아직 검증중이다 or 아니면 원래 problem의 weak version을 증명했다?

    yg

    12/04/2010 at 3:37 오후

    • 네… 증명된 결과는 conjecture보다 약한 결과입니다.

      Erdos는 평면에 n개의 점이 주어지고, 주어진 점들 중 두 점사이의 거리를 고려할 때 이 거리의 가짓수는 \Omega(n/\sqrt{\log n})라고 추측하였습니다.

      Guth, Katz가 증명한 것은 \Omega(n/\log n) 가짓수의 거리가 존재한다는 것으로, Erdos의 추측에 불과 \sqrt{\log n} 팩터의 차이가 있지요. :)

      pedantry

      12/04/2010 at 3:49 오후

    • 참고로 가짓수의 상한은 이미 Erdos가 O(n/\sqrt{\log n})이라는 것을 증명하였습니다.

      그러니 이 결과가 얼마나 큰 진보인지 느낄 수 있습니다. 상한에서 불과 \sqrt{\log n} 팩터만 떨어진 하한이니, 문제가 거의 풀렸다고 할 수 있는 셈이죠.

      pedantry

      12/04/2010 at 3:53 오후


댓글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중

팔로우

모든 새 글을 수신함으로 전달 받으세요.

%d bloggers like this: