수학동아 연재 (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 추측

  

  • Gyárfás 추측 중에 길이 5이상인 odd cycle이 induced subgraph가 없는 그래프는 ?-bounded라는 것이 최근에 Scott과 Seymour 교수 두 분의 공동연구로 증명된 것을 소개했습니다.
  • 논문: A. Scott, P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes, J. Combin. Theory. Ser. B, in press, 10.1016/j.jctb.2015.10.002
• 2016년 3월호: 홀의 결혼정리를 이산기하 문제로 확장

  

  • 홀의 결혼정리를 KAIST 수리과학과의 Andreas F. Holmsen 교수가 다른 분들과 함께 이산기하 문제로 확장해서 푼 것을 소개했습니다.
  • 논문: A. F. Holmsen, L. Martinez-Sandoval, and L. Montejano. A geometric Hall-type theorem. Proc. Amer. Math. Soc., 144(2):503–511, 2016.
• 2016년 4월호: 광통신망에서 나타나는 라우팅 문제

  

  • 광케이블을 쓰는 SONET 표준의 링 네트웍에서 어느 방향으로 전송할지에 관한 문제인 ring loading problem의 최신 결과를 소개했습니다. 원래 1998년 A. Schrijver, P. Seymour, P. Winkler가 만든 근사 알고리듬과 추측이 있는데 이 것을 개선한 알고리듬을 보이며 그 추측은 반례를 찾아낸 Martin Skutella 교수의 논문을 소개했습니다.
  • 논문: M. Skutella, A note on the ring loading problem, SIAM J. Discrete Math., Vol. 30, No. 1, pp. 327-342.
• 2016년 5월호: 연속한 소수의 끝자리 분포 미스테리

  

  • 최근 발견된 연속한 소수를 n으로 나눈 나머지 수열의 분포가 예측에 비해 매우 치우쳐져 있다는 것을 소개했습니다.
  • 논문: R. J. Lemke Oliver, K. Soundararajan, Unexpected biases in the distribution of consecutive primes, arXiv:1603.03720.
• 2016년 6월호: 8차원과 24차원에서 구 채우기 문제
  • 2016년 3월에 arXiv에 공개된 8차원과 24차원에서 구를 최대로 채우는 밀도가 증명된 논문이 나왔다는 소식을 소개했습니다.
  • 논문:
    • M. Viazovska, The sphere packing problem in dimension 8, arXiv:1603.04246.
    • H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, M. Viazovska, The sphere packing problem in dimension 24, arXiv:1603.06518.
• 2016년 7월호: 볼록다각형 찾기 문제의 행복한 결말

  

  • 2016년 4월에 arXiv에 올라온 Andrew Suk 교수의 Erdos-Szekeres 추측 관련 좋은 결과를 소개하였습니다.
  • 논문
    • A. Suk, On the Erdos-Szekeres convex polygon problem, arXiv:1604.08657.
• 2016년 8월호: ‘세트’가 항상 있게 하려면 카드가 몇 장이나 있어야 하지?

  

  
  

   

  • 2016년 5월에 있었던 (Z/3Z)ⁿ에서 길이 3인 등차수열이 없는 부분집합 중 가장 큰 것의 크기가 2.756ⁿ이하라는 Ellenberg와 Gijswijt의 논문을 소개하였습니다. 증명은 선형대수를 아는 학부생이라면 충분히 이해할 수 있습니다.
  • 논문
    • J. S. Ellenberg and D. Gijswijt. On large subsets of ?_qⁿ with no three-term arithmetic progression, arXiv:1605.09223.
    • 참고 블로그글: Ellenberg 블로그, Tim Gowers 블로그, Terrence Tao 블로그
• 2016년 9월호: 케이크 공평하게 나누기

  

  • 2016년 4월에 arXiv에 올라온, n명이 케이크를 envy-free하게 나누면서도 나누는 칼질 횟수가 n에 관한 어떤 함수값 이하게 되는 최초의 방법을 소개했습니다. 1990년대 개발된 기존 방법은 n=4인 경우에도 칼질 횟수가 유한이긴 해도 매우 커질 수 있었습니다.
  • 논문
    • H. Aziz and S. Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. arXiv:1604.03655, 2016.
• 2016년 10월호: 평면 위의 점 n개로 만들어내는 거리값은 적어도 몇 개 이상일까?

  

  • 2015년 Annals of Mathematics에 실린 Erdős의 distinct distances 문제에 관한 Larry Guth와 Net Katz의 논문을 소개했습니다. 평면에 n개의 점이 있을때 그 점 중 두 점씩 뽑아서 만들수 있는 서로 다른 거리의 최소값은 얼마인가에 관한 문제입니다.
  • 논문
    • Guth, L., & Katz, N. H. (2015). On the Erdős distinct distances problem in the plane. Annals of Mathematics. Second Series, 181(1), 155–190. doi:10.4007/annals.2015.181.1.2
• 2016년 11월호: 외로운 주자 추측 (Lonely Runner Conjecture)

  

  • 최근에 Lonely Runner Conjecture에 관한 틀린 증명이 arXiv에 올라와서 사람들이 떠들썩한 적이 있었습니다. 비록 금방 틀린 것이 알려지게 되었고 논문은 철회되었습니다. 해당 추측을 소개합니다.
  • 논문
    • Barajas, J., & Serra, O. (2008). The lonely runner with seven runners. Electronic Journal of Combinatorics, 15(1), Research paper 48–18.
    • Czerwiński, S. (2012). Random runners are very lonely. Journal of Combinatorial Theory. Series A, 119(6), 1194–1199. doi:10.1016/j.jcta.2012.02.002
    • Bohman, T., Holzman, R., & Kleitman, D. (2001). Six lonely runners. Electronic Journal of Combinatorics, 8(2), Research Paper 3–49 pp.
    • Cusick, T. W., & Pomerance, C. (1984). View-obstruction problems. III. Journal of Number Theory, 19(2), 131–139. doi:10.1016/0022-314X(84)90097-0
    • Renault, J. (2004). View-obstruction: a shorter proof for 6 lonely runners. Discrete Mathematics, 287(1-3), 93–101.
    • 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
• 2016년 12월호: 해밀턴 회로가 있을까? 가운뎃층 문제(middle levels conjecture)

  

  • {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.