essays
Posts in "essays"
Courses on Discrete Math / Graph Theory at KAIST on Spring 2026
Here is a list of some courses related to discrete mathematics and graph theory in the spring semester of 2026 at KAIST. MAS59903 Advanced Discrete Topology Mon/Wed 13:00-14:15 Andreas Holmsen Convex polytopes are fundamental geometric objects which appear in a wide variety of mathematical disciplines. In this course we give an introduction to basic methods and modern tools of polytope theory, focusing on combinatorial aspects. We will learn important examples and constructions (e.g. zonotopes, Minkowski sums, non-rational polytopes, fiber polytopes, and the Lawrence construction) and discuss important results and concepts such as Steinitz’ theorem, f-vectors, h-vectors, the upper bound theorem, and oriented matroids.
KAIST에서 2025년 가을에 열리는 이산수학/그래프이론 관련 교과목
예전에 이산수학/그래프이론 관련 교과목을 정리해서 올린 적이 있었습니다. 타 학과 특강으로 개설된 교과목을 눈여겨 보지 않을 가능성이 있어서 정리해봅니다. MAS.40077 Introduction to Graph Theory 그래프이론개론 화목 13:00-14:15 김재훈 (Jaehoon Kim) 매년 가을마다 열리는 과목입니다. MAS275나 CS204 등 이산수학 과목을 먼저 수강한 후에 듣는 것을 추천합니다. CS.49900 Special Topics in Computer Science <Algorithmic Graph Structure Theory> 월수 13:00-14:15 Sebastian Wiederrecht 그래프의 Tree-width, Branch-width, Tree-Independence Number, Clique-width, Rank-width, Directed Tree-width 등을 다룹니다. 실라버스를 보니 제 논문에 있는 Rank-width 관련 알고리듬도 다룰 듯 합니다.
허준이 교수 연구 결과가 어떻게 실생활에 응용이 되나요?
이번에 필즈상을 받은 허준이 교수의 업적이 어떻게 실생활이나 산업에 응용되는지 궁금해하시는 분들이 있어서 질문도 종종 받게 되네요. 순수수학 하는 사람들은 원래 흥미로운 수학적 현상의 본질적인 원리를 규명하려는 호기심으로 연구를 하기 때문에 응용 가능성을 생각하고 연구를 하는 것도 아니고 실제 응용이 되더라도 연구자 본인이 자기 연구가 어떻게 응용되는지 모를 수도 있습니다. 그렇지만 수학이라는 것이 활용이 되면 정말 파급이 큽니다. 우리가 이 글을 보기 위하여 인터넷을 접속할때부터 이 글을 읽을 때까지 정말 여러 곳에서 수학이 활용되고 있다고 할 수 있습니다. 아울러 수학은 오랜 시간이 지나 활용되는 사례도 여럿 있구요. 그러다보니 수학자들에게 이런 질문을 하면 100년이 지나면 사용될지도 모른다 같은 식의 모호한 답을 하기 마련인데 기자분들은 이런 답을 들으면 답답하실 거에요. 수학자들은 틀린 답은 안 하도록 직업적 훈련을 받는 사람들이라 아닌 걸 맞다라고 하진 못하거든요.
칠판 강연을 위한 연사 추적 카메라 설치 및 유튜브 생중계 경험담
코로나19 이후 세미나 및 강연을 온라인으로 중계하거나 동영상을 녹화하려는 수요가 많아졌습니다. IBS 이산수학그룹에서는 2018년 12월 시작할 때부터 세미나실에 연사 추적 카메라를 설치하여 동영상을 녹화하여 YouTube에 공개해왔고, 2020년 3월부터는 YouTube Live를 통하여 실시간 중계도 해왔습니다. 하지만 2018년에 만든 세팅에 화질, 음질 등 여러 가지 불만도 있어서 어떻게 개선해야 할지 고민이 많았는데 2022년 봄에 이사를 하게 되면서 새롭게 세미나실 셋업을 할 수 있는 기회가 생겨서 훨씬 더 좋은 셋팅을 할 수 있게 되어서 그 사항을 공유해드리고자 합니다.
KIAS 웹진 Horizon에 기고한 글 “2021 아벨상 수상자 로바스 라슬로”
2021년 아벨상 수상자 두 분 중 한 분인 로바스(Lovász László) 교수의 업적을 소개하는 글을 써서 KIAS 웹진 Horizon에 실었습니다. 2021 아벨상 수상자 로바스 라슬로
수학동아xIBS, 나의 삶 나의 수학 시리즈 인터뷰+기고
수학동아와 기초과학연구원(IBS)이 설립 10주년을 맞아 공동으로 IBS 내의 수학자들의 연구와 삶을 소개하는 시리즈를 시작하였습니다. 제 이야기로 그 시리즈 시작이 되었습니다. 내용은 수학동아 2021년 5월호나 IBS 홈페이지에서 볼 수 있습니다. 글을 다듬어주신 홍아름 수학동아 기자님, 그리고 멋진 사진을 찍어주신 AZA 스튜디오 남윤중 실장님 감사드립니다. 내용은 아래에서 볼 수 있습니다. 1편: 기자의 인터뷰 2편: 연구 경험담 제가 하던 수학 연구는 길게는 수년, 짧게는 수일 만에 완성되기도 했습니다. 그중 독일의 한 소도시에서 했던 연구는 단 하루 만에 답을 얻었습니다. 그래프 알고리듬 분야에서 유명한 브루노 쿠르셀 프랑스 보르도컴퓨터과학연구소(LaBRI) 교수님과 만났던 2004년 5월에 생긴 일입니다…
Big Congratulations to Bruno Courcelle for the first S. Barry Cooper Prize
“The 2020 S. Barry Cooper Prize is awarded to Bruno Courcelle for his work on the definability of graph properties in Monadic Second Order Logic, through a sequence of seminal papers and a book (joint with Joost Engelfriet). This forms an outstanding example of theory building, bringing together logic, computability, graph grammars, and various notions of graph width (tree-width, clique-width and rank-width) and opening new avenues in our understanding of graph structure theory and the computability and complexity of graph algorithms. Besides its foundational character, the work has had great impact on a number of areas of computer science, including in parameterized algorithmics, verification and other areas, and has influenced a generation of researchers in this field. It has straddled the divide between the logical and algorithmic aspects of theoretical computer science.”
기초과학연구원(IBS) 이산수학그룹 소개
기초과학연구원의 PRC 제도 2018년부터 기초과학연구원에서는 연구단장이 이끄는 큰 규모의 기존 연구단 형태와는 다른, 새로운 연구단 제도를 만들었습니다. 이 새로운 연구단은 PRC라고 불리는데 PRC는 Pioneer Research Center의 약자입니다. 기존 기초과학연구원의 연구단은 1~2명의 연구단장이 하나의 큰 연구단을 책임지고 운영하는 형태였습니다. PRC 형태의 연구단에서는 내부에 Chief Investigator, 약자로 CI로 불리는 여러 연구자가 독립적으로 운영하는 소규모 연구그룹을 만듭니다. 이 PRC 형태의 연구단의 연구단장은 거기에 속한 CI들이 돌아가며 맡기 때문에 PRC 자체는 여러 연구그룹을 모아놓는 우산과 같은 조직이 됩니다. 각 CI는 예산도 별도로 신청하여 받고 운영도 독립적으로 하지만, 같은 연구단 일은 같은 연구단 소속 다른 CI와 서로 협업을 통하여 운영합니다. 비유를 하자면 기존 연구단은 여러 연구팀으로 나누어 운영되는 경우가 많은데 PRC에서는 각 연구팀을 CI가 맡아서 독립적으로 운영한다고 생각하면 될 것 같습니다. CI를 한글로 어떻게 표시할 것인지에 대하여 의견 정리가 되지 않아서 한글 명칭은 없습니다.
수학동아 “따끈따끈한 수학” 연재 (2019년)
2016년부터 4년간 수학동아에 “따끈따끈한 수학”이라는 코너를 연재하였습니다. 소개된 논문을 정리한 글이 너무 길어져서 연도별로 분리하기로 하였습니다. 2016년 따끈따끈한 수학 내용 보기 2017년 따끈따끈한 수학 내용 보기 2018년 따끈따끈한 수학 내용 보기 2019년 1월호: 램지수 소식 김정한 교수님의 유명한 정리인 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 2019년 2월호: g추측이 해결되었다는 소식 Kadim Adiprasito 교수가 g추측을 해결하였다는 소식을 소개하였습니다.
수학동아 “따끈따끈한 수학” 연재 (2018년)
2016년부터 수학동아에 “따끈따끈한 수학”이라는 코너를 연재하고 있습니다. 소개된 논문을 정리한 글이 너무 길어져서 연도별로 분리하기로 하였습니다. 2016년 따끈따끈한 수학 내용 보기 2017년 따끈따끈한 수학 내용 보기 2019년 따끈따끈한 수학 내용 보기 2018년 1월호: Cops and robber game n*n 바둑판 모양의 그래프에서 도둑 한 명과 경찰 여러 명이 이웃한 꼭짓점으로 이동하면서 잡기 게임을 하는 cops and robber game에서 도둑이 경찰의 R배 속도로 움직일 때 잡기 위한 필요한 경찰의 수는 R이 충분히 크면 n^(c/log log n)보다 크다는 것을 증명한 논문 결과를 소개하였습니다. 논문 P. Balister, A. Shaw, B. Bollobás, B. Narayanan, Catching a fast robber on the grid, J. Combin. Theory Ser. B, 152(2017), 341-352. doi:10.1016/j.jcta.2017.06.009 2018년 2월호: 에라토스테네스의 체 에라스테네스 체 방법으로 1부터 N까지 소수를 찾을 때 필요한 공간의 양을 N^(1/3) (log N)^(2/3) 이하로 만든 Harald Helfgott 교수의 연구 결과를 소개하였습니다. 논문 Harald Andrés Helfgott, “An improved sieve of Eratosthenes”, arXiv:1712.09130, 2017 2018년 3월호: 원을 정사각형으로 만들기 원을 유한 개의 measurable 집합으로 분할하여 다시 재조립하여 정사각형을 만들 수 있다는 연구결과를 소개하였습니다. 논문 Grabowski, Ł., Máthé, A., & Pikhurko, O. (2017). Measurable circle squaring. Annals of Mathematics, 185(2), 671–710. doi:10.4007/annals.2017.185.2.6 2018년 4월호: 그래프의 acyclic edge coloring 관련 결과 평면 그래프의 maximum degree가 k이면 acyclic edge chromatic number가 k+2이하라는 2009년 Cohen, Havet, Müller의 추측을 Dan Cranston이 k 값이 420000000000000 이상이면 참이라고 증명하였다는 소식을 전하였습니다. 논문 D. W. Cranston, “Acyclic edge-coloring of planar graphs: Δ colors suffice when Δ is large,” arXiv:1705.05023, 2017. 2018년 5월호: 소인수분해 관련된 정수론 문제 1부터 x까지 자연수 중 중복을 허용하여 N개 자연수를 뽑았을 때 그중 일부를 곱하여 완전제곱수가 나올 확률이 1에 가깝게 되자면 N을 어느 정도로 잡아야 하는지에 관한 결과를 소개하였습니다. 논문 E. Croot, A. Granville, R. Pemantle, and P. Tetali, “On sharp transitions in making squares,” Ann. of Math., vol. 175, pp. 1507–1550, 2012. P. Balister, B. Bollobás, and R. Morris, “The sharp threshold for making squares,” Ann. of Math., vol. 188, 1-95, 2018. 2018년 6월호: 평면 위에서 거리 1 떨어진 점은 다른 색으로 칠할 때 필요한 색깔 수의 최솟값 관련 최신 결과 Aubrey de Grey가 최근에 평면의 chromatic number가 5 이상임을 증명하였다는 소식을 전하였습니다. 이 문제는 1950년 가을에 당시 18세로 시카고 대학 신입생이었던 에드워드 넬슨(Edward Nelson)이 만들었습니다. 4이상임은 알려져있었는데 5이상인 것을 증명하는 것을 그간 아무도 하지 못했었습니다. 논문 Aubrey de Grey, The chromatic number of the plane is at least 5, arXiv:1804.02385 Quanta Magazine https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/ 관련 polymath 링크 http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem 2018년 7월호: The Reverse Kakeya problem KAIST 전산학부 Otfried Cheong 교수님 및 공저자 분들이 한 연구 결과를 소개하였습니다. 방도 볼록하고 가구도 볼록한 모양이라고 할 때, 만일 그 방에 가구를 임의의 방향으로 놓는 것이 가능하다면 그 가구를 한 바퀴 돌리는 것도 가능한가? 이 1921년에 나온 문제를 풀었습니다. 논문 S. W. Bae, S. Cabello, O. Cheong, Y. Choi, F. Stehn, S. D. Yoon, “The Reverse Kakeya problem”, accepted for presentation at 34th International Symposium on Computational Geometry (SoCG 2018). 2018년 8월호: Oberwolfach 문제 해결 소식 1967년 Ringel이 제기한, 원형 테이블 여러 개 있는 곳에서 여러 사람이 모여서 워크샵을 할 때 정확히 딱 한 번씩만 서로 이웃해서 앉도록 일정을 짜는게 가능한지에 관한 Oberwolfach 문제를 Birmingham 대학의 김재훈 박사 등이 해결했다는 소식입니다. 논문 Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus, Resolution of the oberwolfach problem, Submitted, 2018. arXiv:1806.04644 2018년 9월호: 삼각형으로 정사각형 쪼개기 정사각형을 홀수 개의 넓이가 같은 삼각형으로 쪼개는 것이 불가능하다는 정리가 있는데 최근 그것을 확장하여 넓이가 최대한 비슷하게 삼각형으로 나눈다면 어디까지 할 수 있는지를 연구한 논문이 나왔다는 소식입니다. 논문 Jean-Philippe Labbé, Günter Rote, and Günter M. Ziegler, Area difference bounds for dissections of a square into an odd number of triangles, arXiv:1708.02891, 2018. 2018년 10월호: 그래프의 교차수(crossing number) 구하는 것이 어렵다는 결과 그래프를 평면에 그릴 때 필요한 최소의 교차점 수인 crossing number를 소개하고 관련 추측들을 소개하였으며, 심지어 이 수가 홀수인지 짝수인지 판별하는 것이 NP-hard라는 최신 결과를 소개하였습니다. 논문 S. Cabello and B. Mohar, Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput., 42 (2013), pp. 1803–1829, https://doi.org/10.1137/120872310. S. Cabello, Hardness of approximation for crossing number, Discrete Comput. Geom., 49 (2013), pp. 348–358, https://doi.org/10.1007/s00454-012-9440-6. Petr Hliněný and Carsten Thomassen, Deciding parity of graph crossing number, SIAM J. Discrete Math. 32 (2018), no. 3, 1962–1965. 2018년 11월호: 둘레도 넓이도 같은 두 삼각형을 찾아라! 일본 게이오대 박사과정 학생 두 명이 세 변의 길이가 모두 정수이면서 둘레의 길이와 넓이가 동시에 같은 정삼각형과 이등변삼각형이 어떤 것인지 밝힌 논문을 써서 뉴스에 나왔었습니다. 그 내용을 정리하였습니다. 논문 Yoshinosuke Hirakawa and Hideki Matsumura, A unique pair of triangles, J. Number Theory 194 (2019), 297–302. 2018년 12월호: 내접 사각형 문제 조르당 곡선(Jordan curve) 위의 4점으로 정사각형을 만들 수 있는가 하는 문제에서 시작하여 직사각형을 만들 수 있는지에 관한 최근 결과까지 소개 논문 A. Akopyan and S. Avvakumov, “Any cyclic quadrilateral can be inscribed in any closed convex smooth curve,” Forum Math. Sigma, vol. 6, pp. e7–9, 2018. C. Hugelmeyer, “Every smooth Jordan curve has an inscribed rectangle with aspect ratio equal to 3,” arXiv:1803.07417, 17-Mar-2018. B. Matschke, “A survey on the square peg problem,” Notices Amer. Math. Soc., vol. 61, no. 4, pp. 346–352, 2014.
2018년 제59회 국제수학올림피아드(IMO) 참가후기
2018년 루마니아 클루지나포카에서 열린 제59회 국제수학올림피아드에 다녀왔습니다. 국제수학올림피아드 참가는 저는 2009년, 2011년, 2012년, 2016년, 2017년에 이어 6번째입니다. 이번에는 107개 나라에서 총 594명의 학생이 참가하였습니다. 2016년, 2017년에는 600명이 넘었는데 조금 줄어들었지요. 예전에 적은 것처럼 올해도 후기를 적어볼까 합니다. 2012년 국제수학올림피아드 참가후기 2016년 국제수학올림피아드 참가후기 (사이언스북스 블로그 연재: 1편, 2편, 3편) 2017년 국제수학올림피아드 참가후기 2018년은 우리나라가 국제수학올림피아드에 참가한지 정확히 30년이 되는 해입니다. 올해는 대표학생 6명이 금메달 3개, 은메달 3개를 받았습니다. 학생들의 점수를 합하여 살펴보는 국가별 순위에서는 107개 참가국 중 7위라는 우수한 성적을 거두었습니다. 국가별 순위를 보면 아래와 같습니다.
2017년 카오스강연 “미래의 수학자”
KAOS재단에서 운영하는 대중강연 시리즈인 2017 가을 카오스 강연에 참여할 기회가 있었습니다. 이번 2017년 가을의 주제는 미래과학이라서 “미래의 수학자”라는 제목으로 컴퓨터를 사용한 증명 등 앞으로 수학자들의 일상이 어떻게 될지 생각해보면서 강연을 하였습니다. 강연은 2017년 10월 18일에 있었고, 강연비디오가 youtube에 올라와 있습니다. 강연 영상 재생목록