Combinatorics (Fall 2010)

组合数学 Combinatorics

Instructor
尹一通
Email	yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
office	蒙民伟楼 406
Class
Class meetings	10am -12am, Friday, 馆I-105
Office hours	2pm-5pm, Saturday, MMW 406
Textbook
van Lint and Wilson, A course in Combinatorics, 2nd Ed, Cambridge Univ Press, 2001.

This is the page for the class Combinatorics for the Fall 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

Announcement

• (2010/11/17) 第二次作业答案公布。
• (2010/11/17) 第九次课讲义已补完。
• (2010/11/04) 由于校运动会本科生停课，明天（11月5日）的课暂停。请同学们相互转告。
• (2010/10/26) 第八次课讲义已补完。
• (2010/10/29) 第三次作业已发布，11月12日课上交。

(older announcements...)

Course info

• Instructor : 尹一通

• email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn
• office: MMW 406.

• Teaching fellow: 林木丰

• email: forest.sky.sea@gmail.com

• Class meeting: 10am-12 am, Friday; 馆I-105.
• Office hour: 2-5pm, Saturday; MMW 406.

Syllabus

先修课程 Prerequisites

• 离散数学（Discrete Mathematics）
• 线性代数（Linear Algebra）
• 概率论（Probability Theory）

Course materials

• 教材和参考书清单

Policies

• Policies

Assignments

• (2010/09/17) Problem set 1 due on Sept 25, in class.

• (2010/10/12) Solution

• (2010/10/15) Problem set 2 due on Oct 29, in class.

• (2010/11/13) Solution

• (2010/10/29) Problem set 3 due on Nov 12, in class.
• (2010/11/19) Problem set 4 due on Nov 26, in class.

交作业名单

• (2010/09/27) 第一次交作业名单
• (2010/11/11) 第二次交作业名单

Lecture Notes

A tentative list of topics:

1. Basic enumeration | slides
2. Partitions, Sieve methods | slides
3. Generating functions | slides
4. Existence, the probabilistic method | slides
5. Random graphs | slides
6. Extremal graphs | slides
7. Finite set systems | slides
8. Extremal set theory | slides
9. Extremal set theory II | slides
10. Ramsey theory (under construction...) | slides
11. Optimization
12. Duality
13. Flow and matching
14. Matroid
15. Spectra of graphs
16. Harmonic analysis of boolean functions
17. The Szemeredi regularity lemma
18. Sum-product theorems, Kakeya set

Concepts

• Binomial coefficient
• Composition of a number
• Combinations with repetition, [math]\displaystyle{ k }[/math]-multisets on a set
• Stirling number of the second kind
• Partition of a number
• The twelvefold way
• Ferrers diagram (and the MathWorld link)
• The principle of inclusion-exclusion (and more generally the sieve method)
• Derangement, and Problème des ménages
• Generating function and formal power series
• Fibonacci number
• Newton's formula
• Catalan number
• Double counting and the handshaking lemma
• Cayley's formula
• Pigeonhole principle

• Erdős–Szekeres theorem
• Dirichlet's approximation theorem

• The Probabilistic Method
• Erdős–Rényi model for random graphs
• Graph property
• Some graph parameters: girth [math]\displaystyle{ g(G) }[/math], chromatic number [math]\displaystyle{ \chi(G) }[/math], Independence number [math]\displaystyle{ \alpha(G) }[/math], clique number [math]\displaystyle{ \omega(G) }[/math]
• Extremal graph theory
• Turán's theorem, Turán graph
• Two analytic inequalities:

• Cauchy–Schwarz inequality
• the inequality of arithmetic and geometric means

• Erdős–Stone theorem (fundamental theorem of extremal graph theory)
• Dirac's theorem
• Hall's theorem (the marriage theorem)
• Birkhoff-Von Neumann theorem
• König-Egerváry theorem
• Dilworth's theorem
• Sperner system
• Erdős–Ko–Rado theorem
• VC dimension
• Kruskal–Katona theorem
• Ramsey theory

• Ramsey's theorem
• Happy Ending problem
• Van der Waerden's theorem
• Hales–Jewett theorem

• Lovász local lemma