Combinatorics (Fall 2010): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>WikiSysop
imported>WikiSysop
 
(175 intermediate revisions by the same user not shown)
Line 6: Line 6:
|titlestyle  =  
|titlestyle  =  


|image        =  
|image        = [[File:LW-combinatorics.jpeg|border|100px]]
|imagestyle  =  
|imagestyle  =  
|caption      =  
|caption      =  
Line 31: Line 31:
|header6 =
|header6 =
|label6  = Class meetings
|label6  = Class meetings
|data6  = TBA
|data6  = 10am -12am, Friday, <br>馆I-105
|header7 =
|header7 =
|label7  = Place
|label7  = Place
Line 43: Line 43:
|header10 =
|header10 =
|label10  =  
|label10  =  
|data10  = TBA
|data10  = ''van Lint and Wilson,'' <br> A course in Combinatorics, 2nd Ed, <br> Cambridge Univ Press, 2001.


|belowstyle = background:#ddf;
|belowstyle = background:#ddf;
Line 51: Line 51:
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.  
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) 第二次作业答案公布。


= Announcement =  
:[[Combinatorics (Fall 2010)/Announcement|(''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 =
= Syllabus =


=== 先修课程 Prerequisites ===
=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics），概率论（Probability Theory），线性代数（Linear Algebra）
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）


=== Course materials ===
=== Course materials ===
Line 66: Line 88:


= Assignments =
= Assignments =
* (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/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/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>


= Lecture Notes =
= Lecture Notes =
The followings are the topics that I plan to cover:
# [[Combinatorics (Fall 2010)/Basic enumeration|Basic enumeration]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb1.pdf slides]
# Basic enumeration
# [[Combinatorics (Fall 2010)/Partitions, sieve methods|Partitions, Sieve methods]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb2.pdf slides]
# Permutations and sieves
# [[Combinatorics (Fall 2010)/Generating functions|Generating functions]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb3.pdf slides]
# Generating functions
# [[Combinatorics (Fall 2010)/Existence, the probabilistic method|Existence, the probabilistic method]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb4.pdf slides]
# The probabilistic method  
# [[Combinatorics (Fall 2010)/Random graphs| Random graphs]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb5.pdf slides]
# Random graphs
# [[Combinatorics (Fall 2010)/Extremal graphs| Extremal graphs]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb6.pdf slides]
# Extremal graph theory
# [[Combinatorics (Fall 2010)/Finite set systems|Finite set systems]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb7.pdf slides]
# Finite set systems
# [[Combinatorics (Fall 2010)/Extremal set theory|Extremal set theory]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb8.pdf slides]
# Extremal set theory
# [[Combinatorics (Fall 2010)/Extremal set theory II|Extremal set theory II]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb9.pdf slides]
# Ramsey theory
# [[Combinatorics (Fall 2010)/Ramsey theory|Ramsey theory]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb10.pdf slides]
# Optimization
# [[Combinatorics (Fall 2010)/Optimization|Optimization]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb11.pdf slides]
# Duality
# Guest lecture by [http://math.nju.edu.cn/~zwsun/ Professor Zhi-Wei Sun]
# Flow and matching
# [[Combinatorics (Fall 2010)/Flow and matching | Flow and matching]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb13.pdf slides]
# Matroid
# [[Combinatorics (Fall 2010)/Duality, Matroid|Duality, Matroid]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb14.pdf slides]
# Spectra of graphs
# [[Combinatorics (Fall 2010)/Graph spectrum, expanders|Graph spectrum, expanders]]  | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb15.pdf slides]
# Harmonic analysis of boolean functions
# [[Combinatorics (Fall 2010)/The Szemeredi regularity lemma|The Szemeredi regularity lemma]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb16.pdf slides]
# The Szemeredi regularity lemma
 
# 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>]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [http://en.wikipedia.org/wiki/Dirac's_theorem Dirac's theorem]
* [http://en.wikipedia.org/wiki/Hall's_theorem Hall's theorem ] (the marriage theorem)
* [http://en.wikipedia.org/wiki/Birkhoff-Von_Neumann_theorem Birkhoff-Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
* [http://en.wikipedia.org/wiki/Sperner_family Sperner system]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [http://en.wikipedia.org/wiki/VC_dimension VC dimension]
* [http://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[http://en.wikipedia.org/wiki/Van_der_Waerden's_theorem Van der Waerden's theorem]
:*[http://en.wikipedia.org/wiki/Hales-Jewett_theorem Hales–Jewett theorem]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Combinatorial_optimization Combinatorial optimization]
:* [http://en.wikipedia.org/wiki/Optimization_(mathematics) optimization]
:* [http://en.wikipedia.org/wiki/Convex_combination convex combination], [http://en.wikipedia.org/wiki/Convex_set convex set], [http://en.wikipedia.org/wiki/Convex_function convex function]
:* [http://en.wikipedia.org/wiki/Local_optimum local optimum] (see also [http://en.wikipedia.org/wiki/Maxima_and_minima maxima and minima])
* [http://en.wikipedia.org/wiki/Linear_programming Linear programming]
:* [http://en.wikipedia.org/wiki/Linear_inequality linear constraint]
:* [http://en.wikipedia.org/wiki/Hyperplane hyperplane], [http://en.wikipedia.org/wiki/Half_space halfspace], [http://en.wikipedia.org/wiki/Polyhedron polyhedron], [http://en.wikipedia.org/wiki/Convex_polytope convex polytope]
:* [http://en.wikipedia.org/wiki/Simplex_algorithm the Simplex algorithm]
*  The  [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
:* [http://en.wikipedia.org/wiki/Minimum_cut minimum cut]
* [http://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [http://en.wikipedia.org/wiki/Dual_linear_program Duality]
:* [http://en.wikipedia.org/wiki/Linear_programming#Duality LP Duality]
* [http://en.wikipedia.org/wiki/Matroid Matroid]
:* [http://en.wikipedia.org/wiki/Weighted_matroid weighted matroid] and [http://en.wikipedia.org/wiki/Greedy_algorithm greedy algorithm]
:* [http://en.wikipedia.org/wiki/Matroid_intersection Matroid intersection]
* [http://en.wikipedia.org/wiki/Laplacian_matrix Laplacian]
* [http://en.wikipedia.org/wiki/Algebraic_connectivity <math>\lambda_2</math> of a graph] and [http://en.wikipedia.org/wiki/Expander_graph#Cheeger_Inequalities Cheeger Inequalities]
* [http://en.wikipedia.org/wiki/Expander_graph Expander graph]
* [http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma Szemerédi regularity lemma]

Latest revision as of 14:27, 3 September 2011

组合数学 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.
v · d · e

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) 第二次作业答案公布。
(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

Assignments

Lecture Notes

  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 | slides
  11. Optimization | slides
  12. Guest lecture by Professor Zhi-Wei Sun
  13. Flow and matching | slides
  14. Duality, Matroid | slides
  15. Graph spectrum, expanders | slides
  16. The Szemeredi regularity lemma | slides

Concepts

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Combinatorics_(Fall_2010)&oldid=2675"