램지수에 관한 Burr와 Erdős의 추측
2015년 봄에 KAIST 수리과학과 졸업생인 MIT의 이중범 박사가 램지이론에 관한 Burr와 Erdős의 1973년 추측을 해결한 논문을 인터넷에 공개하여 놀라게 했었습니다. 이중범 박사는 9월에 KAIST 수리과학과 콜로퀴엄에서 그 결과를 알기쉽게 강연해주었는데요, 그 내용을 소개해볼까 합니다.
데이비드 콘론 교수를 소개한 글에서도 램지 이론이 조금 소개되었습니다. 가장 간단한 경우로 6명이 있으면 그 중 어떤 3명은 서로 아는 사이거나, 어떤 3명은 서로 모르는 사이라는 결과가 있지요. 이 상황을 그래프 언어로 표현하면 꼭지점 6개짜리 완전그래프 $K_6$의 각 선을 빨강이나 파랑으로 색칠하면 항상 빨강색...
옥스포드대학 데이비드 콘론 교수
편집자주: 서울에서 열릴 2014 세계수학자대회(ICM)를 기념하여, 조합수학 분야의 기조강연자 및 초청강연자들을 소개하는 글을 준비하였습니다. 이번 글은 2014년 8월 15일 오후 3시에 강연할 옥스포드 대학 데이비드 콘론(David Conlon) 교수에 대해, 그의 첫 박사과정 지도학생인 이준경 학생이 소개하는 글을 싣습니다.
David Conlon
1982년 태어난 콘론 교수는 아일랜드 출신으로, 필즈 메달 수상자인 Timothy Gowers 교수의 지도를 받고 캠브리지 대학에서 박사를 받았습니다. 콘론 교수의 전문 분야는 극단 조합론(extremal combinatorics)의 중심이라 할 수 ...
하트비거(Hadwiger)의 추측과 그 특수경우
Hugo Hadwiger (Pictures from Oberwolfach Photo Collection, CC-BY-SA-2.0-de)
평면 상에 교차점 없이 그릴 수 있는 그래프를 평면그래프라 한다. 모든 평면그래프는 이웃한 꼭지점이 서로 다른 색이 되도록 4개 이하의 색으로 잘 칠할 수 있다는 정리를 4색정리라고 하는데, 그래프이론에서 4색정리만큼 잘 알려지고 많은 사람들의 관심을 받은 문제는 없다고 해도 과언이 아니다. 이제 4색정리는 증명이 되었지만, 또 어떤 문제들이 남아있을까?
어떤 그래프 H가 그래프 G의 마이너라 함은, G에서 일부 변과 꼭지점을 지운 후 몇몇 변은 양 끝점을 한 점으로 합치는 ...
등차수열 여러 개로 정수 집합 덮기
…, -2, 0, 2, 4, 6, 8, 10, … (짝수)
…, -3, 0, 3, 6, 9, 12, 15, … (3의 배수)
…, -3, 1, 5, 9, 13, 17, … (4의 배수+1)
…, -5, 3, 11, 19, 27, 35, … (8의 배수+3)
…, -5, 7, 19, 31, 43, … (12의 배수+7)
…, -1, 23, 45, 68, … (24의 배수+23)
어떤 수 $n$을 24로 나눈 나머지를 생각해보면 모든 정수는 위 등차수열 중 적어도 하나에는 반드시 포함됨을 알 수 있다. 유명한 수학자 에르되시(Erdős)는 1950년 논문에서 임의의 $N$에 대해, 공차가 $N$ 이상인 등차...
잘 짜인 동아리 (Generalized Steiner System)
전체 $n$명의 사람이 있는 학교에서 $q$명의 학생들로 구성된 동아리들이 있다고 한다. 그런데 아무렇게나 $r$명의 학생을 모아도 그 $r$명이 동시에 속한 동아리의 수는 정확히 $\lambda$로 똑같다고 한다. 과연 $n$, $q$, $r$, $\lambda$ 값이 어떤 경우에 이런 식으로 동아리들을 구성할 수 있을까?
$i\le r$인 어떤 수 $i$에 대해, 학생 $i$명의 집합 $Z$를 생각해보자. 이 집합 $Z$의 학생을 동시에 포함한 $r$명의 학생의 집합$Y$는 정확히 $\binom{n-i}{r-i}$개가 있으므로, 집합 $Z$의 학생을 동시에 포함한 동아리 $X$가 있을 때 $(X,Y)$의 순서...