图论与组合 (Fall 2011)

Table of Contents

News

  • 2011/10/19: 更新课程提纲文件。包括下次要讲的两个证明（Ramsey theorem and Erdos-Szekeres theorem）。
  • 2011/10/12: 期中考试日期：10/26周三课上。
  • 2011/10/12: Hw4纠正了几个错误；澄清了几个模糊的地方；增加了最后一小题。
  • 2011/10/10: Hw4，下周三（10/19）交。

Lecture Notes

下面是简要的课堂内容提纲。文件在每节课后更新。 希望大家积极提供反馈，补充和指正。

(ps) - (pdf)

  1. Lecture 1, 2011/09/07 Basic counting, binomial numbers.
  2. Lecture 2, 2011/09/14 Combinatorial proofs, Catalan numbers.
  3. Lecture 3, 2011/09/21 Principle of Inclusion-Exclusion, Mobius inversion.
  4. Lecture 4, 2011/09/26 Mobius inversion on numbers, and a little preview of incidence algebra.
  5. Lecture 5, 2011/09/28 Stirling numbers.
  6. Lecture 6, 2011/10/10 Basic concepts in graphs.

Homework

作业一般在周三的课前交。也可以将ps或pdf文件email给我。

  1. Homework1 : (tex) - (ps) - (pdf)
  2. Homework2 : (tex) - (ps) - (pdf)
  3. Homework3 : (tex) - (ps) - (pdf)
  4. Homework4 截止2011/10/19 10am : (tex) - (ps) - (pdf)

Course Description

Description: This course serves as a broad exploration in the field of combinatorics, with a focus on the topics in or related to the theory of graphs and hyper-graphs. The course stars with the basic enumerative combinatorics, including combinatorial proofs in counting, the inclusion-exclusion principle and Mobius inversion, recursion and generating functions. Then we will discuss many interesting topics and techniques, including Ramsey theorems, extremal graph theory, conbinatorial designs, combinatorial geometry, graph matching, connectivity, planarity, and colouring, random graphs, Szemeredi's regularity lemma, the probabilistic method, and the algebraic method. We will adore the legendary Erdos and his co-authors, and attack open problems. The course will be self-contained. The students are assumed to have the basic ability in problem solving.

Textbook(s)

教科书：

  • J.H. van Lint and R. M. Wilson: A Course in Combinatorics (2nd ed). Combridge University Press, 2001.

推荐读物：

  • B. Bollobas: Combinatorics. Combridge University Press, 1986.
  • R. Stanley: Enumerative Combinatorics Vol 1, Combridge University Press, 2000.
  • H. Wilf: Generatingfunctionology, A K Peters, 2006. (Also available online)

Contact

陈晓敏 gougle [at] gmail [dot] com

个人工具