图论与组合 (Fall 2011)

Table of Contents

News

  • 2011/12/20: 讲义p38, Fact 7.8 (Markov Ineq.) Fixed typo。
  • 2011/12/19: 更新讲义。加了今天的内容，Fixed前面的一些小typo。
  • 2011/12/17: Hw12，文件中加了参考答案。
  • 2011/12/14: 关于期末考试，在本页的最后。可能会根据同学们的问题不断有所修改和补充。（每次的修改都会在这个News section出现。）
  • 2011/12/14: Hw11，更新了答案。
  • 2011/12/14: 更新了讲义。
  • 2011/11/15: 公布了期中考试的参考答案。
  • 2011/10/20: 添加了和近期课程有关的推荐读物。

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.
  7. Lecture 7, 2011/10/12 More basic concepts in graphs.
  8. Lecture 8, 2011/10/19 The pigeon hole principle, the Ramsey principle.
  9. Lecture 9, 2011/10/24 Problems from the homeworks; Hypergraphs, Ramsey theorem, Erdos-Szekeres theorem, and Erdos' theorem on sum-free subsets.
  10. Lecture 10, 2011/11/02 Problems from the homeworks and the midterm; The probabilistic method, linearity of expectation.
  11. Lecture 11, 2011/11/07 Probability methods, alterations. Ramsey numbers. Graphs with big girth and big chromatic number.
  12. Lecture 12, 2011/11/09 Probability methods, property B.
  13. Lecture 13, 2011/11/16 Independent events. The Lovasz local lemma.
  14. Lecture 14, 2011/11/21 Using the Lovasz local lemma. Mantel's theorem, Turan graphs.
  15. Lecture 15, 2011/11/23 Extremal graph theory: Turan's theorem, Hamilton cycles, girth >=5 graphs, Erdos-Stone theorem.
  16. Lecture 16, 2011/11/30 Extremal graph theory: Szemeredi regularity lemma and its applications.
  17. Lecture 17, 2011/12/05 Hall's marriage theorem, Dilworth theorem.
  18. Lecture 18, 2011/12/07 Sperner's theorem, Erdos-Ko-Rado theorem. Basic linear algebraic methods.
  19. Lecture 19, 2011/12/14 More linear algebraic topics. Spectrum of graphs. Lindstrom lemma, Cauchy-Binet formula, and Matrix tree theorem.
  20. Lecture 20, 2011/12/19 Problems in combinatorial geometry.

Homework

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

  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 : (tex) - (ps) - (pdf)
  9. Homework9 : (tex) - (ps) - (pdf)
  10. Homework10 : (tex) - (ps) - (pdf)
  11. Homework11 with solutions : (tex) - (ps) - (pdf)
  12. Homework12 with solutions : (tex) - (ps) - (pdf)

Exams

Midterm with solutions to section II: (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) 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

Contact

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

About the final exam

考试时间地点：12月21日 周三 上午9:45到12:45 东下院203。

可以带教科书、笔记、作业。不能用电子设备。考卷为英语，用中文答题完全没有问题。

讲义上有不少内容是了解和欣赏性质的，不在考试范围内。这些部分包括：

  • 所有的conjecture和open problem。
  • Thm7.10的证明。
  • Thm7.12的statement。
  • Thm7.13的statement和证明。
  • Lemma8.2（LLL）的证明。
  • Thm9.7的statement。
  • 整个section 10 (Szemeredi Lemma)。
  • Example12.2的证明。
  • Thm12.6的证明。
个人工具