내 생각엔 조합론은 크게 순수 조합론 / 그래프이론 / 매트로이드 등으로 나뉘는 것 같음.



1) 순수 조합론: Enumeration, Combinatorial Number Theory, Extremal Set Theory, Algebraic Combinatorics 등


1-a) Enumeration: 어떤 조건을 만족하는 대상을 전부 세거나 개수를 추정하는 문제를 다룸. Polya 정리, Burnside 같은 걸 생각하면 됨. 최근에는 많이 안 하는 듯? 


1-b) Combinatorial Number Theory: 정수의 덧셈, 분할 등을 연구함.

개인적으로 조합론보다 수론에 가깝다고 생각하고, 더럽게 어려운 거 말고는 아는 게 별로 없음.


1-c) Extremal Set Theory: 조건을 만족하는 set들로 이루어진 family의 크기, 구조를 연구하는 분야임.

Oddtown-like problem, Union-closed sets, Fisher's inequality 등을 참고하면 좋음.

대수적인 툴을 쓰면 아름답게 풀리는 경우가 많고, 연구도 활발히 진행 중임. Peter Frankl 등이 유명함.


1-d) Algebraic Combinatorics: 대수적인 방법으로 조합론 문제들을 푸는 분야임.

앞서 언급했듯이 Extremal Set Theory의 일부도 걸쳐 있음.

Chevalley-Warning Theorem, Combinatorial Nullstellensatz, Cap-set Problem 등을 다룸.

Erdos–Ginzburg–Ziv Theorem 찾아보면 좋을 듯.

증명에서 Combinatorial Nullstellensatz를 기가 막히게 쓰는데 배울 때 좀 쌌음.


1-e) 그 외: Topological Combinatorics라고 discrete한 대상의 complex를 정의하고 경계 연산을 확장해서 Homology를 연구하는 괴악한 분야도 있음.

요즘 이거 하는데 재미는 있지만 머리가 터질 것 같다...



2) 그래프이론: Extremal Graph Theory, Structural Graph Theory, Probabilistic Graph Theory, 그 외로 나뉨


2-a) Extremal graph theory: 어떤 조건을 만족하는 그래프에서 특정 파라미터(edge 수, chromatic number)의 하한/상한을 구하고 extremal case의 그래프 구조를 연구함.

Turan's Theorem, Erdos-Stone-Simonovits Theorem, Ramsey Theory 참고하면 좋음.

사용하는 툴에 따라 또 나뉘는데, 진짜 그래프 구조만 가지고 추정하는 부류도 있고 edge를 랜덤하게 줘서 Markov 같은 걸로 적당히 bound하는 방법도 있음.

거장으로는 Benny Sudakov, Jacob Fox, Richard Montgomery 등이 있음.


2-b) Structural graph theory: 어떤 구조를 포함하거나 포함하지 않는 그래프의 성질을 연구함.

예를 들면 H-minor를 포함하지 않는 그래프가 좋은 파라미터(Treewidth, Pathwidth)를 가진다던가, 어떤 그래프와 유사하다던가, 특정 방식으로 분해된다던가...

이걸로 Graph Family를 Classification 하기도 함 (Graph Minor Theory)

Extremal쪽에 비해 순수하게 그래프 조작+구조 관찰로만 문제를 푸는 경우가 많음.

유명한 학자로는 Paul Seymour, Maria Chudnovsky 등이 있고 최근에는 Sophie Spirkl도 뜨고 있음.


2-c) Probabilistic Graph Theory: Extremal Graph Theory랑 걸쳐 있어서 하위분야로 넣어야 할지 고민 좀 했는데, 관찰하는 대상의 느낌이 달라서 넣기로 함. 

일단 고정된 그래프를 연구하는 앞선 분야들과 달리 vertex 개수만 정해놓고 edge는 일정 확률로 assign함.

이때 확률 p가 특정 threshold를 넘으면 갑자기 좋은 성질(Hamiltonicity, Large clique) 등이 나타나는 경우가 있음.

그 threshold가 어느 정도인지, Phase transition은 어떻게 일어나는지 등을 연구함.

아마 교수님이 말한 랜덤 그래프는 이쪽일 거임.

개인적으로는 확률론을 '잘' 해야 하고, 랜덤행렬이 나오기 때문에 선형대수도 잘 다루면서 그래프이론도 빠삭해야 해서 어렵다고 생각함.

대신 꾸준히 좋은 결과가 나오고 있고, 다른 분야(특히 Extremal쪽)에 접목해서 성과를 내기도 함.


2-d) 그 외: Topological Graph Theory(Sphere, Torus등의 표면에 그래프를 embedding하는 문제), Spectral Graph Theory(인접행렬의 고윳값과 그래프 구조의 관계), Geometric Graph Theory(교차 금지, 직선 edge만 허용 같은 기하적인 조건이 그래프 구조를 어떻게 제한하는가), Algorithmic Graph Theory(Shortest path 찾기, Proper coloring 찾기) 등등 수많은 하위분야가 있음.


3) 매트로이드: 벡터공간의 기저와 그래프의 독립집합을 추상화한 무언가를 다룸.

사실 매트로이드는 그래프이론에서 매우 잘 써먹는 이론 중 하나임.
그래프를 매트로이드로 변환 -> 조물조물 -> 다시 그래프로 변환하면 좋은 결과가 자주 나옴.
예를 들어 Structural Graph Theory에서 다루는 Graph Minor를 Matroid Minor로 본다던가...
근데 요즘은 매트로이드 자체가 가지는 성질도 잘 연구하는 것 같음.
당장 오늘 세미나 들은 것도, 원래 그래프이론에서 나온 Erdos-Posa Property와 유사한 성질이 매트로이드에서도 관찰된다는 내용이었음.
나도 요즘 공부하는 중인데 배워두면 많이 쓸만할 듯?


쓰다 보니 주절주절 길어진데다 말도 너무 어렵게 썼는데, 설명 필요하면 글 계속 수정함.