CS477 Spring 2020

CS477 Combinatorics (Spring 2019)

We will hold the course online until some magic moment. Now we have the wechat group, which is good. The notes and homeworks will be posted here and on wechat as well.

Lectures and Notes

A sketch of most of the materials: Lecture notes.

Lectures:

1. Lecture 1, 2020/03/04 sets, functions, and the definition of binomial numbers.
2. Lecture 2, 2020/03/11 sets, binomial number basics.
3. Lecture 3, 2020/03/18 binomial numbers, shapes and identities.
4. Lecture 4, 2020/03/25 Lucas theorem; generating functions. Introduction to graphs.
5. Lecture 5, 2020/04/01 graph automorphisms. Gallai's conjecture. Mantel's theorem.
6. Lecture 6, 2020/04/08 proofs of Turan's theorem. Hypercube.
7. Lecture 7, 2020/04/15 hypercube, error correcting codes.
8. Lecture 8, 2020/04/22 permutations.
9. Lecture 9, 2020/04/29 generating random permutations; bipartite matching theorem.
10. Lecture 10, 2020/05/06 bipartite matching theorems; graph Ramsey theorems.
11. Lecture 11, 2020/05/13 Ramsey, lower bound, general form, integer Ramsey type problems.
12. Lecture 12, 2020/05/20 The basic probabilistic method; alterations.
13. Lecture 13, 2020/05/27 Erdos' proof of graphs with large chromatic number and long girth; property B.
14. Lecture 14, 2020/06/03 The crossing lemma.

Office Hour

On wechat, any time.

Homework

You can use either Chinese or English or some Portuguese or some Italian in your homework and exams.

Please submit all homework via email to gougle [at] gmail [dot] com. You are encouraged to write your work in LaTeX and submit the resulting pdf file together with the tex file. Writing in LaTeX might be time consuming in the beginning, but it is nice / useful / fun.

It is also fine to submit any other human readable format of your work, e.g. photos of your writing / sketch / painting.

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

• NOTE: By default, all the problems are due by the next lecture. Problems with a (*) can be handed in anytime during the semester, and any problem with a (+) can be handed in no later than two weeks after the next lecture.

1. Homework 1 (tex file).
2. Homework 2 (tex file).
3. Homework 3 (tex file).
4. Homework 4 (tex file).
5. Homework 5 (tex file).
6. Homework 6 (tex file).
7. Homework 7 (tex file).
8. Homework 8 (tex file).
9. Homework 9 (tex file).
10. Homework 10 (tex file).
11. Homework 11 (tex file).
12. Homework 12 (tex file).
13. Homework 13 (tex file).
14. Homework 14 (tex file) (NOTE: due in two weeks.)

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 Erdős 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

Recommended reading:

We will not stick to a single book. But van Lint and Wilson (the first item below) has most materials we will cover.

• 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.
• M. Aigner: A Course in Enumeration. Springer, 2007.
• Articles about Paul Erdős: 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 Vašek Chvátal.

Contact

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

TA 范裕达 Email: mistergalahad [at] gmail [dot] com