CS477 Fall 2014

News

• 2014/12/31: Solution to HW12 is available -- just in case some of you want the solutions to prepare for the exam early. You may choose to look at it any time; and you are welcome to send your work to me as usual. And happy new year!
• 2014/12/24: HW11 posted; and merry Christmas.
• 2014/11/26: HW9 is here and happy Thanksgiving.
• 2014/10/31: HW6 solution posted; and happy Halloween.

Lectures and Notes

讲义： Fall 2014 version.

1. Lecture 1, 2014/09/17 Introduction; Hall's theorem, applications and variants;
2. Lecture 2, 2014/09/24 Sets and subsets; combinatorial numbers; combinatorial proofs; Lucas theorem; Dilworth theorem;
3. Lecture 3, 2014/10/08 The principle of inclusion-exclusion, applications; Stirling numbers;
4. Lecture 4, 2014/10/15 Mobius function on posets, and Mobius inversion;
5. Lecture 5, 2014/10/22 Mobius inversion and counting the number of irriducible polynomials; Potential function method; graphs -- definitions, examples, Hamiltonicity, isomorphisms, automorphisms.
6. Lecture 6, 2014/10/29 Chromatic polynomial; pigeonhole principle; Ramsey theorem on graphs; hypergraphs; the Ramsey theorem.
7. Lecture 7, 2014/11/12 Ramsey theory, its proof and applications; the happy ending problem.
8. Lecture 8, 2014/11/19 The basic probabilistic method; linearity of expectations; alteration.
9. Lecture 9, 2014/11/26 Graphs with large girth and large chromatic number; property B, lower bounds and upper bounds.
10. Lecture 10, 2014/12/03 Property B, re-colouring; independence; Lovasz local lemma.
11. Lecture 11, 2014/12/17 Lovasz local lemma -- proof and applications; planar graphs and crossing lemma.
12. Lecture 12, 2014/12/24 Crossing lemma applied to unit distances; Sperner theorem; Erdos-Ko-rado theorem; Sylvester-Gallai theorem; De Bruijn-Erdos theorem.
13. Lecture 13, 2014/12/26 Linear algebra methods in combinatorics; rank, dimension, triangular criterion, spectrum of graphs.
14. Lecture 14, 2014/12/31 Hoffman-Singleton theorem; Turan's theorem; Szemeredi regularity lemma.

Office Hour

每周三课后12点到1点30，逸夫楼312，俞老师办公室。

Homework

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.

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 (expanded) (tex file). Solution to Homework10 (expanded)
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.

Contact

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

杨宽　peanutyk [at] gmail [dot] com