에르디시와 레니의 수학적 정수론에 대한 고찰을 알아본다. 네덜란드의 암스테르담에서 만난 에르디시와 레니는 정수론에 대한 연구를 했고 그 결과로 연속되는 소수에 대한 논문을 발표했다. 그 논문 들은 수학의 모든 분야를 포괄하는 그들의 절충주의적 성향을 반영하고 있다. 두 사람 모두 확률론에 대한 애정으로 이를 광범위한 분야의 문제들에까지 적용했다.
무작위 그래프 이론 분석
이들이 연구한 순수 수학은 그것에만 그치지 않고 종종 현실 세계에도 응용할 수 있는 가능성도 보이고 있었다. 예를 들어서 그들이 쓴 한 논문은 공항의 개수가 1개로 제한된 나라에서 여행을 할 때 승객이 한 번이라도 비행기를 갈아탈 필요가 없으려면 얼마나 많은 다양한 노선을 설정해야 하는가에 대한 문제를 다루었다.
최적 그래프 이론의 문제로 알려진 이 문제는 현실 세계에서 똑같은 형태 그대로 재현될 가능성은 없지만 이들이 얻어낸 결과와 같은 종류의 문제는 실제로 교통망과 통신망의 문제와 관련된다. 에르디시와 레니가 공동으로 진행한 연구 가운데 가장 독창적이고 가장 영향력 있는 업적은 1959년에 씌어진 ‘무작위 그래프의 전개에 관하여(On the Evolution of Random Graphs)’라는 신비스런 제목으로 발표된 일련의 고전적인 논문들에 들어 있다.
이 논문들은 순전히 저자들의 수학적 호기심을 충족하기 위해 쓴 것이지만, 생명의 기원을 포함하여 폭 넓고도 다양한 현실 세계의 현상들을 설명해 주는 하나의 열쇠를 간직하고 있는 것으로 밝혀질 여지가 있는 것이다. 1957년 덴마크 아루스에서 알프레드 레니와 함께 연구를 이어 나갔다. 이들이 함께 연구한 확률론은 현실 세계에도 응용할 수 있다.
어느 날 토목 기사가 도시와 도시 사이에 도로를 놓는 문제를 동전을 던져서 결정한다는 가정으로 질문을 해왔다. 예를 들어 앞면이 나오면 알바니와 보스턴 사이에 도로를 건설하고, 뒷면이 나오면 건설하지 않는다고 질문했다. 이렇게 우연에 의해 얻어진 도로망을 무작위 그래프라고 한다.
에르디시는 파티 문제를 일반화하기 위해 램지 이론에서 무작위 그래프를 사용하였다. 즉 N명의 사람들이 모두 서로를 알거나 혹은 N명의 사람들이 서로 아는 사람이 전혀 없게 하려면 파티의 규모는 어느 정도가 되어야 하는가? 이미 앞서 논의했듯이 N이 5 이상일 때는 답을 아는 사람이 아무도 없다. 그런데 에르디시는 무작위 그래프를 사용하여 필요한 최소 인원 수의 하계(下界, lower bound)를 찾아내는 독창적인 방법을 고안해 냈다.
예컨데 각각의 손님을 그래프의 꼭지점이라고 가정해 보자. 그래프 이론의 문제로 바꿔 볼 수 있는데 두 정점은 정점으로 대변되어 지는 손님들이 서로를 알 경우에만 그리고 그 때에 한해서만 선분으로 연결된다. N명의 사람들로 이루어진 집단에서 그들 모두가 서로 아는 사이 라면 그 집단은 모든 점들이 서로 선분으로 연결되어진 N개의 정점을 가진 집합과 같다.
N명의 사람들의 집단에서 그들 모두가 낯선 사람이라면 그 집단은 간단하게 서로 아무것에도 연결되어지지 않는 N개의 정점을 가진 집합이 된다. 예를 들어서, 적어도 일곱 명 모두가 서로 아는 사이 이거나 또는 서로 모르는 사이라는 조건을 만족하려면 파티의 규모가 어느 정도여야 하는지 결정하려고 한다고 하자.
에르디시는 G명이 초대된 무작위 파티가 이러한 특성을 갖지 못할 확률을 계산했다. 그 확률이 보 다 크고 1보다 작으면, G명이 초대된 그 무작위 파티는 이러한 성질을 갖거나 아니면 그 성질을 갖지 않으므로 이 파티가 그 성질을 가질 확률은 0보다 크게 된다.
에르디시와 스펜서 그리고 많은 다른 수학자들의 손에서 확률적 방법이 탄생했다. 종종 에르디시 방법이라 불리기 이전까지 어렵다고 생각되었던 문제들을 해결하는 강력한 도구가 되었다. 여기에는 마술과 같은 요소가 있다고 스펜서는 인정한다. 에르디시는 확률적 방법을 사용하여 모자에서 토끼가 나오게 하기도 하고 또 다른 묘기를 부려 청중에게 보여 주는 마술사였다.
토끼의 귀를 붙잡아 들어 올리는 일은 에르디시가 연습문제로 다른 사람들을 위해 남겨 두었다. 에르디시의 모자 속에 들어 있던 토끼들은 종종 컴퓨터의 디자인이나 정보 네트워크와 같은 현실세계의 문제들에 대한 해결책이 될 수 있음이 밝혀졌다. 에르디시의 확률적 방법은 해결 방법이 존재한다는 것을 보장 하고 있다.
그러나 이를 실제로 찾아내는 것은 또 다른 문제이다. 건초 더미에 바늘 한 개가 들어 있다는 것을 안다고 해서 반드시 건초 가닥을 하나 하나 훑어서 찾아내는게 실제로 도움이 된다고 할 수는 없다. 적절한 시간 안에 성공적으로 탐색하기 위해서는 자석을 사용하여 바늘을 찾아 낸다든지 하는 다른 묘책도 동원되어야만 한다.
수학에서는 그러한 수법들을 알고리즘이라 부르는데 이는 일반적으로 컴퓨터의 도움을 받아 문 제를 해결하는 체계적인 과정이다. 지난 20년 간 아주 흥미롭게 다뤄진 이 확률적 방법은 ‘에르디시로부터 알고리즘까지’ 라고 부른다”고 스펜서 는 말한다.
1970년대 이래로 컴퓨터 이론 과학자들과 수학자들은 에르디시의 플라토닉한 추상적 사고를 현실적인 문제를 해결할 수 있는 알고리즘으로 바꾸는 방법들을 개발해 왔다. 또한 에르디시가 권위자였던 그래프 이론과 조합론이라는 이 두 분야는 한때 수학에서 낙후된 분야로 여겨 졌지만 지금은 컴퓨터 과학의 필수적인 도구이다.
하지만 에르디시 자신은 컴퓨터를 만진 적도 없었다. 인터넷이 점점 수학 문화의 중요한 부분 이 되면서는 친구들이 그를 대신해 전자우편을 보내거나 받아 전달했다고 스펜서는 말한다. 그런 에르디시가 컴퓨터 과학의 이론적인 발달에 그토록 지대한 영향을 끼쳤다는 것은 아이러니가 아닐 수 없다.
에르디시의 수많은 연구들의 일관된 주제를 찾으라면 단연 질서와 혼돈 사이의 미묘한 관계라고 할 수 있다. 램지 이론에 대한 그의 연구에 이 주제가 가장 잘 나타나 있다. 그는 이 연구에서 완전한 혼돈은 불가능하 다는 것을 보여 주었다.
1959년 에르디시와 레니는 일정한 패턴을 발견 할 수 없도록 그 구조를 신중하게 고안한 무작위 그래프의 뒤엉킨 혼돈 상태에서 질서를 찾아봄으로써 이 주제를 추구했다. 놀랍게도 이와 같은 무작위 상태에서조차도 질서 있는 구조가 자발적으로 생겨나고 있었다. 에르디시와 레니가 분석한 상황은 앞서 언급한 토목 기사의 질문에 대한 이야기를 변형한 것이다.
다시 한 번 그 토목 기사가 여러 도시들 가령 만 개의 도시를 연결하는 도로 건설의 임무를 갖는다고 하자. 그는 거리를 무시하고 두 도시를 무작위로 선택하여 그 사이에 도로 건설을 시작한다. 이 작업을 끝낸 기사는 두 도시를 무작위로 더 골라서 또 다른 도로를 건설한다. 기사는 이런 방식으로 일을 계속한다.
단, 두 개의 도시가 이미 연결되어 있다면 제2의 도로는 건설하지 않는다. 처음에 도로는 소수의 도시만을 연결해 줄 것이다. 그러나 기사가 도로를 건설해 나감에 따라 작지만 서로 연결되어 형성된 일단의 도시 군락이 나타날 것이다. 이 도시 군락에 사는 사람들은 일련의 도로를 따라 같은 도시 군락 내에서 다른 도시로 차를 몰아갈 수 있다.
에르디시와 레니는 처음에 도시 군락들은 크기가 작고 흩어져 있음을 발견했다. 그 기사가 도로를 점점 더 많이 추가로 건설하면서 도시 군락의 크기는 아주 천천히 증가하며, 그 도시 군락 안의 도시들은 점점 더 많이 서로 연결되고 있다. 도로의 수가 도시 수의 절반에 근접할 때까지 크게 변화하는 것은 없다.
그러다가 기적과 같은 일이 일어난다. 아주 작은 수의 도로만을 추가로 건설하자, 갑자기 고립되어 있던 수많은 도시 군락들이 서로 연결되어 거의 모든 도시를 총망라하는 하나의 거대한 도시군락을 형성한 것이다. 작고 고립된 도시 군락에서 하나의 거대한 도시 군락으로의 급속한 변화는 물이 갑작스럽게 얼어 붙는다거나 교통 마비와 같은 수많은 자연 현상과 놀랄 정도로 유사하다.
위상 변환으로 알려져 있는 이러한 현상에 과학자들은 오랫동안 매료 되어 왔고 동시에 당황하기도 했다. 순전히 수학적 호기심을 충족시키기 위해 행해진 에르디시와 레니의 [무작위 그래프 분석] 은 위상 변환의 메커니즘을 규명하는 데 도움이 되는 간단한 모델을 제시해 주었다. 이 논문은 전혀 새로운 하나의 독립된 분야를 탄생 시켰다고 에르디시의 수제자인 조엘 스펜서는 진술하고 있다.