CS477 Combinatorics (Spring 2018)

星期三 10:00-11:40（单双周）、星期五 14:00-15:40（双周），东中院4-203

News

2018/06/16: Here is your final: Problems (tex file)..
2018/06/04: The12th and final HW posted.
2018/05/24: HW 11 posted.
2018/05/17: HW 10 posted.
2018/05/10: Expanded version of HW 9 is here.
2018/05/03: HW 9 is here. Pay attention to the due date.
2018/04/24: The midterm is here: Midterm (tex file)..
2018/04/19: otto.
2018/04/12: sette.
2018/04/05: sei.
2018/03/28: Fifth.

Lectures and Notes

Lecture 1, 2017/02/28. Appetizers; sets, functions, and binomial numbers.
Lecture 2, 2017/03/07. Lucas theorem and other various binomial tricks.
Lecture 3, 2017/03/09. Combinatorial proofs. Discussions on HW1.
Lecture 4, 2017/03/14. P.I.E. for the pie day. Euler function, derangements, and other examples.
Lecture 5, 2017/03/21. more P.I.E., colouring and chromatic polynomial, permanents, permutations.
Lecture 6, 2017/03/23. HW2 and 3.
Lecture 7, 2017/03/28. permutations and matchings. Hall's theorem.
Lecture 8, 2017/04/04. more applications and equivalent forms of Hall. Posets. Dilworth theorem and its relative.
Lecture 9, 2017/04/08. HW4 and 5. Proofs of Dilworth.
Lecture 10, 2017/04/11. Mobius inversion.
Lecture 11, 2017/04/18. Standard applications of Mobius inversion. Ramsey on graphs.
Lecture 12, 2017/04/25. Ramsey on integers. Striling numbers.
Lecture 13, 2017/05/02. Hypergraph Ramsey. The happy ending problem.
Lecture 14, 2017/05/04. The basic probabilistic method.
Lecture 15, 2017/05/09. Erdos' theorem on sum-free subsets. Erdos' theorem on graphs with large girth and large chromatic number.
Lecture 16, 2017/05/16. Property B.
Lecture 17, 2017/05/18. Property B.
Lecture 18, 2017/05/23. Independence and the local lemma.
Lecture 19, 2017/05/30. Proof and applications of local lemma.
Lecture 20, 2017/06/01. Crossing lemma, the proof

Office Hour

Wed. 12:00-14:00 in classroom or somewhere nearby.

Homework

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 slower in typing Chinese.

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.

And here is something made me laugh quite hard.

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

推荐读物：

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 / Wechat: 1837187082