[ new blog ]

new blog

https://jihyo-jeon.github.io/

A Puzzle of Clever Connections Nears a Happy End

Happy Ending Problem은 5개의 주어진 점이 있고 어떤 세 점도 한 줄 위에 있지 않다면 볼록 다각형인 사각형을 만들 수 있다는 것이다. 이것은 사실이다. 하지만 볼록다각형인 오각형, 육각형 혹은 11각형을 만들어야 한다면 얼마나 많은 점이 필요할까?

세 명의 젊은 수학자는 3,4,5각형일 때의 경우를 풀었다. 5개의 점이 4각형을 만들고, 9개의 점이 5각형을 만들 수 있다. 그들은 2^(n–2) + 1개의 점이 볼록 다각형 n각형을 만들 수 있다고 생각했다. 그리고 이것을 증명하는데에 $500를 걸었다.

몇십년이 흐르는 동안, 17개의 점이 볼록다각형 6각형을 보장한다는 것 외에 진전이 없었다. 그리고 이 문제가 나타난지 80여년이 지나서야 드디어 2^(n–2) + 1개의 점이 볼록 다각형 n각형을 만들 수 있다는 것이 증명되었다.

Split Shapes

이 문제는 볼록다각형을 만드는 변들을 찾는 것으로 볼 수 있다. 1935년의 논문에서 그들은 u shape모양을 Cup라고 하였고, n shape 모양을 Cap이라고 하였다. 그래서 볼록다각형을 만들 때는 cup 위에 cap을 붙이면 된다. 이를 이용하면, 볼록다각형을 확장할 때 어떤 것을 붙일지를 통해 쉽게 생각할 수 있다.

그들은 이 논문에서 컵-캡 정리를 증명했다. 컵-캡 정리는 점이 적어도 몇 개 필요한지 컵 또는 캡의 사이즈를 정하기 전에 알려준다. 게다가 Happy Ending Problem의 상한을 정할 수 있다. 그들은 이 정리를 통해 4^n개의 점이 n sided convex polygon을 만든다는 것을 알았다. 하지만 이 상한은 여전히 크다.

Sorting Spikes

Andrew Suk은 Ramsey Theory에 집중했다. 문제에 Ramsey Theory를 적용하면, 잘 정리된 볼록다각형의 point set을 얻을 수 있다.

Suk의 작업은 Erdős and Szekeres’ conjecture 가 거의 맞다는 것을 보여줬다. 기존의 상한은 4^n이었던데 반해, Suk은 상한을 2^(n+6n^(⅔)log n) 까지 제한하는데 성공했다.

To Divide the Rent, Start With a Triangle

작년에 나는 두명의 친구와 함께 맨해튼에 있는 방 3개 짜리 아파트로 이사했다. 월세도 합리적이었고, 위치가 특히 편했다. 집을 구하는 것도 힘들었지만 우리는 또 다른 문제에 직면했다. 바로 누가 어떤 방을 쓸 것인가에 관한 것이었다.

각 방은 각각 다른 크기를 가지고 있었다. 두 방은 거리를 향한 북향이고 가장 작은 방은 뒷골목을 향했다. 가장 큰 방은 두 개의 창문이 있고, 두번째로 큰 방은 화재대피로와 연결된다.

사람들은 주거비를 아끼기 위해 전혀 알지도 못하는 사람들과 살기도 한다. 월세를 똑같이 나눌지, 방 크기에 따라 나눌지 아니면 수입에 따라 나눌지도 정해야 한다.

그래서 학계에서는 공평하게 나누는 법을 연구했다. 연구자들은 어떤 방법에도 만족하지 못했다.

문제는 개개인이 각 방을 다르게 평가한다는 것이다. 나는 자연광을 굉장히 고려하지만 다른 사람들은 그렇지 않았다. 옷장을 갖는 것보다 가치가 있는 일인지? 어떤 이는 방 모양을, 다른 이는 화장실 유무를 더 크게 고려했다.

방의 크기나 각 개인의 선호도를 전부 고려하지 못하다 보니 뾰족한 수가 없는 협상은 갈등과 서운함만을 불러올 뿐이었다.

나는 우리의 월세를 나누는 더 좋은 방법을 찾기 위해 고민했다. 그렇게 Harvey Mudd 대학의 수학 교수인 Francis Su의 논문까지 보게 되었다. 수학적으로 어떻게 분할할 것인가를 고민한 Sperner’s lemma에 관한 논문이었다.

Su 박사는 1999년 논문 "Rental Harmony : Sperner’s Lemma in Fair Division."(조화로운 월세 내기 : Sperner’s lemma를 적용한 공평한 나누기)에서 Sperner’s lemma와 월세 나누기의 연관성을 처음으로 제시했다. 그는 하버드에서 박사학위를 마칠 때 쯤 이 문제를 연구하기 시작했다. 그의 친구가 나와 똑같은 곤경에 처해 있었고, 그에게 조언을 구했기 때문이다.

Su 박사는 어쩌면 이 문제가 자신이 들어본 다른 문제와 연관이 있을 수도 있을 것이라는 생각을 하게 된다.

The prize in economic sciences 2012

The prize in economic sciences 2012

현실과 시장경제에서 자원들을 어떻게 잘 매칭할 수 있을까? 예를 들어 이런 경우가 있다. 학생들이 다음 교육기관에 어떻게 진학할 것인가? 학교마다 정원이 정해져 있으므로 모든 학생이 원하는 학교 갈 수는 없을 것이다. 기증받은 장기를 어떤 환자에게 이식할 것인가? 장기의 수가 부족하니 가장 효율적인 방법을 찾아야 할 것이다. 2012년 노벨 경제학상을 받은 Alvin Roth와 Lloyd Shapley가 해결했다.

Matching Theory

Gale과 Shapley는 matching을 분석하기 위해 쉽게 그릴 수 있는 예시인 결혼을 생각했다. 여기서 stable matching은 어떤 커플도 깨지고 싶지 않아하는 상태를 말할 수 있다. 이 예시는 이렇게 설정된다. 1. 남자나 여자가 프로포즈를 하는데 가장 선호하는 사람에게 한다. 2. 가장 선호하는 사람에게 프로포즈를 받으면 수락하고 나머지는 거절한다. 3. 거절당하면 다음으로 선호하는 사람에게 프로포즈를 한다. 모두가 짝을 만날 때까지 반복한다. Gale과 Shapley는 이 알고리즘이 언제나 stable matching을 만들어 낸다는 것을 보였다.

Evidence

미국 의대생들이 졸업 전에 병원과 어떻게 match될 것인가에 대한 문제이다. 학생들을 놓치지 않기 위해 offer시기가 점점 빨라져 학생들이 충분히 자격을 갖추기 전에 계약이 진행되었고, 학생들은 다음에 어떤 기회가 있는지 알지도 못한 상태로 결정을 내려야 했다. Gale-Shapley Algorithm과 밀접한 NRMP가 해결했다.

Matching students and high-schools

Gale-Shapley 알고리즘은 상급학교 진학 등 다른 응용 문제에도 유용하다. 가장 가고 싶은 학교 5개를 정하고 같은 알고리즘으로 최선의 선택을 만들어낼 수 있다. 오늘날에도 많은 지역들이 Gale-Shapley 알고리즘의 다양한 변형을 이용하고 있다.

Matching kidneys and patients

지금까지는 matching의 주체 양 쪽 모두가 의지를 갖고 있는 경우를 보았다. 장기이식의 경우는 조금 다른데, 한 쪽은 완전히 Passive하다. Top trading cycle 이라고 하는 이 알고리즘은 initial allocation과 subsequent swapping이 핵심이다.

Graph Theory in the Information Age

Graph Theory in the Information Age

그래프 이론은 그래프라고 하는 수학 구조를 공부하는 것을 말한다. 200년 역사 중 지난 10년 간 그래프 이론은 엄청난 변화를 겪었다. WWW의 웹 페이지들과 하이퍼링크들을 그래프 요소인 vertex와 edge로 보면 그래프 이론을 기반으로 웹 관련 알고리즘들을 만들 수 있었던 것이다. 훨씬 크고, 복잡하고, 방대한 그리고 실생활에 아주 밀접한 그래프를 다루는 'network science'가 등장했다. 네크워크의 많은 정보들을 다루려고 하다보니, 새로운 고민들이 생겼다. 이렇게 큰 네트워크는 구조를 어떻게 그려야하지? 어떻게 발전시키지? 그래프 작동의 기본적인 원리는 무엇일까? 이런 질문에 답하기 위해서 비록 충분하지는 않지만 먼저 기존 그래프 이론을 깊이 탐구하였다.

Random Graph Theory for General Degree Distributions

Erdos 와 Renyi 는 n개의 점 위에 정의된 그래프로서 두 점을 잇는 선분의 발생 확률을 p 로 주어 만들어지는 그래프 G(n, p) 를 랜덤 그래프의 모델로 선정하였다. 랜덤 그래프는 n 개의 점들 위에서 정해진 확률에 따라 선분이 한 개씩 늘어나면서 진화하는(evolve) 유기체로 이해될 수도 있다. 그렇다면 그래프가 진화하는 동안 어느 시점에 어떤 특정한 성질을 갖게 될까?

Random Subgraphs in Given Host Graph

많은 네트워크가 log n 이하의 작은 지름을 가지는데, 이를 small world phenomenon이라고 한다. 랜덤한 서브 그래프들을 다루는 방법 중 하나에는 여과하기 방법이 있다. 확률 threshold를 정하고 넘지 못하는 bond는 삭제하는 것이다. 이 방법으로 전염병의 확산 등을 알 수 있다.

PageRank and Local Partitioning

실제 세상을 표현한 그래프는 기본적으로 small world phenomenon이기 때문에 각 점들은 매우 짧은 path로 연결되어 있다. 1998년 Brin과 Page는 구글 웹 서치를 위해 PageRank라는 알고리즘을 고안했다. 페이지랭크는 더 중요한 페이지는 더 많은 사이트와 연결되었다는 사실을 이용하고 있다.

Network Games

아침마다 모든 사람들이 제일 빠르고 편한 길을 찾듯이, 게이머들은 기본적으로 이기기 위한 이기적인 플레이를 한다. 고전 그래프 이론은 게임의 입장에서 볼 수 도 있다. 예를 들어 인접한 점들은 다른 색을 가져야 하는 색칠하기 등이 있다.