Combinatorics (Fall 2010): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
(37 intermediate revisions by the same user not shown) | |||
Line 52: | Line 52: | ||
= Announcement = | = Announcement = | ||
* | * (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) 第二课的lecture notes和slides中有个错误, | |||
:<math>|U|-\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|</math> 的正负号有误,应为 <math>|U|+\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|</math> 或 <math>|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 = | = Course info = | ||
* '''Instructor ''': | * '''Instructor ''': 尹一通 | ||
:*email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn | :*email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn | ||
:*office: MMW 406. | :*office: MMW 406. | ||
* '''Teaching fellow''': 林木丰 | |||
:*email: forest.sky.sea@gmail.com | |||
* '''Class meeting''': 10am-12 am, Friday; 馆I-105. | * '''Class meeting''': 10am-12 am, Friday; 馆I-105. | ||
* '''Office hour''': 2-5pm, Saturday; MMW 406. | * '''Office hour''': 2-5pm, Saturday; MMW 406. | ||
Line 75: | Line 85: | ||
= Assignments = | = Assignments = | ||
* | * (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 = | ||
A tentative list of topics: | A tentative list of topics: | ||
# [[Combinatorics (Fall 2010)/Basic enumeration|Basic enumeration]] | # [[Combinatorics (Fall 2010)/Basic enumeration|Basic enumeration]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb1.pdf slides] | ||
# [[Combinatorics (Fall 2010)/ | # [[Combinatorics (Fall 2010)/Partitions, sieve methods|Partitions, Sieve methods]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb2.pdf slides] | ||
# [[Combinatorics (Fall 2010)/ | # [[Combinatorics (Fall 2010)/Generating functions|Generating functions]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb3.pdf slides] | ||
# [[Combinatorics (Fall 2010)/ | # [[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 96: | Line 109: | ||
# The Szemeredi regularity lemma | # The Szemeredi regularity lemma | ||
# Sum-product theorems, Kakeya set | # Sum-product theorems, Kakeya set | ||
= Concepts = | |||
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient] | |||
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number] | |||
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset_coefficient#Multiset_coefficients <math>k</math>-multisets on a set] | |||
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind] | |||
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number] | |||
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way] | |||
* [http://en.wikipedia.org/wiki/Partition_(number_theory)#Ferrers_diagram Ferrers diagram] (and the MathWorld [http://mathworld.wolfram.com/FerrersDiagram.html link]) | |||
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method]) | |||
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages] | |||
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series] | |||
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number] | |||
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula] | |||
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number] | |||
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma] | |||
* [http://en.wikipedia.org/wiki/Cayley's_formula Cayley's formula] | |||
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle] | |||
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres 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/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
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]