Combinatorics (Fall 2010): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| (8 intermediate revisions by the same user not shown) | |||
| Line 52: | Line 52: | ||
= Announcement = | = Announcement = | ||
* (2010/09/ | * (2010/10/02) <font color="red" size="3">第四次课讲义已补完, 讲义最后附有参考阅读的章节.</font> | ||
* (2010/09/27) <font color="red" size="3">第一次交作业的名单已公布，见assignment。如果交了作业但没有看到名字，请与我联系。</font> | |||
* (2010/09/24) 提醒：明天（9月25日）上课时交作业。 | |||
* (2010/09/15) 第一次作业已发布，9月25日课上交。 | * (2010/09/15) 第一次作业已发布，9月25日课上交。 | ||
* (2010/09/15) 第二课的lecture notes和slides中有个错误， | * (2010/09/15) 第二课的lecture notes和slides中有个错误， | ||
| Line 83: | Line 85: | ||
= Assignments = | = Assignments = | ||
* (2010/ | * (2010/09/17) [[Combinatorics (Fall 2010)/Problem set 1|Problem set 1]] due on Sept 25, in class. | ||
== 交作业名单 == | |||
* (2010/09/27) [[Combinatorics (Fall 2010)/第一次交作业名单| 第一次交作业名单]] | |||
= Lecture Notes = | = Lecture Notes = | ||
| Line 91: | Line 96: | ||
# [[Combinatorics (Fall 2010)/Generating functions|Generating functions]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb3.pdf slides] | # [[Combinatorics (Fall 2010)/Generating functions|Generating functions]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb3.pdf slides] | ||
# [[Combinatorics (Fall 2010)/Existence, the probabilistic method|Existence, the probabilistic method]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb4.pdf slides] | # [[Combinatorics (Fall 2010)/Existence, the probabilistic method|Existence, the probabilistic method]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb4.pdf slides] | ||
# Random graphs | # [[Combinatorics (Fall 2010)/Random graphs| Random graphs]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb5.pdf slides] | ||
# Extremal graph theory | # Extremal graph theory | ||
# Finite set systems | # Finite set systems | ||
| Line 125: | Line 130: | ||
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem] | :* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem] | ||
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method] | * [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method] | ||
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs] | |||
* [http://en.wikipedia.org/wiki/Graph_property Graph property] | |||
* Some graph parameters: [http://en.wikipedia.org/wiki/Girth_(graph_theory) girth <math>g(G)</math>], [http://mathworld.wolfram.com/ChromaticNumber.html chromatic number <math>\chi(G)</math>], [http://mathworld.wolfram.com/IndependenceNumber.html Independence number <math>\alpha(G)</math>], [http://mathworld.wolfram.com/CliqueNumber.html clique number <math>\omega(G)</math>] | |||
Revision as of 09:39, 8 October 2010
 | |
| 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
- (2010/10/02) 第四次课讲义已补完, 讲义最后附有参考阅读的章节.
- (2010/09/27) 第一次交作业的名单已公布，见assignment。如果交了作业但没有看到名字，请与我联系。
- (2010/09/24) 提醒：明天（9月25日）上课时交作业。
- (2010/09/15) 第一次作业已发布，9月25日课上交。
- (2010/09/15) 第二课的lecture notes和slides中有个错误，
- [math]\displaystyle{ |U|-\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right| }[/math] 的正负号有误，应为 [math]\displaystyle{ |U|+\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right| }[/math] 或 [math]\displaystyle{ |U|-\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right| }[/math]。
- 感谢林文敏同学发现这个错误。
- (2010/09/11) 前两节课slides已上传，在lecture notes的部分有链接。
- 9月3日第一次课。时间：上午三、四节；地点：馆I-105。
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/09/27) 第一次交作业名单
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 graph theory
- Finite set systems
- Extremal set theory
- Ramsey theory
- Optimization
- Duality
- Flow and matching
- Matroid
- Spectra of graphs
- Harmonic analysis of boolean functions
- The Szemeredi regularity lemma
- 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
- 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]