Combinatorics (Fall 2010): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 94: | Line 94: | ||
:*(2010/12/23) [[Combinatorics (Fall 2010)/Solution to problem set 4|Solution]] | :*(2010/12/23) [[Combinatorics (Fall 2010)/Solution to problem set 4|Solution]] | ||
* (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/16) (optional) [[Combinatorics (Fall 2010)/Problem set 6|Problem set 6]] the "makeup", due on Dec 31, in class. | |||
== 交作业名单 == | == 交作业名单 == |
Revision as of 15:26, 23 December 2010
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/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) 第二次作业答案公布。
- (2010/11/17) 第九次课讲义已补完。
- (2010/11/04) 由于校运动会本科生停课,明天(11月5日)的课暂停。请同学们相互转告。
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/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/12/23) Solution
- (2010/11/19) Problem set 4
due on Nov 26, in classpostponed: due on Dec 10, in class.
- (2010/12/23) Solution
- (2010/12/16) Problem set 5 due on Dec 24, in class.
- (2010/12/16) (optional) Problem set 6 the "makeup", due on Dec 31, in class.
交作业名单
Lecture Notes
A tentative list of topics:
- 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 (under construction...) | slides
- Optimization | slides
- Guest lecture by Professor Zhi-Wei Sun
- Flow and matching | slides
- Duality, Matroid | slides
- Graph spectrum, expanders
- The Szemeredi regularity lemma
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