CS5130 - Mathematical Tools for Theoretical Computer Science

Meetings  

• Theme 1 : The Basics : PHP, Bijections and PIE - 10 meetings

  • Meeting 01 : Mon, Jul 25, 05:00 pm-05: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

  • Meeting 02 : Wed, Jul 27, 02:00 pm-03:15 pm

  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

  • Meeting 03 : Thu, Jul 28, 03:30 pm-05:00 pm

  Dirichlet's Approximation theorem.

  References	Lecture Notes - Lecture 03
  Exercises
  Reading

  Dirichlet's Approximation theorem.
  

  References:

  Lecture Notes - Lecture 03

  • Meeting 04 : Mon, Aug 01, 05:00 pm-05:50 pm

  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

  • Meeting 05 : Wed, Aug 03, 02:00 pm-03:15 pm

  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

  • Meeting 06 : Thu, Aug 04, 03:30 pm-04:50 pm

  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

  • Meeting 07 : Mon, Aug 08, 05:00 pm-05:50 pm

  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

  • Meeting 08 : Wed, Aug 10, 02:00 pm-03:15 pm

  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

  • Meeting 09 : Thu, Aug 11, 03:30 pm-04:50 pm

  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

  • Meeting 10 : Wed, Aug 17, 03:30 pm-04:50 pm

  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

  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.

  • Meeting 12 : Mon, Aug 22, 05:00 pm-05:50 pm

  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.

  • Meeting 13 : Wed, Aug 24, 02:00 pm-03:15 pm

  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)

  • Meeting 14 : Thu, Aug 25, 03:30 pm-04:50 pm

  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)

  • Meeting 15 : Mon, Aug 29, 05:00 pm-05:50 pm

  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)

  • Meeting 16 : Thu, Sep 01, 03:30 pm-04:50 pm

  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

  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

  • Meeting 18 : Wed, Sep 07, 02:00 pm-03:15 pm

  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

  • Meeting 19 : Sat, Sep 10, 10:00 am-11:00 am

  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

  • Meeting 20 : Mon, Sep 12, 05:00 pm-05:50 pm

  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)

  • Meeting 21 : Wed, Sep 14, 02:00 pm-04:00 pm

  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 Theorem
  

  References:	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.

  • Meeting 22 : Thu, Sep 15, 03:30 pm-04:55 pm

  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

  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.

  • Meeting 24 : Wed, Sep 21, 02:00 pm-03:15 pm

  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.

  • Meeting 25 : Thu, Sep 22, 03:30 pm-04:50 pm

  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.

  • Meeting 26 : Wed, Sep 28, 02:00 pm-03:15 pm

  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.

  • Meeting 27 : Thu, Sep 29, 03:30 pm-04:50 pm

  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:

  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.

  • Meeting 28 : Wed, Oct 05, 02:00 pm-03:15 pm

  No Lecture. Institute holiday.

  References
  Exercises
  Reading

  No Lecture. Institute holiday.
  

  References:

  None

  • Meeting 29 : Thu, Oct 06, 03:30 pm-04:50 pm

  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

  • Meeting 30 : Mon, Oct 10, 05:00 pm-05:50 pm

  Existence of expanders. Probabilistic Arguement.

  References
  Exercises
  Reading

  Existence of expanders. Probabilistic Arguement.
  

  References:

  None

  • Meeting 31 : Wed, Oct 12, 02:00 pm-03:15 pm

  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

  • Meeting 32 : Thu, Oct 13, 03:30 pm-04:50 pm

  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

  • Meeting 33 : Wed, Oct 19, 02:00 pm-03:15 pm

  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

  Short Quiz - 2

  References
  Exercises
  Reading

  Short Quiz - 2
  

  References:

  None

  • Meeting 35 : Thu, Oct 20, 05:00 pm-05:50 pm

  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.

  • Meeting 36 : Wed, Oct 26, 02:00 pm-03:15 pm

  BLR Linearity testl

  References	Ryan O'Donnel's Book: Analysis of Boolean Functions"
  Exercises
  Reading

  BLR Linearity testl
  

  References:

  Ryan O'Donnel's Book: Analysis of Boolean Functions"

  • Meeting 37 : Thu, Oct 27, 03:30 pm-05:00 pm

  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

  • Meeting 38 : Mon, Oct 31, 05:00 pm-06:15 pm

  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

  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

  • Meeting 40 : Wed, Nov 02, 02:00 pm-03:20 pm

  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"

  • Meeting 41 : Thu, Nov 03, 03:30 pm-04:50 pm

  Mobius inversion over posets (contd) . Applications.

  References
  Exercises
  Reading

  Mobius inversion over posets (contd) . Applications.
  

  References:

  None

  • Meeting 42 : Mon, Nov 07, 05:00 pm-05:50 pm

  No Lecture.

  References
  Exercises
  Reading

  No Lecture.
  

  References:

  None