김정한 교수님의 유명한 정리인 R(3,t) ~ c t^2 / log t라는 결과에서 c의 범위를 좁혀낸 최신 연구 결과가 나왔음을 소개하였습니다.
논문
G. F. Pontiveros, S. Griffiths, R. Morris, The triangle-free process and the Ramsey number R(3,k), arxiv:1302.6279, 2013. Accepted to Mem. Amer. Math. Soc. 2018.
T. Bohman, P. Keevash, Dynamic concentration of the triangle-free process, arxiv:1302.5963
평면 그래프의 꼭짓점에 c개 이하의 색으로 색칠을 잘 해서, 임의의 path에서 어떤 연속한 같은 길이의 부분path를 보더라도 그 색깔 패턴이 전혀 반복되지 않게 칠할 수 있도록 하는 상수 c가 존재하는지에 관한 미해결 문제가 해결되었다는 소식을 전하였습니다. 이러한 색칠을 non-repetitive coloring이라고 합니다.
그래프 H를 부분 그래프로 갖지 않는 꼭짓점 n개짜리 그래프의 선의 수의 최댓값을 ex(n,H)라고 합니다. H가 이분 그래프가 아닌 경우에는 ex(n,H)가 n2에 비례함이 잘 알려져 있습니다만, H가 이분 그래프인 경우에는 H에 따라 n의 몇 승에 비례하게 되는지가 다 다르고 정확한 것이 알려져 있지 않습니다. ex(n,H)가 n의 r승으로 비례하게 되는 r 값을 모두 찾아보려는 연구가 여러 그룹에서 진행되었는데 그 연구 결과들을 소개하였습니다. 이 중에는 제 지도학생 강동엽 학생의 연구도 있습니다.
n*n 바둑판 모양의 그래프에서 도둑 한 명과 경찰 여러 명이 이웃한 꼭짓점으로 이동하면서 잡기 게임을 하는 cops and robber game에서 도둑이 경찰의 R배 속도로 움직일 때 잡기 위한 필요한 경찰의 수는 R이 충분히 크면 n^(c/log log n)보다 크다는 것을 증명한 논문 결과를 소개하였습니다.
평면 그래프의 maximum degree가 k이면 acyclic edge chromatic number가 k+2이하라는 2009년 Cohen, Havet, Müller의 추측을 Dan Cranston이 k 값이 420000000000000 이상이면 참이라고 증명하였다는 소식을 전하였습니다.
Aubrey de Grey가 최근에 평면의 chromatic number가 5 이상임을 증명하였다는 소식을 전하였습니다. 이 문제는 1950년 가을에 당시 18세로 시카고 대학 신입생이었던 에드워드 넬슨(Edward Nelson)이 만들었습니다. 4이상임은 알려져있었는데 5이상인 것을 증명하는 것을 그간 아무도 하지 못했었습니다.
KAIST 전산학부 Otfried Cheong 교수님 및 공저자 분들이 한 연구 결과를 소개하였습니다. 방도 볼록하고 가구도 볼록한 모양이라고 할 때, 만일 그 방에 가구를 임의의 방향으로 놓는 것이 가능하다면 그 가구를 한 바퀴 돌리는 것도 가능한가? 이 1921년에 나온 문제를 풀었습니다.
1967년 Ringel이 제기한, 원형 테이블 여러 개 있는 곳에서 여러 사람이 모여서 워크샵을 할 때 정확히 딱 한 번씩만 서로 이웃해서 앉도록 일정을 짜는게 가능한지에 관한 Oberwolfach 문제를 Birmingham 대학의 김재훈 박사 등이 해결했다는 소식입니다.
2018년 루마니아 클루지나포카에서 열린 제59회 국제수학올림피아드에 다녀왔습니다. 국제수학올림피아드 참가는 저는 2009년, 2011년, 2012년, 2016년, 2017년에 이어 6번째입니다. 이번에는 107개 나라에서 총 594명의 학생이 참가하였습니다. 2016년, 2017년에는 600명이 넘었는데 조금 줄어들었지요. 예전에 적은 것처럼 올해도 후기를 적어볼까 합니다.
2018년은 우리나라가 국제수학올림피아드에 참가한지 정확히 30년이 되는 해입니다. 올해는 대표학생 6명이 금메달 3개, 은메달 3개를 받았습니다. 학생들의 점수를 합하여 살펴보는 국가별 순위에서는 107개 참가국 중 7위라는 우수한 성적을 거두었습니다. 국가별 순위를 보면 아래와 같습니다.
1위: 미국 212점
2위: 러시아 201점
3위: 중국 199점
4위: 우크라이나 186점
5위: 태국 183점
6위: 대만 179점
7위: 대한민국 177점
8위: 싱가포르 175점
9위: 폴란드 174점
10위: 인도네시아 171점
올해 역시 작년과 마찬가지로 우리나라 대표 학생들은 모두 서울과학고 학생이었습니다. 우리 나라 대표 학생들과 그 메달은 아래와 같습니다. 서울과학고가 아닌 최근 대표로는 2년전 국제수학올림피아드에서 만점을 받았던 세종과학고 홍의천 학생이 있었습니다.
이 중 김다인 이송운 학생은 작년에 이어 두 번째로 출전하였습니다. 김다인 학생은 이번 팀의 유일한 여학생이었습니다. (한국대표팀에서 김다인 학생 이전에 국제수학올림피아드 대표를 한 여학생으로는 2005년 2006년 두 번에 걸쳐 출전한 경기과학고 남주강씨가 있습니다.) 이제까지 한국대표팀으로 국제수학올림피아드를 나가서 금메달을 두 번 이상 받은 학생은 총 14명이 있고, 그 중 여학생은 이제 김다인 학생을 포함하여 이제 3명이 되었습니다.
2016년부터 우리나라에서는 2월에 루마니아 수도 뷰쿠레스티에서 열리는 루마니아 수학 마스터 대회(Romanian Master of Mathematics)에 출전하고 있습니다. 이 6명의 대표 중 4명, 강지원 김다인, 김홍녕, 이송운 학생은 이미 루마니아 수학 마스터 대회에 한국 대표로 출전한 경험이 있어서 루마니아에 좀더 익숙했을 것입니다. 김홍녕 학생은 올해 루마니아 수학 마스터 대회에서 전체 개인 순위 1위로 금메달을 수상하였는데, 국제수학올림피아드에서도 우리 팀 1위를 하며 큰 기여를 하였습니다.
대표 6명에는 들지 못했지만 최종 후보로 뽑혔던 그 밖의 9명의 학생들은 다음과 같습니다.
이번 한국대표팀 단장으로는 인하대 송용진 교수님이 작년처럼 수고해주셨고, 유원대 이승훈 교수님이 단장팀에 합류하셔서 함께 문제 번역 등의 일을 하셨습니다. 학생들을 인솔하다가 시험 후에는 채점 과정에 참여하는 부단장팀에는 저와 아주대 최수영 교수, 그리고 서울대 수리과학부 학생이며 2014년, 2015년 국제수학올림피아드 한국대표였던 김재형 학생이 있었습니다. 그리고 한국과학창의재단에서 연경남 박사님도 오셔서 도와주셨습니다.
올해 역시 최근 경향에 맞게 1, 2, 4, 5 문제가 정수, 대수, 조합, 기하 분야 한 문제씩 골고루 나왔습니다. 작년보다 2번 5번 문제가 쉬워졌습니다. 우리나라 대표학생들은 보통 1, 2, 4, 5번 문제를 다들 골고루 잘 하고 어려운 3, 6번 문제를 몇몇이 공략하여 좋은 성적을 거두었습니다. 하지만 올해는 2, 5번 문제가 작년보다 쉬워지는 바람에 다른 강국들도 공략을 잘 하였습니다. 아울러 3번, 6번이 어려워서 우리나라 학생들은 이번에 3번, 6번에서 만점을 받은 사람이 아무도 없었습니다. 전체 참가자 중에 3번 만점은 고작 11명, 6번 만점은 고작 18명이었습니다.
비디오 촬영중
작년에 이어 올해에도 조교로 수고한 서울대 김재형 학생이 해설하는 국제수학올림피아드 풀이 동영상을 제작하였습니다. 촬영장소와 삼각대 및 오디오 장비를 빌려주신 카오스 재단분들께 감사드립니다. 참고로 김재형 학생이 입은 티셔츠는 2018년 여름학교 입교생들을 위하여 Jane Street이라는 Quantitative Trading 회사에서 후원해주신 것입니다. 올해부터 Jane Street은 한국수학올림피아드를 후원해주고 계십니다. 홍콩에서 티셔츠를 큰 상자로 보내주셨지요.
작년처럼 올해도 현지에서 태국 대표팀과 함께 며칠간 현지 공동 캠프를 진행하였습니다. 캠프를 위해 대회날보다 일찍인 7월 3일에 출국하였습니다. 작년처럼 최수영 교수님이 캠프를 위해 큰 수고를 하셨고 김재형 조교 또한 수고를 많이 하였습니다. 저는 창의재단 연경남 박사님과 함께 7월 6일 출국하여 현지에 7월 7일 자정 직후에 도착할 수 있었습니다.
단장팀이 묵었던 숙소 Grand Hotel Italia. 좋은 호텔에서 지내시니 부러웠습니다.
이번 국제수학올림피아드가 열린 도시인 클루지나포카(Cluj-Napoca)는 이런 큰 규모의 인원을 한번에 수용할만한 호텔은 없는 것으로 보였습니다. 단장팀의 경우는 Grand Hotel Italia라는 시내에서 좀 떨어진 멋지고 큰 호텔에 모두 묵었습니다. 하지만 부단장팀은 몇몇 나라별로 쪼개져서 시내의 여러 호텔 혹은 기숙사에 분산 수용되었습니다.
한국팀은 다행히 상당히 괜찮은 위치의 호텔인 Grand Hotel Napoca에 배정되었습니다. 나라별로 여러 호텔에 배정되다보니 제가 공항에 도착하였을 때 밤 늦게 나와계신 주최측 자원봉사자 분께서 제가 어느 호텔에서 자야 하는지 잘 찾지도 못하실 정도로 좀 허술한 면도 있었습니다. 여러 숙소로 나뉘다보니 같은 숙소가 아닌 다른 나라 사람들을 만날 기회가 너무 없었고 학생들끼리 서로 친목을 도모할 기회도 부족하였다는 점이 아쉬웠습니다.
학생들은 모두 2인 1실을 사용하였습니다. 이송운 송승호 학생이 217호, 김다인 학생은 이라크 대표 학생과 219호, 강지원 김홍녕 학생이 301호, 조영준 학생은 나이지리아 대표 학생과 302호를 썼습니다. 김다인 학생의 룸메이트였던 쿠르드에서 온 학생은 우리말을 너무 능통하게 써서 모든 사람들이 깜짝 놀랐습니다. K-POP에 매우 관심이 많아서 EXO의 팬이라는 그 학생 덕분에 김다인 학생은 외국인 룸메이트와 한국어로만 이야기를 주고 받을 수 있었습니다.
한국대표팀이 묵은 Grand Hotel Napoca. Wi-Fi가 연결 되지 않는 경우가 많아서 가져간 인터넷 공유기가 매우 유용하였다.
Grand Hotel Napoca는 개막식 및 시험이 열린 장소인 Polyvalent Hall과 매우 가까워서 강만 건너면 공원을 가로질러서 금방 걸어갈 수 있었습니다. 하지만 주최측은 항상 대절 버스로 이동하라고 하였는데 사실 버스 안에서 대기하는 시간이면 금방 걸어갈 수 있는 거리였습니다.
우리 팀의 가이드는 고등학생인 Tania Somesfalean이었습니다. 조금 우리말을 할 줄 알아서 원래 북한팀 가이드로 배정되어 있었으나 북한팀이 결국 오지 않은 바람에 한국팀에 배정되었습니다. Tania는 대단히 모범생이라 항상 시간을 꼭 지키게 만들었지만 정작 가보면 우리 팀이 가장 먼저 버스를 탄다든지 하는 경우가 많았습니다. 집에서 호텔까지 거리가 꽤 먼데도 매우 성실하게 도와주었습니다. 우리말도 점점 배우더니 나중에 “교수님” 같은 단어도 잘 썼습니다.
개회식 (7월 8일 일요일)
7월 8일 국제수학올림피아드 개회식 무대에 올라간 한국대표단 학생들과 저. 왼쪽부터 저, 조영준, 이송운, 김다인, 김홍녕, 송승호, 강지원. 사진출처: IMO2018 공식 페이스북.
이번 국제수학올림피아드 개회식은 7월 8일 일요일 오전 11시부터 1시까지 2시간 정도 진행되었습니다. 다른 해와 달리 축사가 매우 많아서 절반을 차지하였습니다. 특히 루마니아 대통령이 직접 와서 연설을 해서 놀랐습니다. 아울러 개막식과 폐막식이 루마니아 국영TV로 생중계되었습니다. 국제수학올림피아드를 처음 만든 나라답게 수학올림피아드에 관한 관심이 많다는 것을 느낄 수 있었습니다.
무대에는 부단장과 학생들, 가이드가 올라갔습니다. 제가 들고간 태극기는 우리가 제작한 것이 아니라 루마니아 주최측에서 제작해준 것인데 좀 허술하였습니다. 조금이라도 오래 서있어야 사진 찍기 좋은데 가이드가 워낙 빨리 무대에서 내려가는 바람에 위에 있는 사진에는 가이드가 나오지 않았습니다.
7월 8일 오후 6시 30분부터 1시간동안 시험장을 미리 답사하는 시간이 있었습니다. 다른 해와 다르게 자기가 사용할 책상까지 직접 가서 앉아볼 수 있었고, 첫날 사용할 답안지 묶음을 확인할 수도 있었습니다. 주최측은 개막식이 끝나자마자 몇 시간만에 시험장으로 바꾸는 기적을 이루어 냈습니다.
시험일 (7월 9일 월요일, 10일 화요일)
시험장에서 화이팅을 하는 우리 대표학생들. 주최측에서 촬영하여 IMO2018 페이스북 페이지에서 공개하였다. 왼쪽부터 송승호, 조영준, 김다인, 김홍녕.
시험은 이틀간 아침 9시부터 1시 반까지 4시간 30분으로 예정되어 있었습니다. 늘 그렇듯 아침 일찍 호텔 식당의 줄이 매우 길고 혼잡하였습니다. 첫날 혼란을 본 이후 둘쨋날은 호텔에서 아침 식사를 좀더 일찍부터 제공하였습니다.
첫째날은 시험보는 동안 부단장팀 교수와 조교들은 주최측에서 제공한 단체 관광을 가느냐 아니면 학생들처럼 어딘가 감금되어 학생들이 풀고 있는 문제를 받아서 생각하느냐 선택이 주어졌습니다. 루마니아까지 갔는데 관광을 한 번은 가야하니 다들 관광을 갔지만 몇몇 의욕이 있는 분들은 관광을 포기하고 문제를 몇 시간 먼저 보기 위하여 남았습니다. 우리 조교 김재형 학생 역시 관광을 포기하고 문제 풀기를 선택하였습니다. 이번 관광지는 Turda Salt Mine이라는 소금 광산인데 신비로운 곳이었습니다. 경찰차가 부단장팀 관광버스가 거기까지 가는 동안 한 번도 정차하지 않도록 모든 신호와 교차로를 통제해주어 정말 빠르게 이동할 수 있었습니다. 관광 끝나고 오니 1시였는데, 학생들 시험이 예정보다 30분쯤 늦게 시작되어 2시나 되어서야 학생들이 시험장을 빠져나왔고 그 동안 밖에서 한참을 기다렸습니다.
둘째날은 첫날의 혼란이 수습이 되었는지 시험은 정시에 시작되었습니다. 둘째날은 단체 관광이 없어서 부단장팀 교수님들과 조교는 옆 건물에 가서 9시 반부터 문제지를 받아서 구경(?)을 하고 있었습니다. 생각보다 문제가 풀만한 것이 많았습니다. 매년 그렇듯 단장팀에 계신 분들은 둘째날 시험 중 질의응답 시간이 끝나야 부단장들과 학생들을 만날 수 있습니다. 학생들을 기다리다가 단장팀에 계셨던 교수님들을 시험장 밖에서 만날 수 있었습니다. 학생들이 호텔 음식을 지겨워하여 그날 저녁은 Nobori라는 일식당에서 먹었습니다.
Coordination (7월 11일 수요일, 7월 12일 목요일)
시험이 끝나면 그 다음날부터 이틀간 학생들은 가이드와 함께 주최측이 제공하는 단체 관광을 다닙니다. 하지만 이때부터 단장팀 부단장팀 교수 및 조교들은 매우 바빠집니다. 채점이 진행되기 때문이지요.
보통은 단장팀의 경우 둘째날 시험이 있을때 부단장팀과 학생들이 있는 호텔로 옮겨오는 경우도 많았는데, 올해는 특이하게도 전혀 그런 배려가 없었습니다. 채점 협상(coordination) 역시 단장팀이 묵는 호텔에서 진행되었기 때문에 부단장들은 하루 한 번 제공되는 편도 30분 버스를 타고 학생들로부터 멀리 떨어진 호텔로 이동을 하여야 했습니다. 결국 우버를 애용할 수 밖에 없었지요. 단장팀과 부단장팀 교수들이 서로 협의할 일이 많은데 서로 먼 곳에 있어서 일하기가 매우 힘들었습니다. 게다가 단장팀 분들은 학생들 만날 기회가 너무 적었습니다.
우리팀의 문제별 coordination 일정은 아래와 같았습니다.
수요일
10시: 2번
12시: 4번
3시 30분: 1번
5시 30분: 5번
목요일
10시: 3번
12시: 6번
보통은 하루 3개씩 이틀간 하는 경우가 많았는데 올해는 더 촉박하게 진행되었습니다. 그 이유는 최종 단장 회의를 목요일 오후 3시 반에 진행하기로 하였기 때문이었습니다. 보통은 모든 점수와 메달을 확정하는 최종 단장 회의를 저녁 먹은 이후에 하였는데, 이번에는 상장 인쇄 시간의 편의 등을 위하여 당긴 것으로 보였습니다.
그래서 화요일 오후부터 학생들 답안지를 공식채점기준표에 맞추어 검토하느라 매우 바쁜 시간을 보냈습니다. 아무튼 여러 우여곡절과 드라마 끝에 한국팀의 성적이 확정되었지요. 모든 채점과 Jury Meeting이 끝난 후 학생들과 이탈리안 레스토랑에서 다시 한번 회식을 하기도 하였습니다.
시상식 (7월 13일 금요일)
시상식이자 폐회식은 7월 13일 오후 2시 30분부터 2시간동안 진행되었습니다. 폐회식동안 저는 가져간 캠코더로 촬영하는 역할을 주로 하였습니다. 공간이 좁은 곳으로 옮겨져서 장소의 중앙 홀에는 메달을 받는 학생만 앉아있고 관중석에 메달을 못 받은 학생들과 단장팀, 부단장팀이 앉아았었습니다. 주최측의 대회 이해가 조금 부족하여 단장팀 부단장팀을 격리시켜놓는 바람에 같이 앉지도 못하는 일도 있었습니다.
보통 그렇듯이 올해도 시상은 점수 순으로 이뤄졌습니다. 동메달 제일 낮은 점수부터 시작하여 점점 점수가 올라가는 식이지요. 국제수학올림피아드에서는 참가 학생의 절반 정도에 금,은,동메달을 주는데 금, 은, 동의 비율이 1:2:3으로 정해져 있습니다. 즉 전체 학생이 600명 가량이니 동메달 이상 받는 300명 가량의 학생들은 앉을 자리가 미리 점수 순으로 지정되어 있었지요.
문제가 어려웠음에도 만점을 받은 학생이 2명이 있었습니다. 영국팀의 Agnijo Banerjee, 미국팀의 James Lin 이 두 학생은 모든 문제를 다 해결하여 제일 앞에 앉았습니다.
시상식 중 한국대표학생들 메달 받는 모습
개회식처럼 시상식 역시 루마니아 국영방송으로 생중계 되었습니다.
7월 13일 열린 시상식 동영상 (국영방송에서 촬영)
시상식이 끝나고 단체사진을 찍었습니다.
시상식 끝난 후 찍은 단체사진. 뒷쪽 왼쪽부터 김다인, 조영준, 이송운, 최수영, 송승후, 김홍녕, 강지원. 앞쪽 왼쪽부터 이승훈, 송용진, 김재형, 엄상일
시상식이 끝난 후에는 단장팀이 묵는 숙소에서 파티가 있었습니다. 단장팀 부단장팀 쪽과 학생들 가는 쪽이 나뉘어졌는데 단장팀 부단장팀 가는 쪽은 클래식 음악과 전통음악 연주를 들으면서 식사를 하였지만 학생들이 있는 쪽에서는 EDM 디제잉이 있어서 매우 흥겨운 시간을 보냈습니다. 우리 학생들도 가이드와 함께 인파 속에서 흥겨운 시간을 보냈습니다. 몇몇 분들은 다음날 다리에 쥐가 났다고 할 정도였지요. 사진 공개는 하지 않겠습니다.
귀국 (7월 14일)
클루지나포카에서 비행기를 타고 독일 뮌헨으로 이동한 후 루프트한자 항공을 이용하여 되돌아 왔습니다. 하지만 독일로 이동하는 비행기가 연착이 되어 비행기를 못 타게 될지 매우 걱정이 많았습니다. (사실 비행기 놓쳐서 하루밤 자고 뮌헨 구경하고 가길 희망하는 사람도 있었습니다.) 빠듯하게 비행기를 갈아타다보니 몇몇 학생들의 짐이 제 시간에 연결되지 않았습니다. 그 중 일부는 메달을 짐가방 안에 두었었기 때문에 올해 공항 단체사진 찍을때는 메달이 없었습니다. 마지막이라 아쉬워하며 눈물을 흘린 학생도 있었습니다. 다들 집에 가는게 아쉬웠는지 계속 이야기 나누고 사진 찍으며 공항에서 긴 시간을 보냈습니다.
인천공항에 도착하고 나서 찍은 사진. 뒷쪽 왼쪽부터 연경남, 김재형, 강지원, 조영준, 이송운, 김홍녕, 김다인, 송승호, 엄상일, 이승훈, 송용진, 최수영
Mac OS X 10.13의 기본 한글입력기를 더 편리하게 사용하려고 Karabiner-Elements를 설치한 후 설정을 만들어 보았습니다. 원래 Karabiner라는 프로그램을 사용하여 잘 쓰고 있었는데 Mac OS 버젼이 올라가면서 이 프로그램은 더 이상 지원되지 않았고 대체하는 새 프로그램인 Karabiner-Elements가 처음에는 기능이 약하여 쓸 수 없었는데 이제 원하는 것이 대충 되는 것 같습니다.
아래와 같이 설정하면 다음 기능을 사용할 수 있습니다.
기능
Shift-Space로 한영 전환. 단, 자체 한글 입력 기능이 있는 Aquamacs와 Vmware Fusion에서는 Shift-Space 한영 전환을 막는다. (수정하면 VirtualBox, Parallels 등 자체 한글입력기능이 있는 프로그램에서 Shift-Space가 먹지 않도록 할 수 있습니다.)
한글 모드에서 Ctrl키를 누르면 일시적으로 영문으로 전환되도록 하여서 한글 모드에서도 Ctrl-A과 같은 단축기를 누를 수 있게 한다. (Mac OS에서는 기본 한글입력기에서 Ctrl-A를 누르면 Ctrl-ㅁ으로 인식하여 아무 일도 일어나지 않습니다.)
Aquamacs와 VMWare Fusion에서는 한글 모드에서 Shift-Space를 누르면 영문으로 전환해준다. 그 외에는 자체 한글입력기능이 동작하도록 아무 것도 하지 않는다. 2018년 8월에 추가된 기능입니다. 이렇게 하는 이유는 간혹 한글 모드에서 Aquamacs로 들어간 경우 영어로 다시 전환되지 않아서 불편했기 때문입니다.
아래 설정에서는 한글 전환키가 Mac OS 기본인 Option-Ctrl-Space가 한글전환키라고 가정한 것입니다.
설치방법: 아래 내용을 ~/.config/karabiner/assets/complex_modifications에 myfile.json이라는 식으로 json 확장자로 넣은 후 Karabiner-Elements 설정 화면에서 “Complex Modifications” 탭에서 Add rule을 눌러 세 가지 설정(Change shift space to shift+control+space, Make control key work in Korean mode, Make shift-space to make English mode in Aquamacs or VMWare)을 모두 선택하여 넣으면 됩니다.
수정 (2022년 2월 14일): ctrl 키 누를때 영어로 잠깐 바뀌었다가 오는 기능 부분에서 한글로 다시 전환되지 않는 문제가 있었는데 한줄 추가하여 문제를 해결하였습니다. 오랜만에 macOS Monterey 12.1 M1에서 써보는데, 잘 되네요.
수정 (2024년 3월 9일): macOS Sonoma 14.4로 업그레이드 한 후 한글 전환기가 기존 Shift-Ctrl-Space에서 Ctrl-Option-Space로 변경되었습니다. 그에 따라 본문 내용과 설정 내용을 수정하였습니다.
KAOS재단에서 운영하는 대중강연 시리즈인 2017 가을 카오스 강연에 참여할 기회가 있었습니다. 이번 2017년 가을의 주제는 미래과학이라서 “미래의 수학자”라는 제목으로 컴퓨터를 사용한 증명 등 앞으로 수학자들의 일상이 어떻게 될지 생각해보면서 강연을 하였습니다. 강연은 2017년 10월 18일에 있었고, 강연비디오가 youtube에 올라와 있습니다.
2009년, 2011년, 2012년, 2016년에 이어 2017년 브라질 리우데자네이루에서 열린 제58회 국제수학올림피아드에 다녀왔습니다. 올해는 111개 나라에서 총 615명의 학생들이 참가하여, 역대 최대 참가자수였던 작년의 602명 기록을 조금 더 넘겼습니다. 예전처럼 올해도 간략하게 참가 후기를 적어볼까 합니다.
우리나라는 1988년 호주에서 열린 29회 대회부터 참가하였는데, 올해는 2012년에 이어 역대 두 번째로 우리 나라 학생 전원이 금메달을 받음과 동시에 총점으로 세는 국가별 랭킹에서 1위를 차지하는 성과를 냈습니다. 올해 참가한 우리나라 대표 학생들은 모두 서울과학고 학생으로 아래와 같습니다.
김다인, 김세훈, 백승윤, 안정현, 이송운, 최규현
이 중 김세훈 학생은 올해 세 번째 출전으로 은메달 하나와 금메달 2개를 받게 되었습니다. 백승윤 학생은 두 번째 출전으로 은메달 하나와 금메달 하나를 받게 되었습니다. 나머지 4명의 학생은 올해 처음 출전이지만, 작년부터 우리나라 대표팀이 참가하기 시작한 루마니아 수학 마스터 대회(Romanian Master of Mathematics)에 출전한 적이 있어 국제대회의 긴장을 이미 경험해 보았습니다. 대표 6명에는 들지 못했지만 최종 후보로 뽑혔던 그 밖의 7명의 학생들은 아래와 같습니다. 이 중 고경명 학생은 세종과학고이지만 다른 학생은 모두 서울과학고였습니다. 다른 학교에서도 분발하면 좋겠습니다.
강지원, 고경명, 김준곤, 명기범, 박주영, 안재준, 이정호, 조민기
이번 한국대표팀 단장팀에서는 IMO 자문위원회 위원이기도 한 인하대 송용진 교수님과 유원대 이승훈 교수님이 문제 번역 등으로 수고를 하셨습니다. 부단장팀에서는 올해 대한수학회 올림피아드 사업이사를 맡고 있는 아주대 최수영 교수님과 저, 그리고 KAIST 학생이자 2013년 국제수학올림피아드 대표였던 이종원 학생이 있었습니다. 또한 한국과학창의재단 김기상 박사님도 오셔서 도와주셨습니다. 이번 국제수학올림피아드 문제별 분야와 출제자는 아래와 같습니다. 참고로 분야 옆에 붙은 번호는 Short List라고 해서 문제 후보를 분야별로 정리한 목록에서 분야별로 몇 번 문제인지를 적은 것입니다. 보통 숫자가 클 수록 어려운 문제로 생각합니다.
(정수1) 남아프리카공화국 Stephan Wagner
(대수6) 알바니아 Dorlir Ahmeti
(조합5) 오스트리아 Gerhard Woeginger
(기하2) 룩셈부르크 Charles Leytem
(조합4) 러시아 Grigory Chelnokov
(정수8) 미국 John Berman
최근부터 국제수학올림피아드에서는 1, 2, 4, 5번 문제는 정수, 대수, 조합, 기하 분야 한 문제씩 골고루 내고 있고, 더 어려운 3, 6번 문제는 따로 선정하고 있습니다. 이번에도 그런 규칙에 따라 문제가 출제되었습니다. 다만 보통 기하가 적어도 두 문제가 나왔는데 이번에는 쉬운 문제 하나만 나왔다는게 이변 아닌 이변이었습니다. 아울러 이번 3번 문제는 7점을 받은 사람이 고작 2명뿐이라 역대 최고로 어려웠던 문제로 기록되었습니다. 아쉽게도 우리나라 대표학생 중에서는 푼 사람이 없었고 부분점수 1점 받은 사람만 있었습니다.
동영상 촬영 중
오늘의 문제. #이렇게까지?
이번에는 특별히 현지에 참가한 조교인 이종원 학생이 해설하는 국제수학올림피아드 풀이 동영상을 제작하였습니다. 유난히 쉬운 4번 문제만 동영상이 3분 정도이며 다른 동영상은 대체로 8분~12분 정도입니다. 동영상을 촬영하는데 메모도 없이 한 번에 술술 해설해서 놀랐습니다. 이종원 학생은 현지에서도 학생들에게 매일 풀어볼 문제도 만들어주고 나중에 채점 과정에서도 큰 기여를 하는 등 수고가 많았습니다.
이번 상위권 나라 성적은 아래와 같습니다. 우리가 1위 했던 2012년의 경우 우리는 209점 2위 중국은 195점으로 14점 차이였는데 이번은 11점 차이입니다. 이번에는 문제가 어려워서 점수가 많이 내려갔습니다. 참고로 우리가 2위를 했던 2016년의 경우 우리는 207점, 미국이 214점이었습니다.
1위 170점: 한국
2위 159점: 중국
3위 155점: 베트남
4위 148점: 미국
5위 142점: 이란
6위 134점: 일본
공동 7위 131점: 싱가포르, 태국
공동9 위 130점: 대만, 영국
10위 128점: 러시아
태국대표단과 Joint Camp
2012년 아르헨티나 대회에도 워낙 먼 거리를 감안하여 이틀 일찍 현지에 가서 시차적응을 했습니다. 이번에는 아예 7월 11일에 출국하여 현지에서 태국 대표팀과 함께 며칠간 현지 공동 캠프를 진행하였습니다. 저는 여기까지는 참석하지 않았고 최수영 교수님이 대표 학생들 인솔 등으로 처음 가보는 브라질 현지에서 큰 수고를 하셨습니다. 저는 창의재단 김기상 박사님과 함께 7월 15일 출국하여 현지에 16일에 합류하였습니다. 이번 국제수학올림피아드가 열린 호텔은 Barra da Tijuca의 해변에 위치한 Windsor Oceânico 호텔이었습니다. 개막식, 폐막식, 시험 등이 모두 같은 호텔에서 열려서 매우 편리하였습니다. 참고로 작년 홍콩 대회의 경우 숙소는 홍콩과기대 기숙사였습니다. 이 곳 해변은 그 길이가 18 km로 매우 길고 비록 계절은 겨울이지만 따뜻한 날씨 덕에 많은 이들이 해수욕을 즐기고 있었습니다. 동네가 워낙 좋은 동네라 물가가 비싸서 애를 먹었습니다. 개막식 (7월 17일)
7월 17일 국제수학올림피아드 개막식 무대에 올라간 한국대표단 학생 (왼쪽부터 안정현, 백승윤, 김세훈, 최규현, 이송운, 김다인) 및 한국대표팀 가이드, 사진: Davi Campana/R2
우리 학생들의 개막식 입장 동영상을 찍었습니다. 한편 주최측에서 촬영한 1시간 13분짜리 동영상도 올라왔습니다. 우리 학생들은 47분쯤에 나옵니다.
제58회 국제수학올림피아드 개막식
시험 (7월 18일, 19일)
첫날 시험 시작 대기 모습. 사진: Davi Campana
시험은 9시부터 1시 30분까지 4시간 30분동안 열릴 예정이었습니다. 시험 30분 전까지는 다들 입실해야 된다고 들어서 열심히 준비시켜 학생들을 보냈는데, 9시 직전까지 입실하지 않은 학생들이 꽤 많았습니다. 특히 휴대품 검사에 시간이 많이 소요되어 시험은 한참 늦게 시작되었습니다. 결국 점심식사도 매우 늦었습니다. 둘째날인 19일에는 첫날보다는 좀더 순조롭게 시험이 시작되어 좀더 일찍 시험이 끝났습니다. 학생들이 첫날 시험을 보는 동안 전통에 맞게 부단장팀은 주최측이 주선한 관광을 다녀왔는데 별로 기억에 남는 것이 없습니다. 리우데자네이루에서 가장 유명한 예수상은 가지 않고 축구경기장과 시내 멋있는 거리를 잠깐 걸어 산책한 것이 전부였습니다. 학생들은 21일에, 단장팀은 22일 오전에 똑같은 관광을 갔습니다. 이제까지 제가 가본 국제수학올림피아드에서는 보통 학생들 시험이 끝나는 날 단장팀이 학생들이 있는 호텔로 이동해서 함께 지내는 것이 보통이었는데 이번에는 특이하게도 학생은 IMO 호텔에 두고 부단장팀은 전원 단장이 있는 호텔로 이동하게 되었습니다. 학생들은 브라질 대학생인 현지 가이드에게 잘 부탁하고 부단장팀은 짐을 꾸려 같은 해변이지만 3km 떨어진 Windsor Marapendi 호텔로 이동하였습니다.
Coordination (7월 20일, 21일) 및 Jury Meeting (21일)
4번 문제 협의중
채점하여 점수를 협의하는 과정을 Coordination이라고 합니다. 각국 단장 부단장들과 주최국에서 준비한 Coordinator들과 지정된 시간에 만나 미리 정해진 채점 기준표에 따라 점수를 협의하는 과정을 이틀간 진행합니다. 이번에는 학생들이 잘 해서인지, 혹은 딱히 부분점수를 크게 따져야할 풀이가 없어서인지, 이 과정이 매우 쉽게 끝났습니다. 작년엔 점심도 굶어가며 몇번씩 같은 문제로 coordination room에 다녀오곤 했는데 올해는 한 번에 모두 일사천리로 해결되어 21일 오전에 우리팀은 모두 끝나서 잠깐 오후에 시내 관광을 나갔다 올 여유도 있었습니다. 이미 그때 우리 팀이 1등할 가능성이 매우 높다는 것을 알 수 있었습니다. 21일 저녁 있었던 Jury Meeting에서 금메달 커트라인이 우리 팀 예상보다 훨씬 아래여서 놀랐고 여유있게 1등을 해서 기뻤습니다. 이 이틀동안 학생들은 브라질의 필즈메달 수상자인 아빌라 교수의 강연도 듣고 관광도 다녀왔습니다.
시상식 (22일) 개막식때는 보통 학생들이 나라별로 착석하고 무대에 나라별로 올라가서 인사를 합니다. 하지만 시상식때는 학생들이 점수순으로 착석하고 동메달부터 낮은 점수부터 순서대로 무대를 올라갑니다. 우리 학생들은 워낙 뒤에 올라가게 되어 있어서 한참을 기다렸습니다. 앞줄에 있던 네덜란드 분들이 사진기 들고 언제 나가야 하나 고민하는 우리를 보면서 너희들은 아직 멀었으니 한참 기다려라고 하며 웃었습니다. 이번에는 IMPA Olympiad Girls’ Award라고 해서 각 대륙별로 여학생 참가자 중 가장 잘 한 학생에게 특별상을 하나씩 주었습니다. 아시아 대륙을 대표해서 우리나라 김다인 학생이 수상했습니다. 여학생 중 유일한 금메달이었으니 당연한 일이었습니다. 한편 보츠와나 대표로 나온 박가람 학생이 아프리카 대표로 이 상을 받았습니다.
IMPA 여학생상 수상
한편 29점 동점으로 나란히 금메달 받으러 올라가던 김세훈 안정현 학생은 김다인 학생을 가마를 태워서 입장해서 큰 박수를 받았습니다.
주최측에서 촬영한 폐막식 동영상이 나중에 올라왔습니다. 1시간 43분 분량입니다. 1시간 20분 지점 근처를 보세요.
제58회 국제수학올림피아드 폐막식
이번 국제수학올림피아드의 개인 1등은 5문제를 해결한 세 명이 했습니다. 이란, 일본, 베트남 대표였는데, 그 중 Yuta Takaya라는 일본 대표는 올해 국제수학올림피아드에서 최고점으로 1등했을 뿐만 아니라 올해 이란에서 열린 국제정보올림피아드에서도 최고점으로 1등을 하여 화제가 되었습니다. 국제정보올림피아드에 4번 출전하여 모두 금메달을 받았고 국제수학올림피아드에는 3번 출전하여 은메달 하나와 금메달 둘을 받았습니다.
귀국 (23일) 비행기 시간이 너무 밤 늦게 있어서 23일 낮에는 “빵산”이라고 불리는, Sugarloaf mountain을 다 함께 다녀왔습니다. 그 후 30시간이 넘게 비행기를 타고 애틀란타를 경유하여 한국으로 잘 돌아왔습니다. 현지 출발은 23일이지만 한국 도착은 25일이었습니다. 30시간동안 씻지 않으면 어떻게 되는지 아래 사진에서 확인할 수 있습니다. 도착 직후에 중앙일보, 동아일보 기자와 학생들 사이의 인터뷰도 있었고, 대한수학회 이향숙 회장님 등 여러 분들의 환대도 있었습니다.
2017년 가을학기 교과목 수강신청기간을 맞이하여 지난 학기에 하였던 것처럼 이번 2017년 가을학기에 열릴 이산수학/그래프이론 관련 교과목 및 기타 흥미로운 교과목을 정리해봅니다.
MAS477 Introduction to Graph Theory (그래프이론개론). 월수 13:00~14:15, 엄상일
(네, 아시다시피 제가 하는 과목입니다.) 보통 매년 가을학기에 열렸으며 제가 연구년을 갔던 2013년에는 Andreas Holmsen 교수님이 강의를 하셨었고 작년에는 대수적 그래프이론 전공한 Brendan Rooney 교수님이 강의를 하였습니다. 2년만에 다시 하게 되었습니다.
그래프이론의 다양한 부분을 다룹니다. 보통 많이 생각하는 기초적인(?) 해밀턴 회로 오일러 회로 같은건 다루지 않습니다. 주요 내용을 언급하면 아래와 같습니다.
그래프 connectedness: 그래프가 얼마나 잘 연결되었는지, 그리고 한 점에서 다른 점으로 몇 개의 서로 겹치지 않가 있는지와 같은 Menger 정리 등.
그래프의 매칭: 남녀 학생을 짝지울때 써먹는(?) 홀의 결혼정리와 König의 정리, 그리고 남녀가 아닌 일반적인 그래프의 perfect matching에 관한 Tutte의 정리, 그리고 그래프의 maximum matching이 어떤 구조인지 설명하는 Gallai-Edmonds Structure 정리와 함께 Edmonds의 유명한 다항식 시간에 maximum matching 찾는 알고리듬을 다룹니다.
평면그래프: 이산수학 시간에는 정리만 배웠던 Kuratowski 정리를 엄밀하게 증명합니다. 오일러 공식 및 dual에 대해 다룹니다.
채색 문제: 4색정리5색정리를 증명합니다. List Coloring도 배우며 이를 통해 Thomassen의 다른 방식의 5색 정리 증명도 배웁니다. 그리고 perfect graph에 관한 성질도 배웁니다.
Flow 문제: 채색문제의 dual이라고 할 수 있는 nowhere-zero flow에 관해 배우고 관련된 Tutte의 유명한 추측들을 다룹니다.
그외 시간에 따라 다룰 가능성이 있는 주제: Turan 정리, Hadwiger 추측, Szemeredi의 Regularity lemma, Higman의 lemma, Kruskal의 well-quasi-ordering 정리, Robertson과 Seymour의 그래프 마이너 정리
MAS583C Topics in Analytic Combinatorics (해석조합론), 화목 10:30-11:45, 김동수 교수님
예전에 1학점 특강으로 잠깐 개설된 적이 있던 주제인데 이번에 처음 3학점 특강 과목으로 개설되었습니다. 학부 고년차나 대학원생의 경우 학부때 배우는 복소 과목이 어떻게 조합론에서 쓰일 수 있나 알아보는 기회가 되겠습니다. 특히 어떤 조합적 대상의 수를 asymptotic하게 새는 도구들을 배우게 된다고 보시면 됩니다. 과목을 마치게 되면 생성함수를 잘 다루게 될 것이고, 생성함수를 복소평면 위에서의 함수로 이해한 다음 singular point들을 찾아서 분석하는 기술을 습득하게 될 겁니다. 그 외에 다른 재미있는 주제가 있을 것 같습니다.
The Theory of Computation provides a sound logical foundation to computer science. By comparing various formal models of computation with respect to their capabilities, it identifies both fundamental features and ultimate limitations of contemporary digital computing machinery. Rigorous notions of efficiency are captured by famous complexity classes such as P and PSPACE; and concepts like oracles or polynomial-time reduction permit to compare computational problems with respect to their algorithmic cost: NP-hardness results thus serve as ‘beacons’ of intractability.
EE412 빅데이터 분석 개론 (신진우 교수님)
EE488A 머신러닝 소개 (유창동 교수님), EE488B 딥러닝과 알파고 (정세영 교수님), CS492E 기계학습입문 (양은호 교수님): 전기전자 및 전산학부 과목인데, 비슷한 주제로 세 과목이 열리네요.
EE817 Network Science (박홍식 교수님):
In the first half we deal with fundamental network and graph theory and then study generation, characteristics and analysis of various types of networks such as regular, random, small-world, and scale-free network. In the second half, we study dynamic processes on networks including phase transition, resilience, synchronization, epidemic spreading and information spreading in social networks.
MAS711 암호 및 부호이론 (한상근 교수님)
EE623 정보이론 (정혜원 교수님):
This course is a graduate-level introduction to information theory. Information theory is one of the most elegant mathematical theories, with a direct and significant impact to our lives in the information age. In this class, we will learn how to model the information transmission/processing system, with applications of data science as well as communications, and analyze the model from information-theoretical perspectives to derive fundamental limits on what is possible on the system.
전산학부의 기본 과목 중 관련 과목: CS204 이산구조, CS300 알고리듬 개론
최적화 관련 산업및 시스템 공학과 교과목들: IE539 컨벡스 최적화 (김우창 교수님), IE631 정수계획법 (박성수 교수님)
조합적 디자인 문제에 최근 좋은 결과들이 나오고 있습니다. 몇 년 전 Peter Keevash 교수가 150년 전의 문제인 Generalized Steiner System에 관한 문제를 해결한 후, 이를 확장하는 연구 결과가 최근 S. Glock, D. Kühn, A. Lo, D. Osthus에 의해 증명되었습니다.
각 꼭지점의 차수가 3인 평면 그래프의 제곱을 7색으로 칠할 수 있다는 덴마크 DTU의 Carsten Thomassen 교수의 결과를 다루었습니다. 즉, 어떤 평면 그래프에서 각 꼭짓점에 이웃한 다른 꼭짓점의 수가 정확히 3이면, 거리가 2 이하인 두 점은 서로 다른 색이 되도록 7개 색 이하만 사용하여 칠할 수 있다는 정리입니다.
Asymmetric TSP 문제의 constant factor approximation algorithm이 처음으로 나왔다는 소식을 전했습니다. 풀어쓰자면, n개 도시를 모두 각각 한 번씩 들르고 출발점으로 최소 비용으로 돌아와야 하는 외판원 문제(Traveling Salesman Problem)의 최적값의 5500배 이내의 비용임을 보장해주는 경로를 찾아주는 효율적인 알고리듬이 나왔다는 소식입니다.
2년~3년 정도 주기로 열리고 있는 과목입니다. 국내에서는 KAIST에서만 볼 수 있는 과목으로 이산기하 전공하신 교수님으로부터 잘 배울 수 있습니다. 흥미로운 증명과 주제들이 많습니다. 마지막으로 열린 것은 2014년 봄입니다. 특별한 선수과목은 없지만 이산수학을 들어두었으면 수학적 내공이 충분하지 않을까 생각됩니다.
강의 설명:This course is an introduction to discrete geometry. We will cover basic results from packing and covering, convex polytopes, intersection patterns of convex sets, and combinatorial geometry. Our goal is to reach some key results by combining methods from linear algebra, topology, and probability. However, since this is an introductory course, all necessary notions will be introduced. The main prerequisite for this course is a basic understanding of elementary discrete mathemtaics and the n-dimensional Euclidean space.
교재: Jiří Matoušek, Lectures on Discrete Geometry (Springer, GTM 212). http://link.springer.com/book/10.1007%2F978-1-4613-0039-7
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
교재: Chris Godsil, Gordon Royle, Algebraic Graph Theory, Sringer, GTM 207. http://link.springer.com/book/10.1007/978-1-4613-0163-9
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
KAIST에서는 적어도 최근 10년간은 열린 적이 없는 과목이고 앞으로도 언제 다시 열릴지 알 수 없는 과목입니다. Algebraic Graph Theory를 전공하였고 교재의 저자인 Chris Godsil 교수로부터 박사학위를 받은 Brendan Rooney 교수님이 강의하실 예정이라 기대가 됩니다.
중요한 선수과목은 선형대수학개론 혹은 선형대수학입니다. 행렬의 eigenvalue 관련된 내용을 숙지하고 spectral decomposition 같은 것들도 잘 알고 있으면 좋습니다.
MAS575 Combinatorics (조합수학), 화목 10:30~12:00, 엄상일.
주교재: S. Jukna, Extremal Combinatorics, Springer-Verlag http://link.springer.com/book/10.1007%2F978-3-642-17364-6
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
여러 기술들이 조합수학의 정리를 증명하는데 어떻게 활용되는지 다양하게 살펴봅니다. 선형대수 활용하는 방법, 다항식의 성질을 활용하는 방법, 램지 정리 관련, 확률을 활용하는 방법 등 다양한 주제를 다룹니다. 이산수학, 선형대수학개론을 수강한 학생이 듣는 것이 좋으며 가을마다 열리는 그래프이론개론을 수강했었다면 좀더 수월할 수도 있지만 내용은 독립적입니다.
2년마다 한 번씩 봄에 열리며, 학부생이나 대학원생 모두 수강 가능합니다.
MAS583C 수학특론 Parameterized Algorithms and Lower Bounds (매개변수 고정 알고리즘과 하한), 수 16:00~17:30, 금 10:30~12:00, Helmut Alt 교수 및 Otfried Cheong 교수
전산학과 CS700과 교차개설된 과목입니다. 강의실도 전산학부 건물에서 열립니다. 독일 베를린자유대학 Helmut Alt 교수님이 KAIST 오셔서 강의하십니다.
비슷한 과목은 2014년 봄에 수리과학과에서 제가 MAS583B Fixed-Parameter Algorithms라는 제목으로 연 적이 있습니다. 내용은 비슷하지 않을까 생각합니다. 그래프이론과도 관련이 많고 제 연구와도 관련이 많습니다.
교재: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer. http://link.springer.com/book/10.1007/978-3-319-21275-3
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
2016년부터 수학동아에 “따끈따끈한 수학”이라는 코너를 연재하기로 하였습니다. 목표는 이산수학 분야의 따끈따끈한 논문 소식들을 중학생 수준에서도 읽을만하게 적는 것입니다. 사실 그게 말처럼 쉬운 것은 아니지만요. 현재까지 실린 글과 앞으로 실릴 글을 예고하고 관련 논문을 정리했습니다. 혹시 글감으로 추천할 논문이 있으면 연락주셔도 좋습니다. 글이 길어져서 2017년 내용은 따로 분리하였습니다. 2017년 따끈따끈한 수학 내용 보기
작년 가을에 떠들석했던 그래프 동형 문제를 quasi-polynomial 시간에 풀 수 있다는 Babai 교수 결과에 대해 정리했습니다. (사실 기사 제목에 “P일까, NP일까?”로 나갔는데 잘못된 제목입니다. 정확하게는 “P일까 아닐까?” 정도가 좋겠죠. NP 대신 NP-hard라고 하든지 했어야 하는데 제목이 들어간 편집본을 꼼꼼히 검토하지 못했네요.)
2016년 4월에 arXiv에 올라온, n명이 케이크를 envy-free하게 나누면서도 나누는 칼질 횟수가 n에 관한 어떤 함수값 이하게 되는 최초의 방법을 소개했습니다. 1990년대 개발된 기존 방법은 n=4인 경우에도 칼질 횟수가 유한이긴 해도 매우 커질 수 있었습니다.
2015년 Annals of Mathematics에 실린 Erdős의 distinct distances 문제에 관한 Larry Guth와 Net Katz의 논문을 소개했습니다. 평면에 n개의 점이 있을때 그 점 중 두 점씩 뽑아서 만들수 있는 서로 다른 거리의 최소값은 얼마인가에 관한 문제입니다.
Bienia, W., Goddyn, L., Gvozdjak, P., Sebő, A., & Tarsi, M. (1998). Flows, view obstructions, and the lonely runner. Journal of Combinatorial Theory. Series B, 72(1), 1–9. doi:10.1006/jctb.1997.1770
{1,2,…,2n+1}의 부분집합 중 크기가 n것과 n+1인을 모아놓으면 거기서 만든 Hasse diagram 안에 해밀턴 회로가 있다는 가운뎃층 문제가 최근에 해결되었다는 소식을 전했습니다.
논문
Mütze, Torsten. (2016). Proof of the Middle Levels Conjecture. Proceedings of the London Mathematical Society. Third Series 112, no. 4 (2016): 677–713. doi:10.1112/plms/pdw004.
