Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : The Basics : PHP, Bijections and PIE**- 10 meetings- Meeting 01 : Mon, Jul 25, 05:00 pm-05:50 pm
- Meeting 02 : Wed, Jul 27, 02:00 pm-03:15 pm
- Meeting 03 : Thu, Jul 28, 03:30 pm-05:00 pm
- Meeting 04 : Mon, Aug 01, 05:00 pm-05:50 pm
- Meeting 05 : Wed, Aug 03, 02:00 pm-03:15 pm
- Meeting 06 : Thu, Aug 04, 03:30 pm-04:50 pm
- Meeting 07 : Mon, Aug 08, 05:00 pm-05:50 pm
- Meeting 08 : Wed, Aug 10, 02:00 pm-03:15 pm
- Meeting 09 : Thu, Aug 11, 03:30 pm-04:50 pm
- Meeting 10 : Wed, Aug 17, 03:30 pm-04:50 pm

Administrative announcements. Proof techniques and axiomatization. <br>PHP and basic applications. References Lecture Notes - Lecture 01 Exercises Reading Administrative announcements. Proof techniques and axiomatization.

PHP and basic applications.References: Lecture Notes - Lecture 01 Four example Applications of PHP. Erdos-Szekeres Theorem. References Lecture Notes - Lecture 02 Exercises Reading Four example Applications of PHP. Erdos-Szekeres Theorem.References: Lecture Notes - Lecture 02 Dirichlet's Approximation theorem. References Lecture Notes - Lecture 03 Exercises Reading Dirichlet's Approximation theorem.References: Lecture Notes - Lecture 03 Counting by Bijections. Double counting. Multichoose. Four counting problems and bijection between them. References Lecture Notes - Lecture 04 Exercises Reading Counting by Bijections. Double counting. Multichoose. Four counting problems and bijection between them.References: Lecture Notes - Lecture 04 Expression for multichoosing. Monotone walks on the grid. Catalan Bijections. References Lecture Notes - Lecture 05/06 Exercises Reading Expression for multichoosing. Monotone walks on the grid. Catalan Bijections.References: Lecture Notes - Lecture 05/06 Counting by approximate Bijections. Principle of Inclusion-Exclusion. Applications of PIE. Counting non-derangements. Bound for Euler's totient function using PIE. Bon-Ferroni inequalities. References Lecture Notes - Lecture 07/08 Exercises Reading Counting by approximate Bijections. Principle of Inclusion-Exclusion. Applications of PIE. Counting non-derangements. Bound for Euler's totient function using PIE. Bon-Ferroni inequalities.References: Lecture Notes - Lecture 07/08 Mobious function. Counting the number of surjections. Stirling number of second kind. References Lecture Notes - Lecture 09 Exercises Reading Mobious function. Counting the number of surjections. Stirling number of second kind.References: Lecture Notes - Lecture 09 Kirchoff's Matrix Tree Theorem. Determinant expansion and properties. Tutte's theorem on counting arborescences, Spregs. References Lecture Notes - Lecture 10 Exercises Reading Kirchoff's Matrix Tree Theorem. Determinant expansion and properties. Tutte's theorem on counting arborescences, Spregs.References: Lecture Notes - Lecture 10 Using PIE to prove Tutte's theorem on counting arborescences via Spregs. Correspondence between spregs and terms in the determinant expression. References Lecture Notes - Lecture 10 Exercises Reading Using PIE to prove Tutte's theorem on counting arborescences via Spregs. Correspondence between spregs and terms in the determinant expression.References: Lecture Notes - Lecture 10 Algorithmic Applications of PIE. References Lecture Notes - Lecture 11 (unfortunately it is incomplete). Exercises Reading Algorithmic Applications of PIE.References: Lecture Notes - Lecture 11 (unfortunately it is incomplete). **Theme 2 : Combinatorial and Probablity Methods**- 6 meetings- Meeting 11 : Thu, Aug 18, 03:30 pm-04:50 pm
- Meeting 12 : Mon, Aug 22, 05:00 pm-05:50 pm
- Meeting 13 : Wed, Aug 24, 02:00 pm-03:15 pm
- Meeting 14 : Thu, Aug 25, 03:30 pm-04:50 pm
- Meeting 15 : Mon, Aug 29, 05:00 pm-05:50 pm
- Meeting 16 : Thu, Sep 01, 03:30 pm-04:50 pm

Back to extremal Problems. Party Theorem. Two models using graphs and using colored complete graphs. Definition of Ramsey numbers. Erdos-Szekeres upper bound for Ramsey numbers. References Notes from <a href="https://math.uchicago.edu/~may/REUDOCS/Steed.pdf">here</a>. Exercises Reading Back to extremal Problems. Party Theorem. Two models using graphs and using colored complete graphs. Definition of Ramsey numbers. Erdos-Szekeres upper bound for Ramsey numbers.References: Notes from here. Lower bound for diagonal Ramsey's numbers. Probabilistic method. k-dimensional Ramsey numbers, recurrence for them. Applications of Ramsey theory. Schur's theorem. References Notes from <a href="https://math.uchicago.edu/~may/REUDOCS/Steed.pdf">here</a>. Exercises Reading Lower bound for diagonal Ramsey's numbers. Probabilistic method. k-dimensional Ramsey numbers, recurrence for them. Applications of Ramsey theory. Schur's theorem.References: Notes from here. Mantel's theorem and the three proofs. (1) Cauchy-Schwartz inequality (2) AM-GM-inequality (3) using PHP. Introduction to averaging argument and shifting technique. References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> Page 39) Exercises Reading Mantel's theorem and the three proofs. (1) Cauchy-Schwartz inequality (2) AM-GM-inequality (3) using PHP. Introduction to averaging argument and shifting technique.References: EC Book by Jukna Page 39) Weight shifting argument. Graham-Kleitman Theorem. Fourth proof of Mantel's Theorem. References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> (Page 43) Exercises Reading Weight shifting argument. Graham-Kleitman Theorem. Fourth proof of Mantel's Theorem.References: EC Book by Jukna (Page 43) Turans Theorem. Basic probability definitions and expectation. Linearity of expectation. References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> (Page 41) Exercises Reading Turans Theorem. Basic probability definitions and expectation. Linearity of expectation.References: EC Book by Jukna (Page 41) Expectation Method. Caro-Weil Theorem on independence number. General features of the method. <br> Counting under symmetry. Properties of the set of symmetries. Group Structure. References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> (Page187-189 - Theorem 18.4) Exercises Reading Expectation Method. Caro-Weil Theorem on independence number. General features of the method.

Counting under symmetry. Properties of the set of symmetries. Group Structure.References: EC Book by Jukna (Page187-189 - Theorem 18.4) **Theme 3 : Algebraic Methods**- 6 meetings- Meeting 17 : Mon, Sep 05, 05:00 pm-05:50 pm
- Meeting 18 : Wed, Sep 07, 02:00 pm-03:15 pm
- Meeting 19 : Sat, Sep 10, 10:00 am-11:00 am
- Meeting 20 : Mon, Sep 12, 05:00 pm-05:50 pm
- Meeting 21 : Wed, Sep 14, 02:00 pm-04:00 pm
- Meeting 22 : Thu, Sep 15, 03:30 pm-04:55 pm

Counting under symmetry. The square coloring problem. Properties of the set of symmetries. Group Structure. Subgroups, cosets, Lagrange's theorem. Orbits. Stabilizers. Orbit-Stabilizer Lemma. References <a href="https://courses.mai.liu.se/GU/TATA55/Dokument/Huisinga.pdf">Huisinga's Notes</a> Exercises Reading Counting under symmetry. The square coloring problem. Properties of the set of symmetries. Group Structure. Subgroups, cosets, Lagrange's theorem. Orbits. Stabilizers. Orbit-Stabilizer Lemma.References: Huisinga's Notes Orbit Stabilizer Lemma. Burnside's Lemma. Applications to counting under symmetry. Counting the number of fixpoints. References <a href="https://courses.mai.liu.se/GU/TATA55/Dokument/Huisinga.pdf">Huisinga's Notes</a> Exercises Reading Orbit Stabilizer Lemma. Burnside's Lemma. Applications to counting under symmetry. Counting the number of fixpoints.References: Huisinga's Notes Cycle Index Polynomial. Polya's theorem. Cycle index for symmetric group, Dihedral group. Applications. References <a href="https://courses.mai.liu.se/GU/TATA55/Dokument/Huisinga.pdf">Huisinga's Notes</a> Exercises Reading Cycle Index Polynomial. Polya's theorem. Cycle index for symmetric group, Dihedral group. Applications.References: Huisinga's Notes Extremal Problems in Sets Linear Algebraic Tools. Fischers Inequality. References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> (Page 73) Exercises Reading Extremal Problems in Sets Linear Algebraic Tools. Fischers Inequality.References: EC Book by Jukna (Page 73) Independence Method. Constructive Ramsey Lower Bounds. Erdos-Ko-Rado Theorem References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> (Page 73) Exercises Reading We did not prove Erdos-Ko-Rado in class due to time limiations. But the recording of the same is shared. Independence Method. Constructive Ramsey Lower Bounds. Erdos-Ko-Rado TheoremReferences: EC Book by Jukna (Page 73) Reading: We did not prove Erdos-Ko-Rado in class due to time limiations. But the recording of the same is shared. Polynomial-Method. Two-Distance-Theorem. Frankl-Wilson-Theorem. References <a href="https://www.mathematik.uni-muenchen.de/~kpanagio/draft.pdf">EC Book by Jukna</a> (Page 136) Exercises Reading Polynomial-Method. Two-Distance-Theorem. Frankl-Wilson-Theorem.References: EC Book by Jukna (Page 136) **Theme 4 : Spectral Methods**- 11 meetings- Meeting 23 : Mon, Sep 19, 05:00 pm-05:50 pm
- Meeting 24 : Wed, Sep 21, 02:00 pm-03:15 pm
- Meeting 25 : Thu, Sep 22, 03:30 pm-04:50 pm
- Meeting 26 : Wed, Sep 28, 02:00 pm-03:15 pm
- Meeting 27 : Thu, Sep 29, 03:30 pm-04:50 pm
- Meeting 28 : Wed, Oct 05, 02:00 pm-03:15 pm
- Meeting 29 : Thu, Oct 06, 03:30 pm-04:50 pm
- Meeting 30 : Mon, Oct 10, 05:00 pm-05:50 pm
- Meeting 31 : Wed, Oct 12, 02:00 pm-03:15 pm
- Meeting 32 : Thu, Oct 13, 03:30 pm-04:50 pm
- Meeting 33 : Wed, Oct 19, 02:00 pm-03:15 pm

The adjacency matrix of a graph. Algebraic properties vs Graph properties. The spectrum of a graph. References Lecture notes by Quinlan. Exercises Reading The adjacency matrix of a graph. Algebraic properties vs Graph properties. The spectrum of a graph.References: Lecture notes by Quinlan. Co-spectral Graphs. Examples. The friendship theorem. An algebraic proof. A quick overview of linear algebra. References Lecture notes by Quinlan. Exercises Reading Co-spectral Graphs. Examples. The friendship theorem. An algebraic proof. A quick overview of linear algebra.References: Lecture notes by Quinlan. Quick overview of Linear Algebra: Matrices, Eigen values and eigen vectors. Real symmetric matrices. References Lecture notes by Quinlan and lecture notes by He Sun. For more linear algebra, refer to any standard text book on the matter, e.g., one by Hoffman and Kunz (doesn't have much on eigen values though). The one by Sheldon Axler "Linear Algebra Done Right" is also a good reference. Further, Gilbert Strang's "Linear Algebra and Its Applications" has detailed examples. Exercises Reading Quick overview of Linear Algebra: Matrices, Eigen values and eigen vectors. Real symmetric matrices.References: Lecture notes by Quinlan and lecture notes by He Sun. For more linear algebra, refer to any standard text book on the matter, e.g., one by Hoffman and Kunz (doesn't have much on eigen values though). The one by Sheldon Axler "Linear Algebra Done Right" is also a good reference. Further, Gilbert Strang's "Linear Algebra and Its Applications" has detailed examples. Spectrum of symmetric matrices. Spectrum of the Laplacian matrix of a graph. References Notes by Trevisan (uploaded on moodle). Text book: "Spectral Graph Theory" by Fan R. K. Chung. Examples were taken by this book. The lectures notes by He Sun in fact follows the book by Chung. Exercises Reading Spectrum of symmetric matrices. Spectrum of the Laplacian matrix of a graph.References: Notes by Trevisan (uploaded on moodle). Text book: "Spectral Graph Theory" by Fan R. K. Chung. Examples were taken by this book. The lectures notes by He Sun in fact follows the book by Chung. Spectrum of the Laplacian matrix of a graph. References Notes by Trevisan (uploaded on moodle). Text book: "Spectral Graph Theory" by Fan R. K. Chung. Examples were taken by this book. The lectures notes by He Sun in fact follows the book by Chung. Exercises Reading Spectrum of the Laplacian matrix of a graph.References: No Lecture. Institute holiday. References Exercises Reading No Lecture. Institute holiday.References: None Expander graphs. Introduction. Vertex expansion. Spectral expansion. Spectral to vertex expansion. References Exercises Reading Expander graphs. Introduction. Vertex expansion. Spectral expansion. Spectral to vertex expansion.References: None Existence of expanders. Probabilistic Arguement. References Exercises Reading Existence of expanders. Probabilistic Arguement.References: None Expander Mixing Lemma. Random Walks in Expanders. Applications of expander graphs. References Exercises Reading Expander Mixing Lemma. Random Walks in Expanders. Applications of expander graphs.References: None Random Walks in expanders. Sucess probability amplification. Construction of expander graphs. Introduction to graph products. References Exercises Reading Random Walks in expanders. Sucess probability amplification. Construction of expander graphs. Introduction to graph products.References: None Construction of expanders: Squaring, Tensor product and zig-zag product. An overview of Applications of Expanders: Undirected s-t connectivity. References Exercises Reading Construction of expanders: Squaring, Tensor product and zig-zag product. An overview of Applications of Expanders: Undirected s-t connectivity.References: None **Theme 5 : Analytical Methods**- 5 meetings- Meeting 34 : Mon, Oct 17, 05:00 pm-05:50 pm
- Meeting 35 : Thu, Oct 20, 05:00 pm-05:50 pm
- Meeting 36 : Wed, Oct 26, 02:00 pm-03:15 pm
- Meeting 37 : Thu, Oct 27, 03:30 pm-05:00 pm
- Meeting 38 : Mon, Oct 31, 05:00 pm-06:15 pm

Short Quiz - 2 References Exercises Reading Short Quiz - 2References: None Introductions to Fourier Analysis of Boolean functions. Basic properties. References Ryan O'Donnel's book. Exercises Reading Introductions to Fourier Analysis of Boolean functions. Basic properties.References: Ryan O'Donnel's book. BLR Linearity testl References Ryan O'Donnel's Book: Analysis of Boolean Functions" Exercises Reading BLR Linearity testlReferences: Ryan O'Donnel's Book: Analysis of Boolean Functions" The spectrum of a Boolean function. Applications to Learning theory. References Exercises Reading The spectrum of a Boolean function. Applications to Learning theory.References: None Goldreich Levin Theorem. Introduction to Mobius inversion. References Exercises Reading Goldreich Levin Theorem. Introduction to Mobius inversion.References: None **Theme 6 : Poset Methods**- 4 meetings- Meeting 39 : Mon, Oct 03, 05:00 pm-05:50 pm
- Meeting 40 : Wed, Nov 02, 02:00 pm-03:20 pm
- Meeting 41 : Thu, Nov 03, 03:30 pm-04:50 pm
- Meeting 42 : Mon, Nov 07, 05:00 pm-05:50 pm

Vide lecture. (13 and 14) Revision of inclusion exclusion principle. Introduction to Mobius function. Mobius inversion formula. Proof. References Exercises Reading Vide lecture. (13 and 14) Revision of inclusion exclusion principle. Introduction to Mobius function. Mobius inversion formula. Proof.References: None Mobius inversion for numbers. Introduction to posets. Mobius inversion on posets. References VanLint and Wilson "Combinatorics" Brualdi's book "Introductory Combinatorics" Exercises Reading Mobius inversion for numbers. Introduction to posets. Mobius inversion on posets.References: VanLint and Wilson "Combinatorics" Brualdi's book "Introductory Combinatorics" Mobius inversion over posets (contd) . Applications. References Exercises Reading Mobius inversion over posets (contd) . Applications.References: None No Lecture. References Exercises Reading No Lecture.References: None