跳转到内容

图论与组合 (Fall 2013)

来自ACM Class Wiki
（重定向自CS477 Fall 2013）

News

  • 2013/12/31: I finished the grading of the final. You may communicate via emails or online chat. I am very impressed by the class' performance in the final. I hope you have enjoyed the course, and Happy New Year!
  • 2013/12/23: HW11, P2: I need to say that these points are in general position, otherwise the statement is not true.
  • 2013/12/23: Solutions to HWs 10, 11, and 12 posted below. I did them in a hurry, please let me know of any problems, and I will update them here. (Also, I am lazy in doing this, but you are encouraged to draw nice pictures in the HW and exam.)
  • 2013/12/23: Where to pay attention to in the Notes: 简要的复习范围
  • 2013/12/19: HW12 below. Do not hand in, solution will be posted here.
  • 2013/12/19: I was sick for a week.. Sorry that I did not grade HW10 in time. I will post here solutions to HW 10, 11, and 12 early next week.
  • 2013/12/13: The exam: 2013/12/30 周一上午8点到11点 东上302.
  • 2013/12/13: HW11 below. Due 12/20.
  • 2013/10/26: Notes are updated with the theorems and proofs on Hamiltonian graphs, and the chromatic polynomial.
  • 2013/09/28: My office hour will be 12:30-2:00 after class, in Prof. Y Yu's office.

Lectures and Notes

讲义： Fall 2013 version

  1. Lecture 1, 2013/09/13 introduction, lines in triple systems, binomial numbers, Lucas' theorem.
  2. Lecture 2, 2013/09/27 binomial identities, Catalan numbers, posets and incidence algebra.
  3. Lecture 3, 2013/09/29 Mobius function and Mobius Inversion on posets, Principle of Inclusion-Exclusion, derangements.
  4. Lecture 4, 2013/10/11 more examples on P.I.E., Mobius Inversion on integers, Stirling numbers.
  5. Lecture 5, 2013/10/18 introduction to graphs.
  6. Lecture 6, 2013/10/25 more on graphs: Hamiltonian graphs, automorphisms, hypercube, colouring and chromatic polynomial. pigeonhole principle.
  7. Lecture 7, 2013/11/08 Ramsey theorem in graphs, related open problems; hypergraphs; Ramsey theorem.
  8. Lecture 8, 2013/11/15 Ramsey theorem, proof and applications; Schur's theorem; happy ending problem.
  9. Lecture 9, 2013/11/22 The probabilistic method: expectations, sum-free sets, lower bound on Ramsey numbers, alteration.
  10. Lecture 10, 2013/11/29 Graphs without small cycles and with large chromatic numbers, property-B lower and upper bounds.
  11. Lecture 11, 2013/12/06 Property-B lower bound, independence, Lovasz Local Lemma and its applications.
  12. Lecture 12, 2013/12/13 One more application of Lovasz Local Lemma, crossing lemma and its application, Sylvester-Gallai theorem and De Bruijn-Erdos theorem.
  13. Lecture 13, 2013/12/20 linear algebra methods, rank argument and some basic spectral graph theory.

Office Hour

每次课后12：30-2：00，在逸夫楼三楼，俞老师办公室。

Homework

Normally HWs are due on Friday before the class. 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 due 2013/09/29 before class.
  2. Homework2 due 2013/10/11 before class. (tex file)
  3. Homework3 due 2013/10/19. (tex file)
  4. Homework4 due 2013/10/25. (tex file) Solution
  5. Homework5 do not hand in. (tex file)
  6. Homework6 due 2013/11/15. (tex file)
  7. Homework7 due 2013/11/22. (tex file)
  8. Homework8 due 2013/11/29. (tex file)
  9. Homework9 due 2013/12/06. (tex file)
  10. Homework10 due 2013/12/13. (tex file) (Solution)
  11. Homework11 due 2013/12/20. (tex file) (Solution)
  12. Homework12 do not hand in. (Solution)

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

检索自“https://acm.sjtu.edu.cn/w/index.php?title=图论与组合_(Fall_2013)&oldid=881”