math
Posts in "math"
허준이 교수 연구 결과가 어떻게 실생활에 응용이 되나요?
이번에 필즈상을 받은 허준이 교수의 업적이 어떻게 실생활이나 산업에 응용되는지 궁금해하시는 분들이 있어서 질문도 종종 받게 되네요. 순수수학 하는 사람들은 원래 흥미로운 수학적 현상의 본질적인 원리를 규명하려는 호기심으로 연구를 하기 때문에 응용 가능성을 생각하고 연구를 하는 것도 아니고 실제 응용이 되더라도 연구자 본인이 자기 연구가 어떻게 응용되는지 모를 수도 있습니다. 그렇지만 수학이라는 것이 활용이 되면 정말 파급이 큽니다. 우리가 이 글을 보기 위하여 인터넷을 접속할때부터 이 글을 읽을 때까지 정말 여러 곳에서 수학이 활용되고 있다고 할 수 있습니다. 아울러 수학은 오랜 시간이 지나 활용되는 사례도 여럿 있구요. 그러다보니 수학자들에게 이런 질문을 하면 100년이 지나면 사용될지도 모른다 같은 식의 모호한 답을 하기 마련인데 기자분들은 이런 답을 들으면 답답하실 거에요. 수학자들은 틀린 답은 안 하도록 직업적 훈련을 받는 사람들이라 아닌 걸 맞다라고 하진 못하거든요.
List of YouTube Channels for research talks on discrete mathematics
Due to the COVID-19 pandemic, many seminars are now held online. Many of them made a YouTube channel to post their videos. But it is very difficult to search for such videos. In this post, I’d like to share a few of them. Please suggest more in the comment. IBS Discrete Mathematics Group Department of Combinatorics and Optimization at University of Waterloo Oxford Discrete Mathematics and Probability Seminar, Oxford University Laboratory of Combinatorial and Geometric Structures, MIPT Discrete Math Seminar at the University of South Carolina Discrete Math Seminar at the Simon Fraser University ACO Program, Georgia Tech SCMS Combinatorics Seminar, Shanghai Center for Mathematical Sciences, Fudan University (on Bilibili.com) PIMS-UVic Discrete Math Seminar (on mathtube.org) Graphs and Optimization seminar, LaBRI (on its own server) Here’s a list of YouTube channels for online seminars.
A solution to the Particles Problem
Prof. Yuval Peres posted the following very interesting problem on his blog. Suppose there are n particles in the unit square. Initially one particle is awake and all others are sleeping. Each awake particle moves in the unit square at speed 1 in a direction you prescribe and wakes up any sleeping particle it encounters. The particles that are awake move simultaneously. Question: Show that you can wake up all the particles by time 10.
수학동아 “따끈따끈한 수학” 연재 (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.
2017년 카오스강연 “미래의 수학자”
KAOS재단에서 운영하는 대중강연 시리즈인 2017 가을 카오스 강연에 참여할 기회가 있었습니다. 이번 2017년 가을의 주제는 미래과학이라서 “미래의 수학자”라는 제목으로 컴퓨터를 사용한 증명 등 앞으로 수학자들의 일상이 어떻게 될지 생각해보면서 강연을 하였습니다. 강연은 2017년 10월 18일에 있었고, 강연비디오가 youtube에 올라와 있습니다. 강연 영상 재생목록
KAIST에서 2017년 가을에 열리는 이산수학/그래프이론 관련 교과목
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의 그래프 마이너 정리 교재: 매년 R. Diestel 교수의 그래프 이론 GTM 책(http://diestel-graph-theory.com)을 교재로 지정하였으나, 올해는 참고도서로만 지정하였습니다. 책 값이 비싸다는 불평들이 있었고, 사실 수업 내용은 평행우주를 달린다는 평도 있었기에… KAIST 교내에서는 책을 온라인으로 볼 수 있습니다. https://doi.org/10.1007/978-3-662-53622-3 Syllabus MAS583C Topics in Analytic Combinatorics (해석조합론), 화목 10:30-11:45, 김동수 교수님 예전에 1학점 특강으로 잠깐 개설된 적이 있던 주제인데 이번에 처음 3학점 특강 과목으로 개설되었습니다. 학부 고년차나 대학원생의 경우 학부때 배우는 복소 과목이 어떻게 조합론에서 쓰일 수 있나 알아보는 기회가 되겠습니다. 특히 어떤 조합적 대상의 수를 asymptotic하게 새는 도구들을 배우게 된다고 보시면 됩니다. 과목을 마치게 되면 생성함수를 잘 다루게 될 것이고, 생성함수를 복소평면 위에서의 함수로 이해한 다음 singular point들을 찾아서 분석하는 기술을 습득하게 될 겁니다. 그 외에 다른 재미있는 주제가 있을 것 같습니다. 교재: 참고도서만 지정되어 있습니다. Analytic Combinatorics, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2009 810페이지짜리 두꺼운 책입니다. 저는 16만원 넘게 주고 산 책인데, 이 책의 홈페이지에서 PDF로 다운받을 수 있습니다. Analytic Combinatorics in Several Variables, Robin Pemantle and Mark C. Wilson, 2013 역시 책의 홈페이지에서 draft 버젼의 PDF를 살펴볼 수 있습니다. 아래는 그 외에 눈 여겨 본 과목들입니다. 일부 내용은 실라버스에서 발췌한 것입니다.
수학동아 "따끈따끈한 수학" 연재 (2017년)
2016년부터 수학동아에 “따끈따끈한 수학”이라는 코너를 연재하고 있습니다. 소개된 논문을 정리한 글이 너무 길어져서 연도별로 분리하기로 하였습니다. 2016년 따끈따끈한 수학 내용 보기 2017년 1월호: 에르되시-버어 추측을 해결하다! 이중범 박사가 40년 이상 묵은 Burr와 Erdos의 1973년 추측을 해결하였고 그 논문이 Annals of Mathematics에 게재승인되었다는 소식을 전했습니다. 논문 Choongbum Lee. Ramsey numbers of degenerate graphs. Annals of Mathematics. 185(2017) pp. 791-829. doi:10.4007/annals.2017.185.3.2 2017년 2월호: 자연수 색칠하기 문제 자연수 전체를 유한개의 색으로 색칠했을 때, x, x+y, xy가 같은 색이 되는 x, y가 항상 있다는 Joel Moreira 박사의 결과를 소개했습니다. 논문 Joel Moreira, Monochromatic sums and products in ℕ. Annals of Mathematics 185 (2017), pp. 1069-1090. doi:10.4007/annals.2017.185.3.10 2017년 3월호: 스타인버그의 추측 길이가 4나 5인 회로가 없는 평면 그래프는 3개 색으로 꼭짓점을 칠할 수 있는지에 관한 스타인버그(Steinberg)의 추측의 반례가 발견되었다는 소식을 전하였습니다. 논문 V. Cohen-Addad, M. Hebdige, D. Král’, Z. Li, E. Salgado, Steinberg’s conjecture is false, J. Combin. Theory Ser. B. 122 (2017) 452–456. doi:10.1016/j.jctb.2016.07.006. 2017년 4월호: Frankl의 Union-Closed Set 추측! Random bipartite graph에서는 P. Frankl의 union-closed sets conjecture가 대부분 성립한다는 H. Bruhn과 O. Schaudt의 논문을 소개하였습니다. 논문 H. Bruhn, O. Schaudt, The union-closed sets conjecture almost holds for almost all random bipartite graphs, European J. Combin. 59 (2017) 129–149. doi:10.1016/j.ejc.2016.06.006 2017년 5월호: 해바라기 추측 Slice rank 방법을 이용하여 Erdos와 Szemeredi의 sunflower 추측을 E. Naslund와 W. Sawin이 간단한 증명으로 해결한 것을 소개하였습니다. 논문 E. Naslund, W.F. Sawin, Upper bounds for sunflower-free sets, arXiv:1606.09575v1, 2016. E. Naslund, W. F. Sawin, Upper bounds for sunflower-free sets, Forum Math, Sigma, 5(2017), e15, doi:10.1017/fms.2017.12 2017년 6월호: 사잇각이 같은 직선들 n차원 공간에서 원점을 지나면서 서로 사잇각이 항상 일정하게 직선을 모을 때 최대 갯수가 어떻게 되는지에 관한 최신 결과를 소개하였습니다. 논문 I. Balla, F. Dräxler, P. Keevash, B. Sudakov, Equiangular Lines and Spherical Codes in Euclidean Space, arXiv:1606.06620, 2016. 2017년 7월호: Caccetta-Häggkvist 추측 Caccetta-Häggkvist 추측을 소개하고 Flag Algebra를 이용한 Jan Hladký, Daniel Král’, Sergey Norin의 논문 내용을 소개했습니다. 논문 J. Hladký, D. Král’, S. Norin, Counting flags in triangle-free digraphs, Combinatorica. 37 (2017) 49–76. doi:10.1007/s00493-015-2662-5. 2017년 8월호: 커크맨의 여학생 문제 조합적 디자인 문제에 최근 좋은 결과들이 나오고 있습니다. 몇 년 전 Peter Keevash 교수가 150년 전의 문제인 Generalized Steiner System에 관한 문제를 해결한 후, 이를 확장하는 연구 결과가 최근 S. Glock, D. Kühn, A. Lo, D. Osthus에 의해 증명되었습니다. 논문 P. Keevash, The existence of designs, arXiv:1401.3665, 2017. S. Glock, D. Kühn, A. Lo, D. Osthus, Hypergraph F-designs for arbitrary F, arXiv:1706.01800, 2017 참고 Peter Keevash 교수 결과에 대한 참고글, blog.combinatorics.kr, 2014. 2017년 9월호: 다울링-윌슨 추측 IAS의 허준이 박사와 위스콘신-매디슨대학교 Botong Wang 교수가 조합론 분야 40년 묵은 추측인 Dowling-Wilson 추측을 해결하였다는 소식을 전했습니다. 논문 J. Huh, B. Wang, Enumeration of points, lines, planes, etc, arXiv:1609.05484, 2017 2017년 10월호: 베크너의 문제 각 꼭지점의 차수가 3인 평면 그래프의 제곱을 7색으로 칠할 수 있다는 덴마크 DTU의 Carsten Thomassen 교수의 결과를 다루었습니다. 즉, 어떤 평면 그래프에서 각 꼭짓점에 이웃한 다른 꼭짓점의 수가 정확히 3이면, 거리가 2 이하인 두 점은 서로 다른 색이 되도록 7개 색 이하만 사용하여 칠할 수 있다는 정리입니다. 논문 C. Thomassen, The square of a planar cubic graph is 7-colorable, J. Combin. Theory Set. B, 128(2018), 192-218. doi:10.1016/j.jctb.2017.08.010 2017년 11월호: 외판원 문제 Asymmetric TSP 문제의 constant factor approximation algorithm이 처음으로 나왔다는 소식을 전했습니다. 풀어쓰자면, n개 도시를 모두 각각 한 번씩 들르고 출발점으로 최소 비용으로 돌아와야 하는 외판원 문제(Traveling Salesman Problem)의 최적값의 5500배 이내의 비용임을 보장해주는 경로를 찾아주는 효율적인 알고리듬이 나왔다는 소식입니다. 논문 O. Svensson, J. Tarnawski, and L. Végh, A constant-factor approximation algorithm for the asymmetric traveling salesman problem, arXiv:1708.04215, 2017 2017년 12월호: 볼록오각형 테셀레이션 문제 볼록오각형 하나와 합동인 도형만 가지고 평면 전체를 빈틈없이 가득 채우는 방법은 총 15가지 종류 뿐이라는 것이 최근 Michaël Rao 박사에 의해 컴퓨터를 사용하여 증명되었습니다. 논문 M. Rao, Exhaustive search of convex pentagons which tile the plane, arXiv:1708.00274, 2017. 참고 M. Rice, https://sites.google.com/site/intriguingtessellations/home N. Wolchover, Marjorie Rice’s secret pentagons, Quanta Magazine, July 11, 2017. N. Wolchover, Pentagon tiling proof solves century-old math problem, Quanta Magazine, July 11, 2017.
Theorems covered in MAS575 Combinatorics Spring 2017
This post will give an incomplete list of theorems covered in MAS575 Combinatorics Fall 2017. This post will be continuously updated throughout this semester. (Last update: April 5, 2017.) 2017년 봄학기 MAS575 조합론 과목에서 다룬 정리들을 정리하였습니다. 빠진 것도 있습니다. 강의가 진행되면서 내용을 업데이트 하겠습니다. Graham and Pollak (1971). Proof by Tverberg (1982) The edge set E(Kn)E(K_n) of the complete graph cannot be partitioned into less than n−1n-1 copies of the edge sets of complete bipartite subgraphs. Lindström and Smet (1970). Let A1,A2,…,An+1⊆[n]A_1,A_2,\ldots,A_{n+1}\subseteq [n]. Then there exist subsets II and JJ of [n+1][n+1] such that I∪J≠∅,I∩J=∅, and ⋃i∈IAi=⋃j∈JAj. I\cup J\neq \emptyset, I\cap J=\emptyset, \text{ and }\bigcup_{i\in I}A_i =\bigcup_{j\in J} A_j. Lindström (1993) Let A1,A2,…,An+2⊆[n]A_1,A_2,\ldots,A_{n+2}\subseteq [n]. Then there exist subsets II and JJ of [n+2][n+2] such that I∪J≠∅I\cup J\neq \emptyset, I∩J=∅I\cap J=\emptyset, and ⋃i∈IAi=⋃j∈JAj and ⋂i∈IAi=⋂j∈JAj.\bigcup_{i\in I} A_i=\bigcup_{j\in J}A_j\text{ and }\bigcap_{i\in I}A_i=\bigcap_{j\in J}A_j. Larman, Rogers, and Seidel (1977) [New in 2017] Every two-distance set in Rn\mathbb R^n has at most (n+22)+n+1\binom{n+2}{2}+n+1 points. (A set of points is a two-distance set if the set of distances between distinct points has at most two values.) Blokhuis (1984) [New in 2017] Every two-distance set in Rn\mathbb R^n has at most (n+22)\binom{n+2}{2} points. Erdős (1963) Let C1,C2,…,CmC_1,C_2,\ldots,C_m be the list of clubs and each club has at least kk members. If m<2k−1m< 2^{k-1}, then such an assignment of students into two lecture halls is always possible. Erdős, Ko, and Rado (1961). Proof by Katona (1972) Let k≤n/2k\le n/2. Let F\mathcal F be a kk-uniform intersecting family of subsets of an nn-set. Then ∣F∣≤(n−1k−1).\lvert \mathcal F\rvert\le\binom{n-1}{k-1}. Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948) Let kk be a positive integer. Let F\mathcal F be a family on an nn-set SS such that ∣X∩Y∣=k\lvert X\cap Y\rvert=k whenever X,Y∈FX,Y\in \mathcal F and X≠YX\neq Y. Then ∣F∣≤n\lvert \mathcal F\rvert\le n. Corollary due to de Brujin and Erdős (1948): Suppose that nn points are given on the plane so that not all are on one line. Then there are at least nn distinct lines through at least two of the nn points. Frankl and Wilson (1981). Proof by Babai (1988). If a family F\mathcal F of subsets of [n][n] is LL-intersecting and ∣L∣=s\lvert L\rvert=s, then ∣F∣≤∑i=0s(ni).\lvert \mathcal F\rvert\le \sum_{i=0}^s \binom{n}{i}. Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991). If a family F\mathcal F of subsets of [n][n] is uniform LL-intersecting and ∣L∣=s\lvert L\rvert=s, then ∣F∣≤(ns).\lvert \mathcal F\rvert\le \binom{n}{s}. (A family of sets is \emph{uniform} if all members have the same size.) Deza, Frankl, and Singhi (1983) Let pp be a prime. Let L⊆{0,1,2,…,p−1}L\subseteq\{0,1,2,\ldots,p-1\} and ∣L∣=s\lvert L\rvert=s.If (i) ∣A∣∉L+pZ\lvert A\rvert\notin L+p\mathbb Z for all A∈FA\in \mathcal F, (ii) ∣A∩B∣∈L+pZ\lvert A\cap B\rvert\in L+p\mathbb Z for all A,B∈FA,B\in \mathcal F, A≠BA\neq B, then ∣F∣≤∑i=0s(ni).\lvert \mathcal F\rvert\le \sum_{i=0}^s \binom{n}{i}. Alon, Babai, and Suzuki (1991) Let pp be a prime. Let kk be an integer. Let L⊆{0,1,2,…,p−1}L\subseteq \{0,1,2,\ldots,p-1\} and ∣L∣=s\lvert L\rvert=s. Assume s+k≤ns+k\le n. If (i) ∣A∣≡k∉L+pZ\lvert A\rvert\equiv k \notin L+p\mathbb Z for all A∈FA\in \mathcal F, (ii) ∣A∩B∣∈L+pZ\lvert A\cap B\rvert\in L+p\mathbb Z for all A,B∈FA,B\in \mathcal F, A≠BA\neq B, then ∣F∣≤(ns).\lvert \mathcal F\rvert\le \binom{n}{s}. Grolmusz and Sudakov (2002) [New in 2017] Let pp be a prime. Let L⊆{0,1,…,p−1}L\subseteq\{0,1,\ldots,p-1\} with ∣L∣=s\lvert L\rvert=s and k≥2k\ge 2. Let F\mathcal F be a family of subsets of [n][n] such that (i) ∣A∣∉L+pZ\lvert A\rvert\notin L+p\mathbb Z for all A∈FA\in \mathcal F and (ii) ∣A1∩A2∩⋯∩Ak∣∈L+pZ\lvert A_1\cap A_2\cap \cdots \cap A_k\rvert\in L+p\mathbb Z for every collection of kk distinct members A1,A2,…,AkA_1,A_2,\ldots,A_k of F\mathcal F. Then ∣F∣≤(k−1)∑i=0s(ni).\lvert \mathcal F\rvert\le (k-1)\sum_{i=0}^s \binom{n}{i}. Grolmusz and Sudakov (2002) [New in 2017] Let ∣L∣=s\lvert L\rvert=s and k≥2k\ge 2. Let F\mathcal F be a family of subsets of [n][n] such that ∣A1∩A2∩⋯∩Ak∣∈L\lvert A_1\cap A_2\cap \cdots \cap A_k\rvert\in L for every collection of kk distinct members A1,A2,…,AkA_1,A_2,\ldots,A_k of F\mathcal F. Then ∣F∣≤(k−1)∑i=0s(ni).\lvert \mathcal F\rvert\le (k-1)\sum_{i=0}^s \binom{n}{i}. Sperner (1928) If F\mathcal F is an antichain of subsets of an nn-set, then ∣F∣≤(n⌊n/2⌋). \lvert \mathcal F\rvert\le \binom{n}{\lfloor n/2\rfloor}. Lubell (1966), Yamamoto (1954), Meschalkin (1963) If F\mathcal F is an antichain of subsets of an nn-element set, then ∑A∈F1(n∣A∣)≤1. \sum_{A\in \mathcal F} \frac1{\binom{n}{\lvert A\rvert}}\le 1. Bollobás (1965) Let A1A_1, A2A_2, …\ldots, AmA_m, B1B_1, B2B_2, …\ldots, BmB_m be subsets on an nn-set such that (a) Ai∩Bi=∅A_i\cap B_i=\emptyset for all i∈[m]i\in[m], (b) Ai∩Bj≠∅A_i\cap B_j\neq\emptyset for all i≠ji\neq j. Then∑i=1m1(∣Ai∣+∣Bi∣∣Ai∣)≤1.\sum_{i=1}^m \frac1{\binom{\lvert A_i\rvert+\lvert B_i\rvert}{\lvert A_i\rvert}} \le 1. Bollobás (1965), extending Erdős, Hajnal, and Moon (1964) If each family of at most (r+sr)\binom{r+s}{r} edges of an rr-uniform hypergraph can be covered by ss vertices, then all edges can also be covered by ss vertices. Lovász (1977) Let A1A_1, A2A_2, …\ldots, AmA_m, B1B_1, B2B_2, …\ldots, BmB_m be subsets such that ∣Ai∣=r\lvert A_i\rvert=r and ∣Bi∣=s\lvert B_i\rvert=s for all ii and (a) Ai∩Bi=∅A_i\cap B_i=\emptyset for all i∈[m]i\in[m], (b) Ai∩Bj≠∅A_i\cap B_j\neq\emptyset for all i<ji<j. Then m≤(r+sr)m\le \binom{r+s}{r}. Let WW be a vector space over a field F\mathbb F. Let U1,U2,…,Um,V1,V2,…,VmU_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m be subspaces of WW such that dim(Ui)=r\dim(U_i)=r and dim(Vi)=s\dim(V_i)=s for each i=1,2,…,mi=1,2,\ldots,m and (a) Ui∩Vi={0}U_i\cap V_i=\{0\} for i=1,2,…,mi=1,2,\ldots,m; (b) Ui∩Vj≠{0}U_i\cap V_j\neq\{0\} for 1≤i<j≤m1\le i<j\le m. Then m≤(r+sr)m\le \binom{r+s}{r}. Füredi (1984) Let U1,U2,…,Um,V1,V2,…,VmU_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m be subspaces of a vector space WW over a field F\mathbb F. If dim(Ui)=r\dim(U_i)=r, dim(Vi)=s\dim(V_i)=s for all i∈{1,2,…,m}i\in\{1,2,\ldots,m\} and for some t≥0t\ge 0, (a) dim(Ui∩Vi)≤t\dim(U_i\cap V_i)\le t for all i∈{1,2,…,m}i\in\{1,2,\ldots,m\}, (b) dim(Ui∩Vj)>t\dim(U_i\cap V_j)>t for all 1≤i<j≤m1\le i<j\le m, then m≤(r+s−2tr−t)m\le \binom{r+s-2t}{r-t}. Frankl and Wilson (1981) The chromatic number of the unit distance graph of Rn\mathbb R^n is larger than 1.2n1.2^n for sufficiently large nn. Kahn and Kalai (1993) (Borsuk’s conjecture is false) Let f(d)f(d) be the minimum number such that every set of diameter 11 in Rd\mathbb R^d can be partitioned into f(d)f(d) sets of smaller diameter. Then f(d)>(1.2)df(d)> (1.2)^{\sqrt d} for large dd. Mehlhorn and Schmidt (1982) [New in 2017] For a matrix C, 2κ(C)≥rank(C)2^{\kappa(C)}\ge \operatorname{rank}(C). (Let κ(C)\kappa(C) be the minimum number of rounds in order to partition CC into almost homogeneous matrices, if in each round we can split each of the current submatrices into two either vertically or horizontally. This is a parameter related to the communication complexity.) Lovász and Saks (1993) κ(C)≤rk(C)\kappa(C)\le \operatorname{rk}(C). ? There exists a randomized protocol to decide the equality of two strings of length nn using O(logn)O(\log n) bits. The probablity of outputting an incorrect answer is less than 1/n1/n. Dvir (2009) [New in 2017] Let f∈F[x1,…,xn]f\in \mathbb F[x_1,\ldots,x_n] be a polynomial of degree at most q−1q-1 over a finite field F\mathbb F with q=∣F∣q=\lvert F\rvert elements. Let KK be a Kakeya set. If f(x)=0f(x)=0 for all x∈Kx\in K, then ff is a zero polynomial. If K⊆FnK\subseteq\mathbb F^n is a Kakeya set, then ∣K∣≥(∣F∣+n−1n)≥∣F∣nn .\lvert K\rvert\ge \binom{\lvert \mathbb F\rvert+n-1}{n} \ge \frac{\lvert F\rvert^n}{n\!}. Ellenberg and Gijswijt (2017) [New in 2017] If AA is a subset of F3n\mathbb F_3^n with no three-term arithmetic progression, then ∣A∣≤3N\lvert A\rvert\le 3N where N=∑a,b,c≥0;a+b+c=n;b+2c≤2n/3n a b c .N=\sum_{a,b,c\ge 0; a+b+c=n; b+2c\le 2n/3} \frac{n\!}{a\! b\! c\!}.Furthermore 3N≤o(2.756n)3N\le o(2.756^n). Tao (2016) [New in 2017] Let k≥2k\ge 2 and let AA be a finite set and F\mathbb F be a field. Let f:Ak→Ff:A^k\to \mathbb F be a function such that if f(x1,x2,…,xk)≠0f(x_1,x_2,\ldots,x_k)\neq 0, then x1=x2=⋯=xkx_1=x_2=\cdots=x_k. Then the slice rank of ff is equal to ∣{x:f(x,x,…,x)≠0}∣\lvert\{x: f(x,x,\ldots,x)\neq 0\}\rvert. Erdős and Rado (1960) [New in 2017] There is a function f(k,r)f(k,r) on positive integers kk and rr such that every family of kk-sets with more than f(k,r)f(k,r) members contains a sunflower of size rr. Naslund and Sawin (2016) [New in 2017] Let F\mathcal F be a family of subsets of [n][n] having no sunflower of size 33. Then ∣F∣≤3(n+1)∑k≤n/3(nk).\lvert \mathcal F\rvert\le 3(n+1)\sum_{k\le n/3}\binom{n}{k}. Alon and Tarsi (1992) Let F\mathbb F be a field and let f∈F[x1,x2,…,xn]f\in \mathbb F[x_1,x_2,\ldots,x_n]. Suppose that deg(f)=d=∑i=1ndi\deg(f)=d=\sum_{i=1}^n d_i and the coefficient of ∏i=1nxidi\prod_{i=1}^n x_i^{d_i} is nonzero. Let L1,L2,…,LnL_1,L_2,\ldots,L_n be subsets of F\mathbb F such that ∣Li∣>di\lvert L_i\rvert>d_i. Then there exist a1∈L1a_1\in L_1, a2∈L2a_2\in L_2, …\ldots, an∈Lna_n\in L_n such that f(a1,a2,…,an)≠0. f(a_1,a_2,\ldots,a_n)\neq 0. Cauchy (1813), Davenport (1935) Let pp be a prime and let A,BA,B be two nonempty subsets of Zp\mathbb{Z}_p. Then ∣A+B∣≥min(p,∣A∣+∣B∣−1).\lvert A+B\rvert\ge \min(p,\lvert A\rvert+\lvert B\rvert-1). Dias da Silva and Hamidoune (1994). A proof by Alon, Nathanson, and Ruzsa (1995). Conjecture of Erdős and Heilbronn (1964). Let pp be a prime and AA be a nonempty subset of Zp\mathbb{Z}_p. Then ∣{a+a′:a,a′∈A,a≠a′}∣≥min(p,2∣A∣−3). \lvert\{ a+a': a,a'\in A, a\neq a'\}\rvert \ge \min(p,2\lvert A\rvert-3). Alon (2000) [New in 2017] Let pp be an odd prime. For k<pk< p and every integers a1,a2,…,ak,b1,b2,…,bka_1,a_2,\ldots,a_k,b_1,b_2,\ldots,b_k, if b1,b2,…,bkb_1,b_2,\ldots,b_k are distinct, then there exists a permutation π\pi of {1,2,…,k}\{1,2,\ldots,k\} such that the sums ai+bπ(i)a_i+b_{\pi(i)} are distinct. Alon? [New in 2017] If AA is an n×nn\times n matrix over a field F\mathbb F, per(A)≠0\operatorname{per}(A)\neq 0 and b∈Fnb\in \mathbb F^n, then for every family of sets L1L_1, L2L_2, …\ldots, LnL_n of size 22 each, there is a vector x∈L1×L2×⋯×Lnx\in L_1\times L_2\times \cdots\times L_n such that (Ax)i≠bi(Ax)_i\neq b_i for all ii. Alon? [New in 2017] Let GG be a bipartite graph with the bipartition AA, BB with ∣A∣=∣B∣=n\lvert A\rvert=\lvert B\rvert=n. Let B={b1,b2,…,bn}B=\{b_1,b_2,\ldots,b_n\}. If GG has at least one perfect matching, then for every integer d1,d2,…,dnd_1,d_2,\ldots,d_n, there exists a subset XX of AA such that for each ii, the number of neighbors of bib_i in XX is not did_i. Erdős, Ginzburg, and Ziv (1961) [New in 2017] Let pp be a prime. Every sequence a1,a2,…,a2p−1a_1,a_2,\ldots,a_{2p-1} of integers contains a subsequence ai1a_{i_1}, ai2a_{i_2}, …\ldots, aipa_{i_p} such that ai1+ai2+⋯aip≡0(modp)a_{i_1}+a_{i_2}+\cdots a_{i_p}\equiv 0\pmod p. Alon, Friedland, and Kalai (1984) [New in 2017] Every (multi)graph with average degree >4>4 and maximum degree ≤5\le 5 contains a 33-regular subgraph. ? Let GG be an undirected graph. Let d(G)=maxH⊆G∣E(H)∣∣V(H)∣d(G)=\max_{H\subseteq G}\frac{\lvert E(H)\rvert}{\lvert V(H)\rvert}. Then there is an orientation of GG such that the outdegree of each vertex is at most ⌈d(G)⌉\lceil d(G)\rceil. Alon and Tarsi (1992) A simple planar bipartite graph is 33-choosable.
수학동아 연재 (2016년)
2016년부터 수학동아에 “따끈따끈한 수학”이라는 코너를 연재하기로 하였습니다. 목표는 이산수학 분야의 따끈따끈한 논문 소식들을 중학생 수준에서도 읽을만하게 적는 것입니다. 사실 그게 말처럼 쉬운 것은 아니지만요. 현재까지 실린 글과 앞으로 실릴 글을 예고하고 관련 논문을 정리했습니다. 혹시 글감으로 추천할 논문이 있으면 연락주셔도 좋습니다. 글이 길어져서 2017년 내용은 따로 분리하였습니다. 2017년 따끈따끈한 수학 내용 보기 2016년 1월호: 그래프 동형 문제 (Graph isomorphism problem) 작년 가을에 떠들석했던 그래프 동형 문제를 quasi-polynomial 시간에 풀 수 있다는 Babai 교수 결과에 대해 정리했습니다. (사실 기사 제목에 “P일까, NP일까?”로 나갔는데 잘못된 제목입니다. 정확하게는 “P일까 아닐까?” 정도가 좋겠죠. NP 대신 NP-hard라고 하든지 했어야 하는데 제목이 들어간 편집본을 꼼꼼히 검토하지 못했네요.) 이 글은 네이버캐스트에도 소개되었습니다. 논문: L. Babai, Graph Isomorphism in Quasipolynomial Time, arXiv:1512.03547, 2015. 2016년 2월호: Gyárfás 추측
그래프 이론 용어 우리말 번역
그래프 이론에서 널리 사용되는 용어들을 우리 말로 번역하는 적절한 표준이 아직 없습니다. 10여년 전에 성균관대 이상구 교수님께서 제작한 “그래프이론 용어사전” 웹사이트가 있습니다만, matching이나 k-connected같은 현대적이고 널리 (제) 연구에 쓰이는 그래프이론 용어가 나오지 않습니다. 오죽하면, 2000년에 고 이창우 교수님이 Introduction to Combinatorics라는 책을 쓰셨는데, 서문을 읽어보면 한국어 용어를 몰라 영어를 잘 못하는데도 불구하고 영어로 책을 쓰게 되었다고 적혀있습니다. (저도 어쩌다보니 보게 된 책일 뿐, 그래프이론 공부를 위해서는 딱히 추천하는 책은 아닙니다.)
KMO 여름학교/겨울학교 강의노트
2008년부터 대한수학회 주최 한국수학올림피아드(KMO) 여름학교와 겨울학교에서 조합수학 분야 강의를 해왔습니다. 그 중 유인물을 나눠준 적이 몇 번 있는데 그것들을 여기에 공유하고자 합니다. 2008년 제21기 겨울학교 (KAIST, 1월 7일-1월 22일) (유인물 없음) 2008년 제18기 여름학교 유인물 (KAIST, 7월 28일-8월 8일) 비둘기집의 원리와 램지 이론 / 수학적 귀납법 / 그래프이론 2009년 제19기 여름학교 (배재대, 8월 4일-8월 13일) (유인물 없음) 2010년 제23기 겨울학교 (한남대, 1월 6일-1월 21일) (유인물 없음) 2010년 제20기 여름학교 (충남대, 8월 2일-8월 13일) (유인물 없음) 2011년 제24기 겨울학교 (KAIST, 1월 6일-1월 21일) (유인물 없음) 2011년 제21기 여름학교 유인물 (KAIST, 8월 1일-8월 12일) 수학적 귀납법 2012년 제25기 겨울학교 (KAIST, 1월 4일-1월 19일) (유인물 없음) 2012년 제22기 여름학교 유인물 (충남대, 7월 26일-8월 7일) 수학적 귀납법 2013년 제26기 겨울학교 유인물 (KAIST, 1월 8일-1월 21일) partial order, well-quasi-order, Dilworth 정리, antichain 2014년 제23기 여름학교 (KAIST, 7월 23일-8월 1일) (유인물 없음) 2015년 제28기 겨울학교 유인물 (KAIST, 1월 2일-1월 15일) 확률론적 방법론 2015년 제24기 여름학교 유인물 (KAIST, 8월 3일-14일) 수학적 귀납법 2016년 제29기 겨울학교 (KAIST, 1월 6일-19일) (유인물 없음) 2016년 제25기 여름학교 (KAIST, 8월 1일-12일) (유인물 없음) 2017년 제30기 겨울학교 (KAIST, 1월 4일-17일) (유인물 없음) 2017년 제26기 여름학교 (KAIST, 7월 31일-8월 11일) (유인물 없음) 2018년 제31기 겨울학교 (KAIST, 1월 3일-1월 16일) (유인물 없음) 한편 1993년 1월에 있었던 제6기 한국수학올림피아드 겨울학교에 고등학생으로 참가하여 필기했던 노트도 공유합니다. 누락되거나 빠진 페이지가 있을 수 있습니다.