DIMAG is a new research group that was established in December 1, 2018 at the Institute for Basic Science (IBS), led by Prof. Sang-il Oum. DIMAG is located at the headquarters of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.
Successful candidates for postdoctoral research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of discrete mathematics with emphasis on structural graph theory, extremal graph theory, combinatorial optimization, matroid theory, or fixed-parameter tractable algorithms.
These non-tenure-track appointments are for two or three years, and the starting salary is no less than KRW 57,000,000. The appointment is one time renewable up to 5 years in total contingent upon the outstanding performance of the researcher.
These are purely research positions and research fellows will have no teaching duties.
A complete application packet should include:
AMS standard cover sheet (preferred) or cover letter (PDF format)
Curriculum vitae including a publication list (PDF format)
For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to dimag@ibs.re.kr by April 26, 2020, Sunday. Recommendations letters forwarded by an applicant will not be considered.
DIMAG encourages applications from individuals of diverse backgrounds.
For Korean citizens who have not yet completed their military duty: IBS는 병역특례지정기관입니다. IBS is a designated institute for alternative military service.
2018년부터 기초과학연구원에서는 연구단장이 이끄는 큰 규모의 기존 연구단 형태와는 다른, 새로운 연구단 제도를 만들었습니다. 이 새로운 연구단은 PRC라고 불리는데 PRC는 Pioneer Research Center의 약자입니다. 기존 기초과학연구원의 연구단은 1~2명의 연구단장이 하나의 큰 연구단을 책임지고 운영하는 형태였습니다.
PRC 형태의 연구단에서는 내부에 Chief Investigator, 약자로 CI로 불리는 여러 연구자가 독립적으로 운영하는 소규모 연구그룹을 만듭니다. 이 PRC 형태의 연구단의 연구단장은 거기에 속한 CI들이 돌아가며 맡기 때문에 PRC 자체는 여러 연구그룹을 모아놓는 우산과 같은 조직이 됩니다. 각 CI는 예산도 별도로 신청하여 받고 운영도 독립적으로 하지만, 같은 연구단 일은 같은 연구단 소속 다른 CI와 서로 협업을 통하여 운영합니다. 비유를 하자면 기존 연구단은 여러 연구팀으로 나누어 운영되는 경우가 많은데 PRC에서는 각 연구팀을 CI가 맡아서 독립적으로 운영한다고 생각하면 될 것 같습니다. CI를 한글로 어떻게 표시할 것인지에 대하여 의견 정리가 되지 않아서 한글 명칭은 없습니다.
기초과학연구원의 자료에 따르면 CI는 “소규모 연구그룹을 구성하여 기초과학분야의 모험적이며 창의적인 연구를 독립적으로 수행할 수 있는 젊은 연구자”라고 정의하며, 이러한 지원을 통하여 “세계적 연구기관의 연구책임자와 대등하거나 혹은 가까운 미래에 이들과 대등한 수준으로 성장할 잠재력이 큰 젊은 연구자에게 독립 연구를 지원함으로써 차세대 세계적 석학으로 육성”하겠다고 합니다. CI에게는 최대 연 10~15억원 예산의 연구그룹을 구성하고 독립연구를 수행할 권한을 부여합니다. CI는 출장비 등 여러 내부 규정에서 부연구단장에 준하는 대접을 받습니다. 참고로 CI가 받는 예산에는 CI 본인의 인건비도 포함되어 있습니다만, 과거와 달리 행정인력의 인건비는 제외되어 있습니다. 행정인력은 본원에서 직접 지원하기 때문입니다.
2018년 초에 처음으로 기초과학연구원에서 CI를 뽑겠다는 공고가 나왔습니다. 올해는 없지만 2018년에는 공개모집과 함께 추천 위원회(search committee)도 운영하여 후보를 추천하는 과정도 있었습니다. CI의 선정은 부연구단장에 준하는 방식으로 진행한다고 합니다. 제가 경험한 비공개 발표 평가에서는 필즈메달 수상자인 심사위원장과 함께, 누가 섭외하셨는지는 모르겠지만 해외에서 제 전공 분야 저명하신 학자분들이 일부러 시간을 내어 서울에 오셨고, 국내에서도 제 분야 여러 원로 교수님들께서 참여하셔서 많은 수고를 해주셨습니다. 공개 심포지엄, 비공개 발표 평가 등 엄정한 심사 과정을 거쳐 제도 시행 첫 해에 CI로 선정되어 매우 영광이고 귀중한 시간을 내어서 과정에 참여해주신 모든 분들께 감사하게 생각합니다.
수리 및 계산 과학 연구단
제도 첫 해인 2018년에는 총 3명의 CI가 선정되었습니다. 그 중 데이터 사이언스 그룹을 구성한 KAIST 전산학부 차미영 교수와 제가 수학 분야로 선정되었고, KAIST 의과학대학원의 김호민 교수는 생물 분야로 선정되었습니다. 김호민 교수는 혼자 속할 PRC 연구단의 이름을 “바이오분자 및 세포 구조 연구단”이라는 이름으로 만들었습니다. 저와 차미영 교수는 여러 논의를 거쳐 “수리 및 계산 과학 연구단”(Center for Mathematical and Computational Sciences)라는 이름으로 PRC 연구단 이름을 정하였습니다.
행정 업무를 위해서 본원 행정인력 중에서 파견받은 행정인력을 두 PRC 연구단이 공용으로 활용하고 있습니다. 원래 두 명이 배정되었으나 최근 한 분이 늘어나 총 세 분의 행정인력이 3명의 CI 활동을 지원하고 있습니다. 앞으로 채용이 진행되면 늘어날 것으로 기대하고 있습니다.
수리 및 계산 과학 연구단은 기초과학연구원 본원의 이론동 2층을 배정받았습니다.
이산수학그룹
이번에 시작한 연구그룹은 이산수학그룹, 영어로 Discrete Mathematics Group이라고 이름을 지었습니다. 약자로는 DIMAG이라고 정하였는데, DIMAG이 마침 힌디어로 두뇌라고 합니다. 홈페이지는 https://dimag.ibs.re.kr에서 볼 수 있습니다.
이 글을 부탁받고 가장 먼저 한 고민은 아직 연구진이 갖추어지지 않은 연구그룹을 어떻게 소개하는가 하는 걱정이었습니다. 아직 이산수학그룹이 시작된지 몇 달 되지 않았다는 점을 감안해서 읽어주시면 감사하겠습니다.
이산수학그룹의 목표는 크게 세 가지로 생각하였습니다.
이산수학, 그래프 이론 및 알고리듬 분야 분야의 세계적 연구를 수행
국내외 관련 분야 연구자들과의 협력 연구 촉진
관련 분야 세미나, 워크샵, 학회, 스쿨 등을 적극적으로 조직하여 연구 결과를 적극적으로 공유하고 아이디어를 나누며 미래 연구자들의 성장을 도움
첫 번째 목표를 위해서 현재는 연구진을 뽑는 작업을 진행하고 있습니다. 초기인만큼 주로 저의 관심분야에 가까우면서도 우수한 연구자들을 뽑고자 노력하고 있습니다.
첫 박사후 연구원을 뽑는 공고는 2018년 12월 중순이 지원 마감이었는데, 짧은 홍보기간에도 불구하고 국내외 많은 분들이 지원해주셨습니다. 서류 전형과 면접 전형을 거쳐 최종으로 3명의 연구자에게 오퍼를 보냈습니다. 고맙게도 세 명 모두 오퍼를 수락하였습니다. 3명 중 1명은 한국인으로 조합적 최적화를 전공하였으며 기초과학연구원에서 전문연구요원으로 복무하면서 박사후 연구원을 할 예정입니다. 나머지 2명은 극단적 조합론(extremal combinatorics)를 전공한 미국인과 인도인인데 둘 다 모두 그 분야에서 유명한 헝가리에서 박사 학위를 받았다는 공통점이 있습니다. 3명 모두 개인 사정상 여름에 합류할 예정입니다.
현재 4월 중순 마감으로 2차 모집 공고가 나갔습니다. 예산 상황 등을 고려하여 두 세 명을 뽑을 예정입니다.
출범되지 얼마되지 않았지만, 벌써 2019년 3월말까지 4건의 Discrete Math Seminar를 개최하였습니다. 관심있는 분들께서는 얼마든지 오셔서 강연을 들으실 수 있으며, 제게 연락하시면 세미나 공지를 이메일로 받으실 수 있게 도와드리겠습니다.
첫 워크샵이었던 “2019-1 IBS Workshop on Graph Theory”는 이화여대 김연진 박사와 공동주관으로 2월 11일부터 12일까지 1박 2일 일정으로 개최하였습니다. 국내 3명의 연사와 함께 체코, 헝가리, 미국에서 온 세 명의 연사가 연구 발표를 진행하였습니다. 올 여름 인천에서 열리는 조합론 학술대회도 공동개최를 할 예정입니다.
한편 올해 프랑스 CNRS의 김은정 박사와 함께, 7월 말부터 3주동안 “2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures”라는 이름의 여름 연구 프로그램을 개최합니다. 총 3주동안 관심사가 비슷한 연구자들이 기초과학연구원에 모여서 집중적으로 연구를 수행하려고 하며, 현재까지 14명의 해외 학자들이 2~3주씩 참가하겠다고 밝혀온 상태입니다.
올 가을에 해외에서 연구년을 이산수학그룹으로 오겠다고 하는 분들이 있어서 논의가 진행되고 있습니다. 국내분들 중에도 1월에 이산수학그룹에 1주일 이상 방문하셔서 연구하신 분도 계십니다. 이산수학그룹에 방문하셔서 연구하시고 싶다면 연락을 주시길 바랍니다. 이산수학그룹이 내부 인원만을 위한 것이 아니기에, 적극적으로 활용해주시면 감사하겠습니다.
기초과학연구원 본원은 대전의 옛 엑스포과학공원 부지에 지어졌습니다. 바로 동쪽에 한빛탑이 있으며 한빛탑을 지나서 걸어가면 롯데시티호텔, ICC 호텔, 대덕특구게스트하우스 등 방문자들을 위한 숙박시설이 충분히 있습니다. 바로 서쪽에는 현재 신세계 백화점 및 특급 호텔이 포함된 지상 43층의 신세계 사이언스 콤플렉스가 2021년 준공 예정으로 공사중입니다. 본원 건물에서 북쪽 방향에는 기초과학연구원의 게스트하우스 및 기숙사 형태의 숙소가 있어서 연구원들이 편하게 생활할 수 있습니다.
기초과학연구원의 본원 건물은 2017년 말에 준공되었습니다. 그런 까닭에 제가 들어오던 12월 초까지도 이론동 2층 전체는 방문 달린 것 말고는 아무것도 없었다고 해도 과언이 아닙니다. 한 달동안 엄청난 노력 끝에 수학자라면 누구나 부러워할 환경을 어느 정도 구축할 수 있었습니다. 기초과학연구원에서 Annals of Mathematics와 같은 수학 저널이나 미국수학회 MathSciNet을 인터넷을 통해 접속할 수 있게 된 것도 작년에 다 이루어진 일입니다.
이론동 2층에 위치한 커다란 칠판을 설치한 두 강의실에는 각각 동영상 촬영 장비를 설치하였습니다. 연사가 동의하는 경우 세미나 영상을 촬영하여 이산수학그룹 홈페이지 및 유투브에서 볼 수 있도록 올리고 있습니다.
토론실
수학 연구자들이 작은 그룹이나 큰 그룹으로 모여서 연구 토의를 할 수 있는 토론실이 작은 것 2개 큰 것 1개가 구축되어 있습니다. 그 중 큰 것에는 3면 벽이 모두 유리보드로 되어 있어서 넓은 보드 공간을 사용하며 연구에 집중할 수 있습니다. 한편 연구원들과 방문자들이 사용할 수 있는 연구실을 여럿 구축하였습니다.
기초과학연구원 본원에는 과학문화센터라는 부속건물이 있습니다. 거기에는 큰 학회를 개최할 수 있는 강당 뿐 아니라 여러 작은 강의실도 많이 있습니다. 대학에서는 학기 중에는 강의 때문에 강의실 대여가 어려운데, 여기서는 강의가 없으므로 그러한 행사 개최가 좀더 쉽습니다.
당부말씀
이산수학그룹의 모든 활동은 이산수학그룹 홈페이지에 공지를 하고 있습니다. 흥미로운 세미나나 워크샵이 있으면 적극적으로 참여 부탁드립니다.
현재까지 기초과학연구원 본원 건물에 출근하는 수학 박사는 저 뿐입니다. 현재 저를 제외하면, KAIST 소속 제 대학원생 3명과 KAIST 소속 그래프이론 전공 박사후 연구원이 이산수학그룹의 연구실을 가장 많이 사용하고 있습니다.
물리 분야의 경우 이론물리 분야 연구단 2개가 이론동 3층의 절반, 4층의 절반을 쓰고 있고 실험 분야도 있습니다. 물리 분야 이론 연구단들은 서로 티타임도 돌아가면서 하고 물리 분야 콜로퀴엄도 개최하는데, 수학은 아직 기초과학연구원 내에 사람이 적어서 그럴 형편이 되지 못합니다.
2019년에도 두 번째로 연구단장과 CI를 뽑는다는 공고가 나왔고 마감이 이미 끝난 상황입니다. 하나의 PRC 연구단에 5명의 CI까지 선정이 가능하다고 합니다. 기초과학연구원 본원 이론동 2층에는 아직 빈 공간이 많이 있고, 앞으로 오실 분들은 이미 연구환경이 어느 정도 구축되어서 저보다 쉽게 시작하실 수 있을 것입니다. 많은 수학자들이 기초과학연구원으로 옮겨오시거나 방문하셔서 자유롭게 연구에 몰입하며 함께 지낼 수 있길 기대합니다.
The Department of Mathematical Sciences at KAIST invites applications for a non-tenure track faculty position beginning from September 1, 2019.
In recent years, KAIST, one of the top research universities in Korea, has been recruiting distinguished scholars of both Korean and foreign nationalities. KAIST is located in Daejeon, a city with a population of 1.5 million, and its operation is financially supported by the Korean government. Most of the courses at KAIST are taught in English.
Applications are accepted from any areas of pure, applied, and interdisciplinary mathematics. Successful applicants must demonstrate outstanding accomplishments or potential in research and teaching.
An annual salary (between 50 to 60 million Korean won) will be commensurate with the experience and qualifications of candidates. The regular teaching load is two courses (at least 6 credits) per semester.
All applications must include the following:
KAIST non-tenure track faculty application form (DOC file)
Curriculum vitae with a publication list
Two recommendation letters; at least one should be related to teaching. (Recommenders should send their letters directly to the email address below.)
All applications should be sent to recruit@mathsci.kaist.ac.kr or to the mailing address below by Friday, May 17, 2019:
Yongnam Lee Head of the Department of Mathematical Sciences KAIST 291 Daehak-ro, Yuseong-gu, Daejeon, Republic of Korea Zip Code: 34141
With the vision of “Making Discoveries for Humanity and Society,” the Institute for Basic Science (IBS) was founded in 2011 by the Korean government to promote basic sciences in Korea. Thirty Research Centers have been launched and each Center has been yielding outstanding results in various fields of research. The IBS “Young Scientist Fellowship” started in 2016 to play an active role in fostering next-generation basic science leaders. We believe this fellowship offers opportunities to conduct independent research by utilizing state-of-art infrastructures and to grow on the basis of research collaborations with leading researchers. We hope that the YS Fellowship serves as a stepping stone for our research fellows to be appointed as independent principal investigators at the prestige institutions worldwide.
2. Eligibility
Within 5 years of obtaining a PhD or under the age of 40 with a PhD (born no earlier than January 1, 1979)※ Ph.D. candidates must be conferred with Ph.D. degrees before August 31, 2019 ※ Researchers currently participating in the IBS research centers are NOT eligible to apply
3. Recruiting Research Centers and Number of Openings
Discrete Mathematics Group has an opening for 1 person.
Annual budget of KRW150-300M per year including KRW60-70M salary
Appointment for 3 years with possible extension of 2 years based on the results of interim review (Full-time work and 100% research participation). ※ Please refer to FAQ for details.
After physically relocated to one of the IBS Centers, YSF conducts independent research by utilizing research facility and equipment of the Center (Can organize small research group).
Selected YSF shall commence his/her research between January 1, 2020 and December 31, 2020.
5. Selection Process: Three Steps
Letter of Intent
1. Submission deadline: ~ May 31, 2019
2. Review by Directors and Evaluation Panel members
3. Invitation to submit full proposals: ~ June 30, 2019
Full proposal
1. Submission deadline: ~ August 31, 2019
2. Review by Directors and Evaluation Panel members
3. Invitation for an on-site interview: ~ September 30, 2019
Interview
1. Interview and presentation: ~ November 15, 2019
2. Comprehensive review by Evaluation Panel chairs
3. Announcement of final YS Fellows: ~ November 30, 2019
The IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea invites applications for several postdoctoral research fellowship positions. The expected start date is the 1st of September 2019 but it can be negotiated; but the candidate should have a Ph.D. by the start date.
DIMAG is a new research group that was established in December 1, 2018 at the Institute for Basic Science (IBS), led by Prof. Sang-il Oum. DIMAG is located at the headquarters of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.
Successful candidates for postdoctoral research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of discrete mathematics with emphasis on structural graph theory, extremal graph theory, combinatorial optimization, matroid theory, or fixed-paramter tractable algorithms.
These non-tenure-track appointments are for two or three years, and the starting salary is no less than KRW 57,000,000. The appointment is one time renewable up to 5 years in total contingent upon the outstanding performance of the researcher.
These are purely research positions and research fellows will have no teaching duties.
A complete application packet should include:
AMS standard cover sheet (preferred) or cover letter (PDF format)
Curriculum vitae including a publication list (PDF format)
Research statement (PDF format)
At least 3 recommendation letters
For full consideration, applicants should email items 1, 2, and 3 and arrange their recommendation letters emailed to dimag@ibs.re.kr by Monday, April 15, 2019. Recommendations letters forwarded by an applicant will not be considered.
DIMAG encourages applications from individuals of diverse backgrounds.
For Korean citizens who have not yet completed their military duty: IBS는 병역특례지정기관입니다. IBS is a designated institute for alternative military service.
The IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea invites applications for several postdoctoral research fellowship positions. The expected start date is the 1st of March 2019 but it can be negotiated; it is possible to start earlier or later in 2019 but the candidate should have a Ph.D. by the start date.
DIMAG is a new research group that is established in December 1, 2018 at the Institute for Basic Science (IBS, www.ibs.re.kr), led by Prof. Sang-il Oum (dimag.ibs.re.kr/home/sangil/). DIMAG is located on the main campus of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.
Successful candidates for postdoctoral research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of discrete mathematics with emphasis on structural graph theory, extremal graph theory, combinatorial optimization, matroid theory, or fixed-paramter tractable algorithms.
These non-tenure-track appointments are for two or three years, and the salary range is KRW 57,000,000 – 66,000,000. The appointment is one time renewable up to 5 years in total contingent upon the outstanding performance of the researcher.
These are purely research positions and research fellows will have no teaching duties.
A complete application packet should include:
(1) AMS standard cover sheet (preferred) or cover letter (PDF format)
(2) Curriculum vitae including a publication list (PDF format)
(3) Research statement (PDF format)
(4) At least 3 recommendation letters
For full consideration, applicants should email items 1, 2, and 3 and arrange their recommendation letters emailed to dimag@ibs.re.kr by Friday, December 14, 2018. Recommendations letters forwarded by an applicant will not be considered.
DIMAG encourages applications from individuals of diverse backgrounds.
2017년 가을학기 교과목 수강신청기간을 맞이하여 지난 학기에 하였던 것처럼 이번 2017년 가을학기에 열릴 이산수학/그래프이론 관련 교과목 및 기타 흥미로운 교과목을 정리해봅니다.
MAS477 Introduction to Graph Theory (그래프이론개론). 월수 13:00~14:15, 엄상일
(네, 아시다시피 제가 하는 과목입니다.) 보통 매년 가을학기에 열렸으며 제가 연구년을 갔던 2013년에는 Andreas Holmsen 교수님이 강의를 하셨었고 작년에는 대수적 그래프이론 전공한 Brendan Rooney 교수님이 강의를 하였습니다. 2년만에 다시 하게 되었습니다.
그래프이론의 다양한 부분을 다룹니다. 보통 많이 생각하는 기초적인(?) 해밀턴 회로 오일러 회로 같은건 다루지 않습니다. 주요 내용을 언급하면 아래와 같습니다.
그래프 connectedness: 그래프가 얼마나 잘 연결되었는지, 그리고 한 점에서 다른 점으로 몇 개의 서로 겹치지 않가 있는지와 같은 Menger 정리 등.
그래프의 매칭: 남녀 학생을 짝지울때 써먹는(?) 홀의 결혼정리와 König의 정리, 그리고 남녀가 아닌 일반적인 그래프의 perfect matching에 관한 Tutte의 정리, 그리고 그래프의 maximum matching이 어떤 구조인지 설명하는 Gallai-Edmonds Structure 정리와 함께 Edmonds의 유명한 다항식 시간에 maximum matching 찾는 알고리듬을 다룹니다.
평면그래프: 이산수학 시간에는 정리만 배웠던 Kuratowski 정리를 엄밀하게 증명합니다. 오일러 공식 및 dual에 대해 다룹니다.
채색 문제: 4색정리5색정리를 증명합니다. List Coloring도 배우며 이를 통해 Thomassen의 다른 방식의 5색 정리 증명도 배웁니다. 그리고 perfect graph에 관한 성질도 배웁니다.
Flow 문제: 채색문제의 dual이라고 할 수 있는 nowhere-zero flow에 관해 배우고 관련된 Tutte의 유명한 추측들을 다룹니다.
그외 시간에 따라 다룰 가능성이 있는 주제: Turan 정리, Hadwiger 추측, Szemeredi의 Regularity lemma, Higman의 lemma, Kruskal의 well-quasi-ordering 정리, Robertson과 Seymour의 그래프 마이너 정리
MAS583C Topics in Analytic Combinatorics (해석조합론), 화목 10:30-11:45, 김동수 교수님
예전에 1학점 특강으로 잠깐 개설된 적이 있던 주제인데 이번에 처음 3학점 특강 과목으로 개설되었습니다. 학부 고년차나 대학원생의 경우 학부때 배우는 복소 과목이 어떻게 조합론에서 쓰일 수 있나 알아보는 기회가 되겠습니다. 특히 어떤 조합적 대상의 수를 asymptotic하게 새는 도구들을 배우게 된다고 보시면 됩니다. 과목을 마치게 되면 생성함수를 잘 다루게 될 것이고, 생성함수를 복소평면 위에서의 함수로 이해한 다음 singular point들을 찾아서 분석하는 기술을 습득하게 될 겁니다. 그 외에 다른 재미있는 주제가 있을 것 같습니다.
The Theory of Computation provides a sound logical foundation to computer science. By comparing various formal models of computation with respect to their capabilities, it identifies both fundamental features and ultimate limitations of contemporary digital computing machinery. Rigorous notions of efficiency are captured by famous complexity classes such as P and PSPACE; and concepts like oracles or polynomial-time reduction permit to compare computational problems with respect to their algorithmic cost: NP-hardness results thus serve as ‘beacons’ of intractability.
EE412 빅데이터 분석 개론 (신진우 교수님)
EE488A 머신러닝 소개 (유창동 교수님), EE488B 딥러닝과 알파고 (정세영 교수님), CS492E 기계학습입문 (양은호 교수님): 전기전자 및 전산학부 과목인데, 비슷한 주제로 세 과목이 열리네요.
EE817 Network Science (박홍식 교수님):
In the first half we deal with fundamental network and graph theory and then study generation, characteristics and analysis of various types of networks such as regular, random, small-world, and scale-free network. In the second half, we study dynamic processes on networks including phase transition, resilience, synchronization, epidemic spreading and information spreading in social networks.
MAS711 암호 및 부호이론 (한상근 교수님)
EE623 정보이론 (정혜원 교수님):
This course is a graduate-level introduction to information theory. Information theory is one of the most elegant mathematical theories, with a direct and significant impact to our lives in the information age. In this class, we will learn how to model the information transmission/processing system, with applications of data science as well as communications, and analyze the model from information-theoretical perspectives to derive fundamental limits on what is possible on the system.
전산학부의 기본 과목 중 관련 과목: CS204 이산구조, CS300 알고리듬 개론
최적화 관련 산업및 시스템 공학과 교과목들: IE539 컨벡스 최적화 (김우창 교수님), IE631 정수계획법 (박성수 교수님)
This post will give an incomplete list of theorems covered in MAS575 Combinatorics Fall 2017. This post will be continuously updated throughout this semester. (Last update: April 5, 2017.)
2017년 봄학기 MAS575 조합론 과목에서 다룬 정리들을 정리하였습니다. 빠진 것도 있습니다. 강의가 진행되면서 내용을 업데이트 하겠습니다.
Graham and Pollak (1971). Proof by Tverberg (1982)
The edge set of the complete graph cannot be partitioned into less than copies of the edge sets of complete bipartite subgraphs.
Lindström and Smet (1970).
Let . Then there exist subsets and of such that
Lindström (1993)
Let . Then there exist subsets and of such that , , and
Larman, Rogers, and Seidel (1977) [New in 2017]
Every two-distance set in has at most points. (A set of points is a two-distance set if the set of distances between distinct points has at most two values.)
Blokhuis (1984) [New in 2017]
Every two-distance set in has at most points.
Erdős (1963)
Let be the list of clubs and each club has at least members. If , then such an assignment of students into two lecture halls is always possible.
Erdős, Ko, and Rado (1961). Proof by Katona (1972)
Let . Let be a -uniform intersecting family of subsets of an -set. Then
Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948)
Let be a positive integer. Let be a family on an -set such that whenever and . Then .
Corollary due to de Brujin and Erdős (1948): Suppose that points are given on the plane so that not all are on one line. Then there are at least distinct lines through at least two of the points.
Frankl and Wilson (1981). Proof by Babai (1988).
If a family of subsets of is -intersecting and , then
Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991).
If a family of subsets of is uniform -intersecting and , then (A family of sets is \emph{uniform} if all members have the same size.)
Deza, Frankl, and Singhi (1983)
Let be a prime. Let and .If
(i) for all ,
(ii) for all , ,
then
Alon, Babai, and Suzuki (1991)
Let be a prime. Let be an integer. Let and . Assume . If
(i) for all ,
(ii) for all , ,
then
Grolmusz and Sudakov (2002) [New in 2017]
Let be a prime. Let with and . Let be a family of subsets of such that
(i) for all and
(ii) for every collection of distinct members of .
Then
Grolmusz and Sudakov (2002) [New in 2017]
Let and . Let be a family of subsets of such that for every collection of distinct members of . Then
Sperner (1928)
If is an antichain of subsets of an -set, then
Lubell (1966), Yamamoto (1954), Meschalkin (1963)
If is an antichain of subsets of an -element set, then
Bollobás (1965)
Let , , , , , , , be subsets on an -set such that
(a) for all ,
(b) for all .
Then
Bollobás (1965), extending Erdős, Hajnal, and Moon (1964)
If each family of at most edges of an -uniform hypergraph can be covered by vertices, then all edges can also be covered by vertices.
Lovász (1977)
Let , , , , , , , be subsets such that and for all and
(a) for all ,
(b) for all .
Then .
Let be a vector space over a field . Let be subspaces of such that and for each and
(a) for ;
(b) for .
Then .
Füredi (1984)
Let be subspaces of a vector space over a field . If , for all and for some ,
(a) for all ,
(b) for all ,
then .
Frankl and Wilson (1981)
The chromatic number of the unit distance graph of is larger than for sufficiently large .
Kahn and Kalai (1993)
(Borsuk’s conjecture is false) Let be the minimum number such that every set of diameter in can be partitioned into sets of smaller diameter. Then for large .
Mehlhorn and Schmidt (1982) [New in 2017]
For a matrix C, . (Let be the minimum number of rounds in order to partition into almost homogeneous matrices, if in each round we can split each of the current submatrices into two either vertically or horizontally. This is a parameter related to the communication complexity.)
Lovász and Saks (1993)
.
?
There exists a randomized protocol to decide the equality of two strings of length using bits.
The probablity of outputting an incorrect answer is less than .
Dvir (2009) [New in 2017]
Let be a polynomial of degree at most over a finite field with elements. Let be a Kakeya set. If for all , then is a zero polynomial.
If is a Kakeya set, then
Ellenberg and Gijswijt (2017) [New in 2017]
If is a subset of with no three-term arithmetic progression, then where Furthermore .
Tao (2016) [New in 2017]
Let and let be a finite set and be a field. Let be a function such that if , then . Then the slice rank of is equal to .
Erdős and Rado (1960) [New in 2017]
There is a function on positive integers and such that every family of -sets with more than members contains a sunflower of size .
Naslund and Sawin (2016) [New in 2017]
Let be a family of subsets of having no sunflower of size . Then
Alon and Tarsi (1992)
Let be a field and let . Suppose that and the coefficient of is nonzero. Let be subsets of such that . Then there exist , , , such that
Cauchy (1813), Davenport (1935)
Let be a prime and let be two nonempty subsets of . Then
Dias da Silva and Hamidoune (1994). A proof by Alon, Nathanson, and Ruzsa (1995). Conjecture of Erdős and Heilbronn (1964).
Let be a prime and be a nonempty subset of . Then
Alon (2000) [New in 2017]
Let be an odd prime. For and every integers , if are distinct, then there exists a permutation of such that the sums are distinct.
Alon? [New in 2017]
If is an matrix over a field , and , then for every family of sets , , , of size each, there is a vector such that for all .
Alon? [New in 2017]
Let be a bipartite graph with the bipartition , with . Let . If has at least one perfect matching, then for every integer , there exists a subset of such that for each , the number of neighbors of in is not .
Erdős, Ginzburg, and Ziv (1961) [New in 2017]
Let be a prime. Every sequence of integers contains a subsequence , , , such that .
Alon, Friedland, and Kalai (1984) [New in 2017]
Every (multi)graph with average degree and maximum degree contains a -regular subgraph.
?
Let be an undirected graph. Let . Then there is an orientation of such that the outdegree of each vertex is at most .
2년~3년 정도 주기로 열리고 있는 과목입니다. 국내에서는 KAIST에서만 볼 수 있는 과목으로 이산기하 전공하신 교수님으로부터 잘 배울 수 있습니다. 흥미로운 증명과 주제들이 많습니다. 마지막으로 열린 것은 2014년 봄입니다. 특별한 선수과목은 없지만 이산수학을 들어두었으면 수학적 내공이 충분하지 않을까 생각됩니다.
강의 설명:This course is an introduction to discrete geometry. We will cover basic results from packing and covering, convex polytopes, intersection patterns of convex sets, and combinatorial geometry. Our goal is to reach some key results by combining methods from linear algebra, topology, and probability. However, since this is an introductory course, all necessary notions will be introduced. The main prerequisite for this course is a basic understanding of elementary discrete mathemtaics and the n-dimensional Euclidean space.
교재: Jiří Matoušek, Lectures on Discrete Geometry (Springer, GTM 212). http://link.springer.com/book/10.1007%2F978-1-4613-0039-7
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
교재: Chris Godsil, Gordon Royle, Algebraic Graph Theory, Sringer, GTM 207. http://link.springer.com/book/10.1007/978-1-4613-0163-9
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
KAIST에서는 적어도 최근 10년간은 열린 적이 없는 과목이고 앞으로도 언제 다시 열릴지 알 수 없는 과목입니다. Algebraic Graph Theory를 전공하였고 교재의 저자인 Chris Godsil 교수로부터 박사학위를 받은 Brendan Rooney 교수님이 강의하실 예정이라 기대가 됩니다.
중요한 선수과목은 선형대수학개론 혹은 선형대수학입니다. 행렬의 eigenvalue 관련된 내용을 숙지하고 spectral decomposition 같은 것들도 잘 알고 있으면 좋습니다.
MAS575 Combinatorics (조합수학), 화목 10:30~12:00, 엄상일.
주교재: S. Jukna, Extremal Combinatorics, Springer-Verlag http://link.springer.com/book/10.1007%2F978-3-642-17364-6
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
여러 기술들이 조합수학의 정리를 증명하는데 어떻게 활용되는지 다양하게 살펴봅니다. 선형대수 활용하는 방법, 다항식의 성질을 활용하는 방법, 램지 정리 관련, 확률을 활용하는 방법 등 다양한 주제를 다룹니다. 이산수학, 선형대수학개론을 수강한 학생이 듣는 것이 좋으며 가을마다 열리는 그래프이론개론을 수강했었다면 좀더 수월할 수도 있지만 내용은 독립적입니다.
2년마다 한 번씩 봄에 열리며, 학부생이나 대학원생 모두 수강 가능합니다.
MAS583C 수학특론 Parameterized Algorithms and Lower Bounds (매개변수 고정 알고리즘과 하한), 수 16:00~17:30, 금 10:30~12:00, Helmut Alt 교수 및 Otfried Cheong 교수
전산학과 CS700과 교차개설된 과목입니다. 강의실도 전산학부 건물에서 열립니다. 독일 베를린자유대학 Helmut Alt 교수님이 KAIST 오셔서 강의하십니다.
비슷한 과목은 2014년 봄에 수리과학과에서 제가 MAS583B Fixed-Parameter Algorithms라는 제목으로 연 적이 있습니다. 내용은 비슷하지 않을까 생각합니다. 그래프이론과도 관련이 많고 제 연구와도 관련이 많습니다.
교재: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer. http://link.springer.com/book/10.1007/978-3-319-21275-3
KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.