图论与组合 (Fall 2012)

Table of Contents

News

  • 2013/01/06: 讲义里和考试相关部分的tex：(下载)。again, the level of the exam problems are similar to the homeworks, though the last problems in the last two hws were clearly harder than the exams will be.
  • 2012/12/28: Hw14 solution posted.
  • 2012/12/26: Hw13 solution posted. I did this in a hurry, let me know if there is any problem.
  • 2012/12/19: Merry Christmas, Happy New Year, and Happy every other days, including 12/21 and 1/8.
  • 2012/12/12: 考试时间：1月8日，第18周周二下午2:00-5:00，考试地点：东下院102。范围：笔记上的p46至p100。考试可带笔、两个page的A4 cheat sheet、没有计算能力的水和食物。
  • 2012/12/19: 笔记现在是完整的，包括去年的内容。
  • 2012/12/12: An article about Vasek Chvatal。
  • 2012/12/05: Hw12,Due 12/12/12 12:12。
  • 2012/11/28: 我的gmail不是很高兴，作业cc到xmchen@cs.sjtu.edu.cn可能好些。

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/07 the basic probabilistic method; lower bound on Ramsey numbers.
  11. Lecture 11, 2012/11/12 alterations; Erdos' proof on graphs with large girth and high chromatic number.
  12. Lecture 12, 2012/11/14 Property B, lower bounds and upper bounds.
  13. Lecture 13, 2012/11/21 independence of events, Lovasz local lemma.
  14. Lecture 14, 2012/11/26 proof of Lovasz local lemma; applications, property B, and directed cycles.
  15. Lecture 15, 2012/11/28 bipartite matching, theorems of Konig, Hall, Dilworth.
  16. Lecture 16, 2012/12/05 Dilworth, Sperner, Erdos-Ko-Rado.
  17. Lecture 17, 2012/12/10 problems in combinatorial geometry. Erdos-Szekeres theorem lower and upper bounds; crossing lemma.
  18. Lecture 18, 2012/12/12 unit distance graph; Sylvester-Gallai theorem; De Bruijn-Erdos theorem.
  19. Lecture 19, 2012/12/14 algebraic methods. odd town and even town; non-uniform Fisher's inequality; Graham-Pollak theorem; two distance sets; Frankl-Wilson theorem.
  20. Lecture 20, 2012/12/17 spectrum of graphs. Erdos-Renyi-Sos theorem; Hoffman-Singleton theorem.
  21. Lecture 21, 2012/12/19 polynomial methods. cover points in 3d; Cauchy-Davenport theorem; Erdos-Ginzberg-Ziv theorem.

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 : (tex) - (ps) - (pdf)
  9. Homework9 : (tex) - (ps) - (pdf)
  10. Homework10 : (tex) - (ps) - (pdf)
  11. Homework11 : (tex) - (ps) - (pdf)
  12. Homework12 : Due 2012/12/12 12:12 (tex) - (ps) - (pdf)
  13. Homework13 : with solutions (tex) - (pdf)
  14. Homework14 : with solutions (tex) - (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
  • A short article on Vasek Chvatal.

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 and my poor English skill.

个人工具