跳转到内容

CS477 Spring 2016

来自ACM Class Wiki

News

  • 2016/06/19: Solution to Hw10 posted.
  • 2016/06/01: Hw10 posted, likely our last problem set, you can submit it any time (even after the final exam).
  • 2016/05/31: Solutions to Hw8 and HW9 posted.
  • 2016/04/16: Solution to HW7 posted.
  • 2016/04/13: Solution to HW6 posted.

Lectures and Notes

讲义： current version.

  1. Lecture 1, 2016/02/26 Different ways of seeing the same problem; the different portraits of permutations / matchings; several equivalent theorems around Hall's theorem, although some are more specific and some are more general.
  2. Lecture 2, 2016/03/04 Binomial numbers. Binomial identities, the algebraic view, analytical methods, and combinatorial views. Lucas' theorem, proof through an example. Assigning potential function to states of games.
  3. Lecture 3, 2016/03/09 Potential / energy methods (whatever we call it). Examples including various sorting problems, the pebble game, Conway's soldiers, and Mantel's theorem (the special case of Turan's theorem). The principle of inclusion-exclusion and its proof. Derangements.
  4. Lecture 4, 2016/03/11 One more example of the energy function / shifting method -- the parity of triangles containing a point. Examples of P.I.E. Stirling numbers of the 2nd kind and 1st kind, their combinatorial proofs and their algebraic interpretation.
  5. Lecture 5, 2016/03/18 Posets. Dilworth theorem and its proofs. Introducing incidence algebra of the poset.
  6. Lecture 6, 2016/03/23 Mobius function on posets. Mobius Inversion and the derivation of P.I.E. from it.
  7. Lecture 7, 2016/03/25 Mobius function on integers. Examples. Counting the number of irreducible polynomials. Graphs.
  8. Lecture 8, 2016/04/01 More examples on graphs -- Hamiltonian cycles, hypercube, set systems. Principle of inclusion exclusion. Ramsey theorems on graphs.
  9. Lecture 9, 2016/04/06 Hypergraphs. Ramsey theorem on hypergraphs and its applications -- Schur's theorem and Erdős-Szekeres theorem on convex polygons.
  10. Lecture 10, 2016/04/15 Proof of Ramsey theorem. Tighter bounds for Erdős-Szekeres theorem.
  11. Lecture 11, 2016/04/20 The probabilistic method. Erdos' proof of sum-free sets; edge balanced graph partition.
  12. Lecture 12, 2016/04/29 Lower bound on Ramsey numbers; alteration. Chromatic number, independent set, and girth of graphs.
  13. Lecture 13, 2016/05/04 Erdős' proof for graphs with large girth and large chromatic number; hypergraph colouring and property-B.
  14. Lecture 14, 2016/05/06 Bounds for property-B.
  15. Lecture 15, 2016/05/13 More examples with linearity of expectation; independence; Lovasz Local Lemma.
  16. Lecture 16, 2016/05/18 Proof of the Lovasz Local Lemma and applications.
  17. Lecture 17, 2016/05/20 Planar graphs and crossing lemma.
  18. Lecture 18, 2016/05/27 Sylvester Gallai theorem and De Bruijn-Erdős theorem.
  19. Lecture 19, 2016/06/01 Linear algebra methods. Odd town and even town, decomposition of complete graph into complete bipartite graphs.

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 gougle [at] gmail [dot] com. You are encouraged to write in LaTeX. It might be time consuming in the beginning, but it is fun. 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 slow at typing.

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 Here is a paper that solves Problem 7; see my comments about how you can try it in slightly different ways.
  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 (tex file). Solution to Homework10

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.
  • 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 Vasek Chvatal.

Contact

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

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