풀커슨상

1. 개요

풀커슨 상은 1979년 델버트 레이 풀커슨을 기리기 위해 제정된 상으로, 미국 수학회와 수리최적화학회가 공동으로 3년마다 이산 수학 분야의 획기적인 연구를 수행한 학자들에게 수여한다. 최대 3개의 논문까지 선정하며, 1994년 이후 상금은 1,500 미국 달러이다. 역대 수상자로는 리처드 매닝 카프, 닐 로버트슨, 폴 시모어, 김정한 등이 있다.

2. 역사

풀커슨 상은 1979년에 미국의 수학자 델버트 레이 풀커슨/Delbert Ray Fulkerson^영어(1924년 8월 14일~1976년 1월 10일)을 기리기 위하여 창설되었고, 이후 3년마다 수여되고 있다. 미국 수학회와 수리최적화학회에서 공동으로 수여한다. 한 번에 최대 3개의 논문까지 수여될 수 있으며, 각 논문의 공저자의 수는 제한이 없다.

상금은 원래 750 미국 달러였으나, 1994년에 1500 미국 달러로 증가하였다.

3. 역대 수상자

풀커슨 상은 이산 수학 분야에서 획기적인 연구를 수행한 학자들에게 수여된다.

3.1. 1970년대

리처드 M. 카프는 많은 중요한 NP-완전 문제들을 분류한 공로를 인정받았다. 케네스 아펠과 볼프강 하켄은 4색 정리 증명에 기여했다. 폴 세이모어는 최대 흐름 최소 절단 정리를 매트로이드로 일반화했다.

3.1.1. 1979년

리처드 M. 카프는 많은 중요한 NP-완전 문제들을 분류한 공로를 인정받았다. 케네스 아펠과 볼프강 하켄은 4색 정리 증명에 기여했다. 폴 세이모어는 최대 흐름 최소 절단 정리를 매트로이드로 일반화했다.

3.2. 1980년대

* 1982년:
다비트 보리소비치 유딘(Давид Борисович Юдин^러시아어), 아르카디 세묘노비치 네미롭스키(Аркадий Семёнович Немиро́вский^러시아어), 레오니트 겐리호비치 하치얀(Леонид Генрихович Хачиян^러시아어, Լեոնիդ Գենրիխովիչ Խաչիյան^{아르메니아어}), 마르틴 그뢰첼(Martin Grötschel^독일어), 로바스 라슬로, 알렉산더르 스흐레이버르(Alexander Schrijver^{네덜란드어})는 선형 계획법과 조합 최적화 분야의 타원체 방법 연구에 기여하였다.
게오르기 페트로비치 예고리체프(Георгий Петрович Его́рычев^러시아어), 드미트리 이힐로비치 팔리크만(Дмитрий Ихилович Фаликман^러시아어)은 모든 항목이 동일한 행렬이 모든 이중 확률 행렬 중 가장 작은 영구를 갖는다는 판 데르 바르덴의 추측을 증명하였다.
* 1985년:
베크 요제프(Beck József^헝가리어)는 불일치의 산술 진행에 대한 타이트한 경계를 제시하였다.
헨드릭 빌럼 렌스트라 2세(Hendrik Willem Lenstra, Jr^{네덜란드어})는 수의 기하학을 사용하여 제약 조건 수에 대해 다항식 시간 내에 변수가 적은 정수 계획법을 해결하였다.
유진 마이클 럭스(Eugene Michael Luks^영어)는 경계가 있는 최대 차수의 그래프에 대한 다항 시간 그래프 동형 알고리즘을 개발하였다.
* 1988년:
터르도시 에버(Tardos Éva^헝가리어)는 최소 비용 순환을 강하게 다항 시간 내에 찾았다.
** 나렌드라 크리슈나 카르마르카르(Narendra Krishna Karmarkar)는 선형 계획법에 카르마르카 알고리즘을 적용하였다.

3.2.1. 1982년

다비트 보리소비치 유딘(Давид Борисович Юдин^러시아어), 아르카디 세묘노비치 네미롭스키( Аркадий Семёнович Немиро́вский^러시아어), 레오니트 겐리호비치 하치얀(Леонид Генрихович Хачиян^러시아어, Լեոնիդ Գենրիխովիչ Խաչիյան^{아르메니아어}), 마르틴 그뢰첼(Martin Grötschel^독일어), 로바스 라슬로, 알렉산더르 스흐레이버르(Alexander Schrijver^{네덜란드어})는 선형 계획법과 조합 최적화 분야의 타원체 방법 연구에 기여하였다. 게오르기 페트로비치 예고리체프(Георгий Петрович Его́рычев^러시아어), 드미트리 이힐로비치 팔리크만(Дмитрий Ихилович Фаликман^러시아어)은 판 데르 바르덴 추측을 증명하였다.

3.2.2. 1985년

* 베크 요제프/Beck József^헝가리어는 불일치 이론에서 산술 진행에 대한 타이트한 경계를 제시하였다.
* 헨드릭 빌럼 렌스트라 2세/Hendrik Willem Lenstra, Jr^{네덜란드어}는 수의 기하학을 이용, 변수가 적은 정수 계획법을 다항식 시간에 해결하였다.
* 유진 마이클 럭스/Eugene Michael Luks^영어는 최대 차수가 제한된 그래프에 대한 다항 시간 그래프 동형 알고리즘을 개발하였다.

3.2.3. 1988년

터르도시 에버(Tardos Éva^헝가리어)는 최소 비용 순환 문제를 강하게 다항 시간 내에 해결한 공로로 수상하였다. 나렌드라 크리슈나 카르마르카르(Narendra Krishna Karmarkar)는 선형 계획법에 카르마르카 알고리즘을 적용한 공로로 수상하였다.

3.3. 1990년대

wikitext

3.3.1. 1991년

마틴 다이어(Martin E. Dyer^영어), 앨런 프리즈(Alan M. Frieze^영어), 라빈드란 칸난(Ravindran Kannan)은 무작위 보행을 기반으로 볼록체의 부피를 근사하는 알고리즘을 개발한 공로로 수상했다. 앨프리드 리먼(Alfred Lehman^영어)은 0,1-행렬을 사용하여 완전 그래프 이론을 연구한 공로로 수상했다. 니콜라이 예브게니예비치 므뇨프(Николай Евгеньевич Мнёв^러시아어)는 므뇨프의 보편성 정리를 증명한 공로로 수상했다.

3.3.2. 1994년

* 루이스 빌레라(Louis J. Billera)는 공간 삼각 측량에서 조각별 다항식 함수 공간의 기저를 발견했다.
* 길 칼라이(גיל קלעי)는 d 차원 다포체의 직경에 대한 지수 함수적 경계를 증명하여 허쉬 추측에 대한 진전을 이루었다.
* 닐 로버트슨, 폴 시모어, 로빈 토마스는 하드위거 추측의 6-색 경우를 증명했다.

3.3.3. 1997년

김정한은 램지 수 R(3, t)의 점근적 성장률을 발견한 공로로 풀커슨상을 수상했다. 김 교수의 수상은 한국 수학의 위상을 크게 높였다는 평가를 받는다.

3.4. 2000년대

* 2000년:
미셸 그자비에 괴망/Michel Xavier Goemans^프랑스어과 데이비드 윌리엄슨/David P. Williamson^영어은 반정부 계획법 기반 근사 알고리즘 개발에 기여했다.
미켈란젤로 콘포르티(Michelangelo Conforti^{이탈리아어}), 제라르 피에르 코르뉘에졸(Gérard Pierre Cornuéjols^프랑스어), 멘두 람모한 라오(Mendu Rammohan Rao)는 균형 0-1 행렬을 다항 시간 내에 인식하는 방법을 제시했다.
* 2003년:
제임스 길런/James F. Geelen^영어, 알버르트 헤라르츠/Albert M. H. Gerards^{네덜란드어}, 아자이 카푸르(Ajai Kapoor)는 매트로이드 소수에 관한 로타 추측의 GF(4) 경우를 증명하였다.
버트런드 게닌(Bertrand Guenin^영어)은 약하게 이분 그래프 (이분 그래프 부분 그래프 다면체가 0-1인 그래프)의 금지된 그래프 특성을 개발하였다.
이와타 사토루/岩田 覚^일본어, Lisa Fleischer, 후지시게 사토루/藤重 悟^일본어, 알렉산더르 스흐레이버르/Alexander Schrijver^{네덜란드어}는 부분 모듈 최소화가 강하게 다항식임을 증명하였다.
* 2006년:
마닌드라 아그라왈, 니라지 카얄, 니틴 삭세나는 AKS 소수성 검사를 개발한 공로로 수상했다.
마크 제럼(Mark Jerrum^영어), 앨리스터 싱클레어(Alistair Sinclair^영어), 에릭 비고다(Eric Vigoda^영어)는 영구 근사에 기여한 공로로 수상했다.
닐 로버트슨(Neil Robertson^영어), 폴 시모어(Paul Seymour^영어)는 그래프 소수가 좋은 준 순서를 형성한다는 것을 보여주는 로버트슨-세이모어 정리를 증명한 공로로 수상했다.
* 2009년:
마리아 추드노브스키(Maria Chudnovsky^영어, מריה צ'ודנובסקי^히브리어), 닐 로버트슨(Neil Robertson^영어), 폴 시모어(Paul Seymour^영어), 로빈 토머스(Robin Thomas^영어)는 강한 완전 그래프 정리를 증명한 공로로 2009년 풀커슨상을 수상했다.
대니얼 앨런 스필먼(Daniel Alan Spielman^영어)과 텅샹화()는 선형 계획법 알고리즘의 평활화 분석에 기여한 공로로 2009년 풀커슨상을 수상했다.
** 토머스 캘리스터 헤일스(Thomas Callister Hales^영어)와 새뮤얼 퍼구슨(Samuel P. Ferguson^영어)은 가능한 가장 조밀한 구형 포장에 대한 케플러 추측을 증명한 공로로 2009년 풀커슨상을 수상했다.

3.4.1. 2000년

* 미셸 그자비에 괴망/Michel Xavier Goemans^프랑스어과 데이비드 윌리엄슨/David P. Williamson^영어은 반정부 계획법 기반 근사 알고리즘 개발에 기여했다.
* 미켈란젤로 콘포르티(Michelangelo Conforti^{이탈리아어}), 제라르 피에르 코르뉘에졸(Gérard Pierre Cornuéjols^프랑스어), 멘두 람모한 라오(Mendu Rammohan Rao)는 균형 0-1 행렬을 다항 시간에 인식하는 방법을 제시했다.

3.4.2. 2003년

* James F. Geelen^영어, Albert M. H. Gerards^{네덜란드어}, 아자이 카푸르(Ajai Kapoor)는 로타 추측의 GF(4) 경우를 증명하였다.
* 버트런드 게닌(Bertrand Guenin^영어)은 약하게 이분 그래프 (이분 그래프 부분 그래프 다면체가 0-1인 그래프)의 금지된 그래프 특성을 개발하였다.
* 岩田 覚^일본어, Lisa Fleischer, 藤重 悟^일본어, Alexander Schrijver^{네덜란드어}는 부분 모듈 최소화가 강하게 다항식임을 증명하였다.

3.4.3. 2006년

마닌드라 아그라왈, 니라지 카얄, 니틴 삭세나는 AKS 소수성 검사를 개발한 공로로 수상했다.

마크 제럼(Mark Jerrum^영어), 앨리스터 싱클레어(Alistair Sinclair^영어), 에릭 비고다(Eric Vigoda^영어)는 영구 근사에 기여한 공로로 수상했다.

닐 로버트슨(Neil Robertson^영어), 폴 시모어(Paul Seymour^영어)는 그래프 소수가 좋은 준 순서를 형성한다는 것을 보여주는 로버트슨-세이모어 정리를 증명한 공로로 수상했다.

3.4.4. 2009년

마리아 추드노브스키(Maria Chudnovsky^영어, מריה צ'ודנובסקי^히브리어), 닐 로버트슨(Neil Robertson^영어), 폴 시모어(Paul Seymour^영어), 로빈 토머스(Robin Thomas^영어)는 강한 완전 그래프 정리를 증명한 공로로 2009년 풀커슨상을 수상했다.

대니얼 앨런 스필먼(Daniel Alan Spielman^영어)과 텅샹화()는 선형 계획법 알고리즘의 평활화 분석에 기여한 공로로 2009년 풀커슨상을 수상했다.

토머스 캘리스터 헤일스(Thomas Callister Hales^영어)와 새뮤얼 퍼구슨(Samuel P. Ferguson^영어)은 가능한 가장 조밀한 구형 포장에 대한 케플러 추측을 증명한 공로로 2009년 풀커슨상을 수상했다.

3.5. 2010년대

* 2012년
산지브 아로라, 사티시 라오, 우메시 바지라니는 그래프 분리자 및 관련 문제에 대한 근사 비율을 $O(\backslash log\; n)$에서 $O(\backslash sqrt\{\backslash log\; n\})$으로 개선하였다.
안데르스 요한손(Anders Johansson^스웨덴어), 제프 칸, 부하반(Vũ Hà Văn^베트남어)은 무작위 그래프가 주어진 작은 그래프의 분리된 복사본으로 덮일 수 있는 가장자리 밀도의 임계값을 결정하였다.
로바스 라슬로, 세게디 벌라주(Szegedy Balázs^헝가리어)는 밀집 그래프 시퀀스에서 부분 그래프 다중성을 특성화하였다.
* 2015년
프란시스코 산토스 레알은 허쉬 추측의 반례를 제시하였다.
* 2018년
로버트 모리스, 고바야카와 요시하루, 사이먼 그리피스, 피터 앨런, 그리고 율리아 뵈처는 그래프의 색 임계값에 기여.
토마스 로스보스는 매칭 다포체의 확장 복잡도에 대한 연구를 수행하였다.

3.5.1. 2012년

* 산지브 아로라, 사티시 라오, 우메시 바지라니는 그래프 분리자 및 관련 문제에 대한 근사 비율을 $O(\backslash log\; n)$에서 $O(\backslash sqrt\{\backslash log\; n\})$으로 개선하였다.
* 안데르스 요한손(Anders Johansson^스웨덴어), 제프 칸, 부하반(Vũ Hà Văn^베트남어)은 무작위 그래프가 주어진 작은 그래프의 분리된 복사본으로 덮일 수 있는 가장자리 밀도의 임계값을 결정하였다.
* 로바스 라슬로, 세게디 벌라주(Szegedy Balázs^헝가리어)는 밀집 그래프 시퀀스에서 부분 그래프 다중성을 특성화하였다.

3.5.2. 2015년

프란시스코 산토스 레알은 허쉬 추측의 반례를 제시한 공로로 2015년 풀커슨상을 수상했다.

3.5.3. 2018년

로버트 모리스, 고바야카와 요시하루, 사이먼 그리피스, 피터 앨런, 그리고 율리아 뵈처는 그래프의 색 임계값에 대한 연구로 수상하였다. 토마스 로스보스는 매칭 다포체의 확장 복잡도에 대한 연구로 수상하였다.

3.6. 2020년대

wikitext
* 2021년:
벨라 차바, 다니엘라 퀸, 앨런 로, 데리크 오스투스, 앤드류 트레글론은 1-요인 분해 및 해밀턴 분해 추측 증명에 기여.
진이 차이 및 시 첸은 복소 가중치를 갖는 CSP 계산의 복잡성에 기여.
가와라바야시 켄이치 및 미켈 토럽은 거의 선형 시간 내의 결정적 가장자리 연결성에 기여.
* 2024년:
벤 커즌스(Ben Cousins^영어)와 산토시 쳄팔라는 가우스 냉각과 $O^*(n^3)$ 부피 및 가우스 부피 알고리즘에 기여.
질린 장, 조나단 타이도르, 위안 야오, 셴통 장, 그리고 위페이 자오는 고정된 각을 갖는 동일각선에 기여.
네이선 켈러와 노암 리프시츠는 초그래프에 대한 훈타 방법과 에르되스-츠바탈 단체 추측에 기여.

3.6.1. 2021년

* 벨라 차바, 다니엘라 퀸, 앨런 로, 데리크 오스투스, 앤드류 트레글론은 1-요인 분해 및 해밀턴 분해 추측 증명에 기여.
* 진이 차이 및 시 첸은 복소 가중치를 갖는 CSP 계산의 복잡성에 기여.
* 가와라바야시 켄이치 및 미켈 토럽은 거의 선형 시간 내의 결정적 가장자리 연결성에 기여.

3.6.2. 2024년

벤 커즌스(Ben Cousins^영어)와 산토시 벰팔라는 가우스 냉각, 부피 및 가우스 부피 알고리즘 연구에 기여하였다. 질린 장, 조나단 타이도, 위안 야오, 션퉁 장, 유페이 자오는 고정된 각을 갖는 동일각선 연구에 기여하였다. 네이선 켈러와 노암 리프시츠는 초그래프에 대한 훈타 방법과 에르되스-츠바탈 단체 추측 연구에 기여하였다.