跳转到内容

CS477 Spring 2017

来自ACM Class Wiki

CS477 Combinatorics (Spring 2017)

星期二16:00-17:40(双周)&星期五14:00-15:40下院203（校历：http://www.jwc.sjtu.edu.cn/web/sjtu/198109-1980000005617.htm ）

News

  • 2017/05/26: Hw13 posted, due by 2017/06/11. This is our last homework set.
  • 2017/05/19: Please decide by the next Friday your planned final presentation time slot: .
  • 2017/05/19: Hw12 posted, due by 2017/05/28.
  • 2017/04/22: No new homework this week. Please find a final project topic by 05/05.
  • 2017/04/18: I posted some final project candidates below, we will discuss this in class.

Public Lecture, everyone is welcomed

  • 2017/06/15 12:00 秋闻达, A Note on Ramsey Numbers
  • 2017/06/15 14:00 龙思杉, Counting the Aztec Tilings
  • 2017/06/15 16:00 叶昊然, Combinatorial Nullstellensatz in Graph Colouring

Private Lecture, nobody is welcomed

  • 2017/06/14 14:00 孔冰玉, Lovasz' Solution to Kneser's Conjecture
  • 2017/06/14 16:00 杨卓林, A Counter Example to Borsuk's Conjecture

Lectures and Notes

  1. Lecture 1, 2017/02/24. Brief introduction. Different views of permutations and matchings.
  2. Lecture 2, 2017/02/28. Bipartite matchings. Generating functions.
  3. Lecture 3, 2017/03/03. Generating functions. Binomial numbers / Pascal's triangle.
  4. Lecture 4, 2017/03/10. Binomial numbers, combinatorial proofs, analytic proofs.
  5. Lecture 5, 2017/03/14. Principle of inclusion-exclusion and its applications.
  6. Lecture 6, 2017/03/17. More applications of P.I.E. Stirling numbers.
  7. Lecture 7, 2017/03/24. Stirling numbers.
  8. Lecture 8, 2017/03/28. Posets and Mobius function.
  9. Lecture 9, 2017/03/31. Mobius inversion and applications. Pigeonhole principle.
  10. Lecture 10, 2017/04/07. Ramsey theorem on graphs, general Ramsey theorem.
  11. Lecture 11, 2017/04/11. Ramsey problems on integers. The probabilistic method on the lower bound of the Ramsey number.
  12. Lecture 12, 2017/04/14. Basic probabilistic method.
  13. Lecture 13, 2017/04/21. Homework recitation.
  14. Lecture 14, 2017/04/25. Graphs with long girth and high chromatic number.
  15. Lecture 15, 2017/04/28. Upper bounds and lower bounds of Property-B.
  16. Lecture 16, 2017/05/05. Independence of events. Lovasz local lemma.
  17. Lecture 17, 2017/05/09. Applications of the L.L.L.
  18. Lecture 18, 2017/05/12. Planar graphs, crossing number, and crossing lemma.
  19. Lecture 19, 2017/05/19. Set families. Sperner theorem and Erdos-Ko-Rado theorem.

Reading Projects

  • L. Lovász, "Kneser's conjecture, chromatic number, and homotopy", Journal of Combinatorial Theory, Series A, 25 (3) (1978), 319-324.
  • L. Lovász, "On the Shannon capacity of a graph", IEEE Transactions on Information Theory, 25 (1), (1979), 1-7.
  • M. Ajtai, J. Komlós, E. Szemerédi, "A note on Ramsey numbers", Journal of Combinatorial Theory, Series A, 29 (3) (1980), 354-360.
  • B. Bollobas, A. Thomason, "Threshold functions", Combinatorica, 7 (1987), 35-38.
  • N. Elkies, G. Kuperberg, M. Larsen, J. Propp, "Alternating-sign matrices and domino tilings", PART I, Journal of Algebraic Combinatorics, 1 (2) (1992), 111–132; PART II, Journal of Algebraic Combinatorics, 1 (3) (1992), 219–234.
  • J. Kahn, G. Kalai, "A counter example to Borsuk's conjecture", Bulletin of the AMS 29 (1993), 60-62.
  • N. Alon, "Combinatorial Nullstellensatz", Combinatorics, Probability and Computing, 8 (1-2), (1999), 7-29.
  • A. Schrijver, "A Pythagoras proof of Szemerédi's regularity lemma", https://arxiv.org/abs/1212.3499 (2012).

Office Hour

星期五12:00-14:00下院203

Homework

Each homework problem set has two sections. "Current Problems" are those problems you need to submit by the due date; "Future Problems" are those problems you are encouraged to think about. Especially, the earlier problems in that section are related to the topic we are going to cover in the next one or two lectures.

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.

  1. Homework 0 (tex file).
  2. Homework 1 (tex file).
  3. Homework 2 (tex file).
  4. Homework 3 (tex file).
  5. Homework 4 (tex file).
  6. Homework 5 (tex file).
  7. Homework 6 (tex file).
  8. Homework 7 (tex file).
  9. Homework 8 (tex file).
  10. Homework 9 (tex file).
  11. Homework 10 (tex file).
  12. Homework 11 (tex file).
  13. Homework 12 (tex file).
  14. Homework 13 (tex file).

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

检索自“https://acm.sjtu.edu.cn/w/index.php?title=CS477_Spring_2017&oldid=3346”