Lecture Series
Lecture 1. Introduction to the Probabilistic Method
이 강의는 확률을 이용해 어떤 수학적 대상의 존재를 증명하는 방법을 소개합니다. 먼저 무작위 선택을 했을 때 원하는 경우가 조금이라도 생기면, 그런 대상이 실제로 존재한다고 볼 수 있다는 생각을 설명합니다. 이를 위해 확률변수, 기댓값, indicator random variable 같은 기본 도구를 배웁니다. 마지막에는 이 방법이 여러 조합론 문제에 어떻게 쓰이는지도 함께 살펴봅니다.
Lecture 2. Deletion Method and the Second Moment Idea
이 강의에서는 처음부터 완벽한 구조를 찾지 못하더라도, 나쁜 부분을 조금 없애면 원하는 대상을 얻을 수 있다는 생각을 배웁니다. 이를 deletion method라고 하며, Markov 부등식을 통해 나쁜 경우가 아주 많지 않다는 점을 설명합니다. 또 서로 함께 가지기 어려워 보이는 성질을 동시에 만족하는 그래프가 존재할 수 있음을 보여 줍니다. 끝으로는 기댓값만이 아니라 분산까지 함께 보는 second moment method의 필요성을 소개합니다.
Lecture 3. Thresholds in Random Graphs and the Lovász Local Lemma
이 강의는 random graph 안에서 어떤 구조가 언제 나타나기 시작하는지를 다룹니다. 예를 들어 삼각형 같은 부분그래프가 어느 순간 갑자기 생기기 시작하는 현상을 통해 threshold의 개념을 설명합니다. 또한 그래프 전체뿐 아니라 그 안의 더 조밀한 부분이 중요한 역할을 할 수 있음을 배웁니다. 마지막에는 사건들이 완전히 독립이 아니어도 사용할 수 있는 Lovász Local Lemma를 소개합니다.
Lecture 4. Concentration Inequalities and Martingales
이 강의는 확률변수가 평균값 근처에 얼마나 강하게 모이는지를 설명합니다. 먼저 Chernoff bound를 이용해 독립인 경우에는 평균에서 크게 벗어날 확률이 매우 작아진다는 사실을 배웁니다. 이를 random graph의 차수 같은 예제에 적용하여 실제 값이 기대값 근처에 집중된다는 점을 확인합니다. 이어서 martingale과 Azuma–Hoeffding inequality를 통해, 완전한 독립이 없는 경우에도 비슷한 결과를 얻는 방법을 소개합니다.
✅ 수강 전 권장 선수 과목
본 강의의 원활한 이해를 위해 아래 과목에 대한 (학부 수준의) 기초 지식이 필요합니다.
이산수학 (또는 조합 및 그래프)
확률 및 통계 (또는 확률론)
선형대수 1