Combinatorics (Fall 2010): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
imported>WikiSysop
 
(108 intermediate revisions by the same user not shown)
Line 52: Line 52:


= Announcement =
= Announcement =
* (2010/10/02) <font color="red" size="3">第四次课讲义已补完, 讲义最后附有参考阅读的章节.</font>
* (2011/01/04) 期末考试：2011年1月10日下午2点至4点，馆I-104。考试形式为闭卷考试。最终成绩由作业成绩和考试成绩共同得出。由于试卷有限，从没有交过作业的人将不具有参加期末考试的资格。
* (2010/09/27) <font color="red" size="3">第一次交作业的名单已公布，见assignment。如果交了作业但没有看到名字，请与我联系。</font>
* (2010/12/31) 选修这门课的研究生：负责教务的老师通知，我只需要将你们的学号和成绩报给她就可以。因此程序上不需要你们做任何事。
* (2010/09/24) 提醒：明天（9月25日）上课时交作业。
* (2010/12/31) 今天（最后一课）有两位补交第五次作业的同学作业没有写名字，请email告诉我名字学号。
* (2010/09/15) 第一次作业已发布，9月25日课上交。
* (2010/12/24) 前四次作业的交作业名单已公布，请大家注意查看。
* (2010/09/15) 第二课的lecture notes和slides中有个错误，
* (2010/12/24) 第六次作业已发布，12月31日交。这次作业不是必须。
:<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/12/17) 第五次作业已发布。12月24日交，只有一个星期。
:感谢林文敏同学发现这个错误。
* (2010/12/03) There will be a guest lecture by Professor Zhi-Wei Sun on Dec 3's class.
* (2010/09/11) 前两节课slides已上传，在lecture notes的部分有链接。
* (2010/11/28) 第四次作业due date推迟至12月10日。
* 9月3日第一次课。时间：上午三、四节；地点：馆I-105。
* (2010/11/19) 第四次作业已发布
* (2010/11/17) 第二次作业答案公布。
 
:[[Combinatorics (Fall 2010)/Announcement|(''older announcements''...)]]


= Course info =
= Course info =
Line 86: 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/29) [[Combinatorics (Fall 2010)/Problem set 3|Problem set 3]] due on Nov 12, in class.
* (2010/09/27) [[Combinatorics (Fall 2010)/第一次交作业名单| 第一次交作业名单]]
* (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 =
A tentative list of topics:
# [[Combinatorics (Fall 2010)/Basic enumeration|Basic enumeration]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb1.pdf slides]
# [[Combinatorics (Fall 2010)/Basic enumeration|Basic enumeration]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb1.pdf slides]
# [[Combinatorics (Fall 2010)/Partitions, sieve methods|Partitions, Sieve methods]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb2.pdf slides]
# [[Combinatorics (Fall 2010)/Partitions, sieve methods|Partitions, Sieve methods]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb2.pdf slides]
Line 97: Line 101:
# [[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]
# [[Combinatorics (Fall 2010)/Random graphs| Random graphs]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb5.pdf slides]
# [[Combinatorics (Fall 2010)/Random graphs| Random graphs]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb5.pdf slides]
# Extremal graph theory
# [[Combinatorics (Fall 2010)/Extremal graphs| Extremal graphs]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb6.pdf slides]
# Finite set systems
# [[Combinatorics (Fall 2010)/Finite set systems|Finite set systems]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb7.pdf slides]
# Extremal set theory
# [[Combinatorics (Fall 2010)/Extremal set theory|Extremal set theory]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb8.pdf slides]
# Ramsey theory
# [[Combinatorics (Fall 2010)/Extremal set theory II|Extremal set theory II]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb9.pdf slides]
# Optimization
# [[Combinatorics (Fall 2010)/Ramsey theory|Ramsey theory]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb10.pdf slides]
# Duality
# [[Combinatorics (Fall 2010)/Optimization|Optimization]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb11.pdf slides]
# Flow and matching
# Guest lecture by [http://math.nju.edu.cn/~zwsun/ Professor Zhi-Wei Sun]
# Matroid
# [[Combinatorics (Fall 2010)/Flow and matching | Flow and matching]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb13.pdf slides]
# Spectra of graphs
# [[Combinatorics (Fall 2010)/Duality, Matroid|Duality, Matroid]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb14.pdf slides]
# Harmonic analysis of boolean functions
# [[Combinatorics (Fall 2010)/Graph spectrum, expanders|Graph spectrum, expanders]]  | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb15.pdf slides]
# The Szemeredi regularity lemma
# [[Combinatorics (Fall 2010)/The Szemeredi regularity lemma|The Szemeredi regularity lemma]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb16.pdf slides]
# Sum-product theorems, Kakeya set


= Concepts =
= Concepts =
Line 133: Line 136:
* [http://en.wikipedia.org/wiki/Graph_property Graph property]
* [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>]
* 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"