Combinatorics (Fall 2010): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 52: | Line 52: | ||
= Announcement = | = Announcement = | ||
* (2011/01/04) | * (2011/01/04) 期末考试：2011年1月10日下午2点至4点，馆I-104。考试形式为闭卷考试。最终成绩由作业成绩和考试成绩共同得出。由于试卷有限，从没有交过作业的人将不具有参加期末考试的资格。 | ||
* (2010/12/31) 选修这门课的研究生：负责教务的老师通知，我只需要将你们的学号和成绩报给她就可以。因此程序上不需要你们做任何事。 | * (2010/12/31) 选修这门课的研究生：负责教务的老师通知，我只需要将你们的学号和成绩报给她就可以。因此程序上不需要你们做任何事。 | ||
* (2010/12/31) | * (2010/12/31) 今天（最后一课）有两位补交第五次作业的同学作业没有写名字，请email告诉我名字学号。 | ||
* (2010/12/24) 前四次作业的交作业名单已公布，请大家注意查看。 | * (2010/12/24) 前四次作业的交作业名单已公布，请大家注意查看。 | ||
* (2010/12/24) 第六次作业已发布，12月31日交。这次作业不是必须。 | * (2010/12/24) 第六次作业已发布，12月31日交。这次作业不是必须。 | ||
| Line 89: | Line 89: | ||
= Assignments = | = Assignments = | ||
* (2010/09/17) [[Combinatorics (Fall 2010)/Problem set 1|Problem set 1]] due on Sept 25, in class. | * (2010/09/17) [[Combinatorics (Fall 2010)/Problem set 1|Problem set 1]] due on Sept 25, in class. | ||
* (2010/10/15) [[Combinatorics (Fall 2010)/Problem set 2|Problem set 2]] due on Oct 29, in class. | * (2010/10/15) [[Combinatorics (Fall 2010)/Problem set 2|Problem set 2]] due on Oct 29, in class. | ||
* (2010/10/29) [[Combinatorics (Fall 2010)/Problem set 3|Problem set 3]] due on Nov 12, in class. | * (2010/10/29) [[Combinatorics (Fall 2010)/Problem set 3|Problem set 3]] due on Nov 12, in class. | ||
* (2010/11/19) [[Combinatorics (Fall 2010)/Problem set 4|Problem set 4]] <STRIKE>due on Nov 26, in class</STRIKE> <font color=red>postponed: due on Dec 10, in class</font>. | * (2010/11/19) [[Combinatorics (Fall 2010)/Problem set 4|Problem set 4]] <STRIKE>due on Nov 26, in class</STRIKE> <font color=red>postponed: due on Dec 10, in class</font>. | ||
* (2010/12/16) [[Combinatorics (Fall 2010)/Problem set 5|Problem set 5]] due on Dec 24, in class. | * (2010/12/16) [[Combinatorics (Fall 2010)/Problem set 5|Problem set 5]] due on Dec 24, in class. | ||
* (2010/12/24) [[Combinatorics (Fall 2010)/Problem set 6|Problem set 6]] the "makeup", due on Dec 31, in class. <font color=red>(optional)</font> | * (2010/12/24) [[Combinatorics (Fall 2010)/Problem set 6|Problem set 6]] the "makeup", due on Dec 31, in class. <font color=red>(optional)</font> | ||
= Lecture Notes = | = Lecture Notes = | ||
Latest revision as of 14:27, 3 September 2011
 | |
| Instructor | |
|---|---|
| 尹一通 | |
| 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
- (2011/01/04) 期末考试：2011年1月10日下午2点至4点，馆I-104。考试形式为闭卷考试。最终成绩由作业成绩和考试成绩共同得出。由于试卷有限，从没有交过作业的人将不具有参加期末考试的资格。
- (2010/12/31) 选修这门课的研究生：负责教务的老师通知，我只需要将你们的学号和成绩报给她就可以。因此程序上不需要你们做任何事。
- (2010/12/31) 今天（最后一课）有两位补交第五次作业的同学作业没有写名字，请email告诉我名字学号。
- (2010/12/24) 前四次作业的交作业名单已公布，请大家注意查看。
- (2010/12/24) 第六次作业已发布，12月31日交。这次作业不是必须。
- (2010/12/17) 第五次作业已发布。12月24日交，只有一个星期。
- (2010/12/03) There will be a guest lecture by Professor Zhi-Wei Sun on Dec 3's class.
- (2010/11/28) 第四次作业due date推迟至12月10日。
- (2010/11/19) 第四次作业已发布
- (2010/11/17) 第二次作业答案公布。
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
Assignments
- (2010/09/17) Problem set 1 due on Sept 25, in class.
- (2010/10/15) Problem set 2 due on Oct 29, in class.
- (2010/10/29) Problem set 3 due on Nov 12, in class.
- (2010/11/19) Problem set 4
due on Nov 26, in classpostponed: due on Dec 10, in class. - (2010/12/16) Problem set 5 due on Dec 24, in class.
- (2010/12/24) Problem set 6 the "makeup", due on Dec 31, in class. (optional)
Lecture Notes
- Basic enumeration | slides
- Partitions, Sieve methods | slides
- Generating functions | slides
- Existence, the probabilistic method | slides
- Random graphs | slides
- Extremal graphs | slides
- Finite set systems | slides
- Extremal set theory | slides
- Extremal set theory II | slides
- Ramsey theory | slides
- Optimization | slides
- Guest lecture by Professor Zhi-Wei Sun
- Flow and matching | slides
- Duality, Matroid | slides
- Graph spectrum, expanders | slides
- The Szemeredi regularity lemma | slides
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
- 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:
- 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