图论与组合 (Fall 2011)

Table of Contents

News

  • 2011/12/22: Added some final words at the bottom of this page. Merry Christmas.
  • 2011/12/22: Office Hour 周一晚7到9点在俞老师办公室，需要确认期末考成绩的同学可以来看考卷。我感觉在grading的时候都看得很清楚了，成绩不会有什么变动。
  • 2011/12/22: 请下列同学务必来Office Hour（考卷签名问题）：张舒畅、肖长城、王朝阳、肖涛、孔维昊、寿鹤鸣。
  • 2011/12/22: 期末考试参考答案和简要小结在下面的Exam section。为了确认你的成绩和预期的相符，你可以：(a)写邮件告诉我期末的估算成绩并询问成绩。(b)周一晚上来office hour看考卷。如果周一不方便的话可以email单独约。
  • 2011/12/17: Hw12，文件中加了参考答案。
  • 2011/12/14: Hw11，更新了答案。
  • 2011/11/15: 公布了期中考试的参考答案。
  • 2011/10/20: 添加了和近期课程有关的推荐读物。

Lecture Notes

下面是简要的讲义。希望大家积极提供反馈，补充和指正。

(tex) - (ps) - (pdf)

  1. Lecture 1, 2011/09/07 Basic counting, binomial numbers.
  2. Lecture 2, 2011/09/14 Combinatorial proofs, Catalan numbers.
  3. Lecture 3, 2011/09/21 Principle of Inclusion-Exclusion, Mobius inversion.
  4. Lecture 4, 2011/09/26 Mobius inversion on numbers, and a little preview of incidence algebra.
  5. Lecture 5, 2011/09/28 Stirling numbers.
  6. Lecture 6, 2011/10/10 Basic concepts in graphs.
  7. Lecture 7, 2011/10/12 More basic concepts in graphs.
  8. Lecture 8, 2011/10/19 The pigeon hole principle, the Ramsey principle.
  9. Lecture 9, 2011/10/24 Problems from the homeworks; Hypergraphs, Ramsey theorem, Erdos-Szekeres theorem, and Erdos' theorem on sum-free subsets.
  10. Lecture 10, 2011/11/02 Problems from the homeworks and the midterm; The probabilistic method, linearity of expectation.
  11. Lecture 11, 2011/11/07 Probability methods, alterations. Ramsey numbers. Graphs with big girth and big chromatic number.
  12. Lecture 12, 2011/11/09 Probability methods, property B.
  13. Lecture 13, 2011/11/16 Independent events. The Lovasz local lemma.
  14. Lecture 14, 2011/11/21 Using the Lovasz local lemma. Mantel's theorem, Turan graphs.
  15. Lecture 15, 2011/11/23 Extremal graph theory: Turan's theorem, Hamilton cycles, girth >=5 graphs, Erdos-Stone theorem.
  16. Lecture 16, 2011/11/30 Extremal graph theory: Szemeredi regularity lemma and its applications.
  17. Lecture 17, 2011/12/05 Hall's marriage theorem, Dilworth theorem.
  18. Lecture 18, 2011/12/07 Sperner's theorem, Erdos-Ko-Rado theorem. Basic linear algebraic methods.
  19. Lecture 19, 2011/12/14 More linear algebraic topics. Spectrum of graphs. Lindstrom lemma, Cauchy-Binet formula, and Matrix tree theorem.
  20. Lecture 20, 2011/12/19 Problems in combinatorial geometry.

Homework

  1. Homework1 : (tex) - (ps) - (pdf)
  2. Homework2 : (tex) - (ps) - (pdf)
  3. Homework3 : (tex) - (ps) - (pdf)
  4. Homework4 : (tex) - (ps) - (pdf)
  5. Homework5 : (tex) - (ps) - (pdf)
  6. Homework6 : (tex) - (ps) - (pdf)
  7. Homework7 : (tex) - (ps) - (pdf)
  8. Homework8 : (tex) - (ps) - (pdf)
  9. Homework9 : (tex) - (ps) - (pdf)
  10. Homework10 : (tex) - (ps) - (pdf)
  11. Homework11 with solutions : (tex) - (ps) - (pdf)
  12. Homework12 with solutions : (tex) - (ps) - (pdf)

Exams

Midterm with solutions to section II: (ps) - (pdf)

Final with solutions and remarks: (ps) - (pdf) (I will update this with students' nice solutions and some statistics by Monday.)

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 attack open problems. The course will be self-contained. The students are 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). Combridge University Press, 2001.

推荐读物：

  • B. Bollobas: Combinatorics. Combridge University Press, 1986.
  • R. Stanley: Enumerative Combinatorics Vol 1, Combridge 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

Contact

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

Epilogue

在美国的学校里教过课，也看到过大师们给学校的本科生上数学课，有种奇怪的感觉；每每会想，要是课堂里坐的是中国一流的学生，双方的感觉会是什么样。第一次给三十多个顶尖的学生开一门课，在这里小结一下。

一直在想这门课要达到的目的是什么。对我来说这不是一个很难的问题：如果让我回到十多年前去给自己上课（谢天谢地，还不算太老），会希望上成什么样。我希望至少能让学生学得很愉快，能感觉到学到很多；希望在十多年后回过头想这门课的时候会觉得有趣，还能记得一个大概和某些神奇的手法；对组合数学感兴趣的学生，能把他们的能量激发出来，开始入手一些有份量的open problem；对其他学生，能偷偷把他们变成有兴趣的学生，然后用前面这个case。（开个玩笑，我是坚决反对改变人的基因的。）不管怎样，或许有一天在工作学习中碰到相关的问题，或许闲暇时想到，能有些亲切感。学生整个课程下来，觉得修了一门艺术欣赏课，那是最好。

整个学期我差不多是向这样的目标努力的。不算太成功，遇到的问题不少。我就不一一抱怨了。同学们都很出色，我这方面希望没有占用大家太多的平时休息时间。唯一不足的是在期末考卷上许多应该拿的分没有拿到，觉得我教得不是很成功——就是那些只要在课堂上听懂就应该会做的。第一次教课，没什么好的坏的经验，有不少东西没有表达清楚。课时比较紧，想教的东西太多。组合里有太多有趣的东西，即使只作简单的深入，两个学期的课程也不一定够。我只能按照自己的taste，把我认为最主要的强加给同学们。大家的兴趣各不相同，背景也有许多差别。我说这门课不需要前件课程，但是在大三对一些基础课程良好的掌握会为我们省下不少时间。再说一遍，我的确在按自己觉得最让人舒服的pace来讲这门课；如果觉得这课教得有些魔鬼，那是因为我认为交大最好的学生的pace应该是这样的。

很多年前和老师朋友谈过什么是好的数学。每个人都有自己的答案。我的答案是，那种开始时觉得无法入手，但突然用一个正确的方法去想去看，会觉得原来这么显然。到那个时候，你会很兴奋，因为觉得自己实实在在掌握了一样甜蜜的真理。（这个是不是有些像柏拉图那著名的关于山洞的寓言？）当然感觉是随着积累而变化的。比如第一次作业的最后那题，自己想出一个组合证明是件很了不起的事，但已经很难带来快感，如果你已经很多次看到那样的walk被翻来翻去，剩下的只有技巧。对比最后一次作业的最后那题，如果你第一次那样做题，感觉是到了一个新的世界。可惜还有不少这样的东西没有时间在课上提到。

毕加索：“It takes a long time to become young.” 这差不多是组合数学现在的状态。希望大家学得开心，玩得开心。

最后，有空多交流。圣诞快乐。

个人工具