Instructor:
Teaching assistants:
Lecture Outline: [All scribed notes below are contributed by Qianfang Zou (×ÞÙ»·¼). Thanks!]
Week 1-2 Countings; Binomial Theorem; Estimating; Inclusion-Exclusion; Ordinary Generating Functions. Week 3 Applications of Ordinary Generating Functions: Integer Partitions, The Catalan Number and Random Walk; Exponential Generating Function. Week 4-7 Exponential Generating Function (continued); Basic of Graph Theory; Double-couting Method, including Handshaking Lemma, Sperner's Lemma (2-dimension), Brouwer's Fixed Point Theorem (2-dimension), Sperner's Theorem (2 proofs), and Reiman's Bound (The maximum number of edges in graphs with no C4); Mantel's Theorem (The maximum number of edges in graphs with no triangle C3). Week 8 Trees and Cayley's formula (3 proofs). Week 9 Midterm and Review. Week 10 Erdos-Ko-Rado; Partially Ordered Sets; Pigeonhole Principle: Two vertices of the same degree, Subset with divisions, Rational Approximation, and Erdos-Szekeres (2 proofs). Week 11 Ramsey Theory: Ramsey's Theorem, Ramsey number, lower bounds of R(k,k), and Schur's Theorem; Probabilistic methods: Union bound (2-colorability of k-family, bipartiteness of random graph). Week 12-13 Probabilistic methods: Union bound (A property of Tournaments); Expectation (Basic, large cut of graphs, sum-free sets, and dominating sets of graphs); Turan's Theorem: rough form (2 proofs: one via maximum independent set and another via maximizing the formula of P), and exact form (a proof by induction on r.) Week 14 The deletion method (a better lower bound of R(k,k), a proof to get the halfway of Turan's Theorem, Markov's inequality, maximum independent set in random graph, graphs with arbitrary high chromatic number and arbitrary large girth, and Mycielsky graphs) Week 15 Linear Algebra methods: Odd/Even town, Even/Odd town, Fisher's inequality, 1-distance problems, and 2-distance set. Week 16-17 L-intersecting family and its applications (explicit Ramsey lower-bound and Borsuk's conjecture); Bollobas's Theorem and its skew version (using the "general position" argument); Graham-Pollak Theorem (covering by complete bipartite subgraphs); Finite Projective Plane (with an application for constructing C4-free graphs).Homeworks:
HW 1 . If you want to use the tex file of the problem set, download Tex1