CS477 Fall 2015

From ACM Class Wiki
Jump to: navigation, search



  • 2016/01/09: About the final. Now you may ask your final exam score via my email below. [Problem 8 was created when I had a conversation with Binyi Chen several months ago. Problem 9 was from my research and the exact same problem appeared as one of the final selection problem for last year's Chinese IMO team. One student in the Chinese team selection exam proved m = 1008, which could get 10 extra points in our exam. Note that, as I know, the highest possible score for this problem alone is more than 100 points.]
  • 2016/01/01: Solution to HW12 posted; and Merry New Year!
  • 2015/12/31: 关于考试:1月7日, 10:30 - 12:30,东中4-301。可以带4张(正反8页)A4的纸和计算器。草稿纸统一提供。
  • 2015/12/24: HW12, solution to HW11, and Happy Christmas!
  • 2015/12/17: HW11 and solution to HW10 posted.
  • 2015/12/12: Solutions to HW8 and HW9 are available.
  • 2015/11/26: HW7 solution below, and Happy Thanksgiving!

Lectures and Notes

讲义: Fall 2014 version.

  1. Lecture 1, 2014/09/14 Introduction; Hall's theorem.
  2. Lecture 2, 2014/09/16 Hall's theorem and variants. Lucas' theorem.
  3. Lecture 3, 2014/09/23 Proof of Lucas' theorem. Posets. Dilworth theorem.
  4. Lecture 4, 2014/09/28 Dilworth from and to Hall. Principle of Inclusion and Exclusion.
  5. Lecture 5, 2014/09/30 Exponential generating functions. P.I.E. applications. Stirling numbers, 1st and 2nd kind.
  6. Lecture 6, 2014/10/12 Post, incidence algebra, and their Mobius function.
  7. Lecture 7, 2014/10/14 Mobius function of the product of posets, Mobius inversion and its applications.
  8. Lecture 8, 2014/10/21 Pigeonhole principle, hypergraphs, and Ramsey principle.
  9. Lecture 9, 2014/10/26 Ramsey, proof and applications.
  10. Lecture 10, 2014/10/28 More applications of Ramsey, the happy ending problem.
  11. Lecture 11, 2014/11/04 I am very sorry.
  12. Lecture 12, 2014/11/09 The probabilistic method; linearity of expectations. Erdos' proof on sum-free subsets; Erdos' simple lower bound on Ramsey numbers.
  13. Lecture 13, 2014/11/18 Simple probabilitic proofs for symmetric and asymmetric Ramsey numbers; alteration for improved bounds.
  14. Lecture 14, 2014/11/23 Alteration. Erdos' proof of the existence of graphs with long girth and big chromatic number. Property-B and its simple bounds.
  15. Lecture 15, 2014/11/25 random construction of upper bound and random colouring and re-colouring for the lower bound for Property-B.
  16. Lecture 16, 2014/12/02 independence, Lovasz Local Lemma.
  17. Lecture 17, 2014/12/07 proof of Lovasz Local Lemma and applications.
  18. Lecture 18, 2014/12/09 combinatorial geometry. Sylvester-Gallai theorem and De Bruijn-Erdos theorem; planar graphs and the crossing lemma.
  19. Lecture 19, 2014/12/16 using Crossing Lemma prove unit distance bound; Five proofs of Sperner's theorem.
  20. Lecture 20, 2014/12/21 Intersecting families, Katona's proof to Erdos-Ko-Rado theorem; linear algebraic proof to De Bruijn-Erdos theorem; odd town and even town.
  21. Lecture 21, 2014/12/23 Partition complete graph into complete bipartite graphs; spectrum of graphs; Erdos-Renyi-Sos theorem and Hoffman-Singleton theorem.
  22. Lecture 22, 2014/12/30 Overview of other problems with algebraic methods; Turan's theorem; a little bit Erdos-Stone; a tiny bit Szemeredi's Regularity Lemma.

Office Hour



Homework is not part of your grade for the course. But you are very welcome to submit your work, as well as any other work / comments / thoughts about our lives, including those related to this course.

You may either submit hard copy of your work, or email to my address below. You are encouraged to write in LaTeX. It might be time consuming in the beginning, but it is fun. You can use either Chinese or English or some Portuguese or some Italian in your homework and exams. The pure reason I don't use Chinese too much in writing is that I am slow at typing.

Due to the restriction of the Wiki, I renamed tex files as txt below.

  1. Homework1 (tex file). Solution to Homework1
  2. Homework2 (tex file). Solution to Homework2
  3. Homework3 (tex file). Solution to Homework3
  4. Homework4 (tex file). Solution to Homework4
  5. Homework5 (tex file). Solution to Homework5
  6. Homework6 (tex file). Solution to Homework6
  7. Homework7 (tex file). Solution to Homework7
  8. Homework8 (tex file). Solution to Homework8
  9. Homework9 (tex file). Solution to Homework9
  10. Homework10 (tex file). Solution to Homework10
  11. Homework11 (tex file). Solution to Homework11
  12. Homework12 (tex file). Solution to Homework12

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). Cambridge University Press, 2001.
  • B. Bollobas: Combinatorics. Cambridge University Press, 1986.
  • R. Stanley: Enumerative Combinatorics Vol 1, Cambridge 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.


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

Personal tools