图论与组合 (Fall 2012)

Table of Contents

News

  • 2012/11/12: Sorry for the late today. Estimating the traffic is NP-hard.
  • 2012/11/12: Hw8的最后一段discussion，没有大问题，我想说的是"If G_{k+1} is k colourable, then G_{k} is k-1 colourable, and so on"，最后说明G_2是1-colourable的，推出矛盾。(Thanks Lu Yifei for clarification.)
  • 2012/11/12: 课上我说的p = Clogn / n，C的确是和k有关系的，尽管还是个常数。见Notes。(Sorry for the mistake and thanks Lin Chengyu for correcting.)
  • 2012/11/12: 更新了讲义。今天的定理的证明应该是严格的。我出$1给挑出毛病的同学。我还说了，路上想的用Expecation证明定理，有人挑出问题的话是$2吧。
  • 2012/11/07: Hw8,下周三课前交。
  • 2012/10/31: 更新了讲义。更多的Ramsey Theory方面的话题见下面推荐读物的Ramsey Theory。van der Waerden定理的证明见A. Y. Khinchin: Three Pearls of Number Theory。

Lecture Notes

本学期的讲义：(ps) - (pdf)

  1. Lecture 1, 2012/09/12 introduction, basic counting, binomial numbers.
  2. Lecture 2, 2012/09/17 Lucas' theorem, combinatorial proofs, incidence algebra on posets.
  3. Lecture 3, 2012/09/19 posets, lattices, Mobius function, and Mobius inversion.
  4. Lecture 4, 2012/09/26 the inclusion-exclusion principle; energy function method.
  5. Lecture 5, 2012/10/10 permanant; classical Mobius inversion on numbers; count the monic irriducible polynomials of degree n; integer patitions.
  6. Lecture 6, 2012/10/15 Euler's pentagonal number theorem; introduction to graphs.
  7. Lecture 7, 2012/10/17 graphs.
  8. Lecture 8, 2012/10/24 pigeonhole principle; Ramsey theorems on graphs; introduction to hypergraphs.
  9. Lecture 9, 2012/10/31 Ramsey theorems and related theorems, Schur's Lemma, Happy ending problem.
  10. Lecture 10, 2012/11/7 The basic probabilistic method; lower bound on Ramsey numbers.

上学年的讲义: (ps) - (pdf)

Homework

  1. Homework1 : (tex) - (ps) - (pdf)
  2. Homework2 : (tex) - (ps) - (pdf)
  3. Homework3 : (tex) - (ps) - (pdf)
  4. Homework4 : (tex) - (ps) - (pdf)
  5. Homework5 : (tex) - (ps) - (pdf)
  6. Homework6 : (tex) - (ps) - (pdf)
  7. Homework7 : (tex) - (ps) - (pdf)
  8. Homework8 : Due 2012/11/14 10a.m. (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 starts 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 hopefully attack open problems. The course will be self-contained. The students are surely assumed to have the basic ability in problem solving.

Textbook(s) and Articles

教科书：

  • 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)
  • R. Graham, B. Rothschild, and J. Spencer: Ramsey Theory (2nd ed). Wiley-Interscience, 1990.
  • N. Alon and J. Spencer: The probabilistic Method (3rd ed). Wiley-Interscience, 2008.
  • A. Bondy and U.S.R. Murty: Graph Theory with Applications. Elsevier Science Ltd/North-Holland, 1976.
  • A. Bondy and U.S.R. Murty: Graph Theory. Springer 2010.
  • B. Bollobas: Modern Graph Theory. Springer, 1998.
  • D. West: Introduction to Graph Theory (2nd ed). Prentice Hall, 2000.
  • M. Aigner, G. Ziegler, and K. Hofmann: Proofs from the BOOK (4th ed). Springer, 2009.
  • Articles about Paul Erdos: http://www.ams.org/notices/199801/comm-erdos.pdf
  • An interview with Endre Szemeredi: http://www.math.toronto.edu/zsuzsi/research/Szemeredi.pdf

Contact

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

金斌 bjin1990+cs477 [at] gmail [got] com

Credits

All the errors and mistakes are due to yours truly and some others.

The homework problems are created by Jin Bin and me.

The midterm exam problems are formed by Shang Jingbo, Jin Bin, and me. As always, I thank Liu Zhiyan, Pang Ruoming, and Wu Xiaoqian for their comments on the problems.

个人工具