Course Information

Problem Sets

1. Problem Set 1: Due Friday Jan 18 and available Tue Jan 8.
   
   
2. Problem Set 2: Due Friday Jan 25 and available Tue Jan 15.
   
   
3. Problem Set 3: Due Friday Feb 1 and available Thu Jan 25.
   
   
4. Practice Midterm: For practice and available Tue Jan 29.
   
   
5. Practice Midterm II: For practice and available Thu Jan 31.
   
   
6. Midterm Exam: Midterm Exam on Fri Feb 8.
   
   
7. Problem Set 4: Due Friday Feb 22 and available Fri Jan 15.
   
   
8. Problem Set 5: Due Friday Mar 1 and available Tue Feb 19.
   
   
9. Problem Set 6: Due Friday Mar 8 and available Thu Feb 28.
   
   
10. Problem Set 7: Due Friday Mar 15 and available Thu Mar 7.
    
    
11. Practice Final: For practice and available Mon Mar 11.
    
    
12. Practice Final II: For practice and available Tue Mar 12.
    
    

Solutions

1. Solutions Problem Set 1: Available Friday Jan 18.
   
   
2. Solutions Problem Set 2: Available Sunday Jan 27.
   
   
3. Solutions Problem Set 3: Available Friday Feb 1.
   
   
4. Solutions Practice Midterm: Available Thursday Jan 31.
   
   
5. Solutions Practice Midterm II: Available Tuesday Feb 5.
   
   
6. Solutions Midterm Exam: Available Fri Feb 8.
   
   
7. Solutions Problem Set 4: Available Friday Feb 22.
   
   
8. Solutions Problem Set 5: Available Tue Mar 5.
   
   
9. Solutions Problem Set 6: Available Mon Mar 11.
   
   
10. Solutions Problem Set 7: Available Fri Mar 15.
    
    
11. Solutions Practice Final: Available Fri Mar 15.
    
    
12. Solutions Practice Final II: Available Fri Mar 15.
    
    

Math Diaries

1. Monday Jan 7: Introduction to Combinatorics.
   
   Structure of the Course. Motivation and Applications.
   Routing Problem (Computer Science). Dijkstra's Algorithm (Optimization).
   Quantum Electrodynamics and Probability (Physics). Molecular Point Groups (Chemistry).
   
   Definition of a set and a subset. Examples.
   Theorem 1.3.1 and its Proof. Theorem 1.5.2 and its Proof.
   The number of digits of 2ⁿ is (n · log(2)+1).
   
   Textbook Reading (Jan 7): Sections 1.3, 1.4 and 1.5.
   Read Sections 1.1 and 1.2 for Introductory Material.
   
   
2. Wednesday Jan 9: Permutations and How Many Subsets.
   
   Seating people and rearranging elements. Definition of Factorial.
   Example of symmetries of a planar equilateral triangle.
   The number of permutations of n elements is n! (Theorem 1.6.1).
   The number of k-element ordered subsets of of n elements (Theorem 1.7.1).
   The number of k-element subsets of of n elements (Theorem 1.8.1).
   Definition of the binomial coefficient. Example of 10 choose 3 and 10 choose 7.
   
   Textbook Reading (Jan 9): Sections 1.6, 1.7 and Beginning of 1.8.
   
   
   
3. Friday Jan 11: Count Twice.
   
   Combinatorial Identities for Binomial Coefficients (Theorem 1.8.2).
   Proof of Theorem 1.8.2. Combinatorial Solution to Problem 1.8.7.
   Closed formula for the sum of the first n numbers via combinatorics.
   Stated formulas for the sums of the first n squares and the first n cubes.
   
   Textbook Reading (Jan 11): Section 1.8 and Problems.
   
   
   
4. Monday Jan 14: The Principle of Induction.
   
   Statement of the Induction Principle: The Base Step and the Induction Step.
   First Application: Closed Formula for The sum of the first n numbers.
   More Examples of Induction. The inequalities 2ⁿ≤ n! ≤ nⁿ.
   
   Textbook Reading (Jan 14): Sections 2.1 and 2.2.
   
   
   
5. Wednesday Jan 16: The Inclusion-Exclusion Technique.
   
   The cardinality of a union of sets. Inclusion-Exclusion Formula for 2 sets.
   Application to the counting numbers which are divisible by a fixed pair of numbers.
   Inclusion-Exclusion Formula for 3 Sets. Application to counting voters.
   Inclusion-Exclusion for 4 sets and General Pattern.
   
   Textbook Reading (Jan 16): Section 2.3 and 2.4.
   
   
   
6. Friday Jan 18: The Birthday Paradox.
   
   The Birthday Problem. Exact count of the probability.
   The General Problem and Closed Formula for the exact probability.
   Estimation and lower bound for the exact probability, via logarithms.
   Corollary in the Birthday Problem case. Successful Class Experiment.
   
   Textbook Reading (Jan 18): Section 2.5.
   
   
   
7. Wednesday Jan 23: Pascal's Triangle.
   
   Binomial Theorem (Thm 3.1.1) and its Combinatorial Proof.
   Four Identities in Pascal's Triangle (3.2, 3.3, 3.4 and Ex. 3.6.1).
   Combinatorial Proofs of these Identities. Refinement of 3.3.
   Statement of the Hockey-Stick Identity.
   
   Textbook Reading (Jan 23): Sections 3.1, 3.5 and 3.6.
   
   
   
8. Friday Jan 25: The Gaussian Behaviour.
   
   The main Theorem of the class (Estimate 3.8).
   Qualitative Behaviour of a row in Pascal's Triangle.
   Detailed Estimates of Decay of Binomial Coefficients (Estimate 3.9).
   Comments and Remarks on Gaussian Behaviour.
   
   Textbook Reading (Jan 25): Sections 3.7 and 3.8.
   
   
   
9. Monday Jan 28: Combinatorial Probability.
   
   Experiment with coin tosses as motivation.
   Probability Spaces. Probability and Uniform Probability.
   Problem 1: Shuffling Cards, Probability that cards stay the same.
   Problem 2: Probability that a Staircase Walk passes through a point.
   Problem 3: Acing a Multiple Choice Test via Random Answers.
   Problem 4: Probability of a pair in a Poker hand.
   
   Textbook Reading (Jan 28): Sections 5.1 and 5.2.
   
   
   
10. Wednesday Jan 31: q-Combinatorics.
    
    Two Motivating Problems: Area of Staircase Walks and Permutations.
    Definition of q-number and the q-factorial. Examples.
    Definition of the (Gaussian) q-Binomial Coefficient.
    Combinatorial Interpretation of the q-Binomial Coefficient via area.
    Combinatorial Interpretation of the q-factorial via permutations.
    
    Textbook Reading (Jan 31): These notes, Sections 6.1 and 6.4.
    Additional References: [1], [2] and Weeks 183-187 in [3].
    
    
    
11. Friday Feb 1: Bijective Solutions (Catalan numbers).
    
    Principle: Solve one problem, solve many. Examples.
    Problem 1: Triangulations of polygons. Problem 2: Parenthesis.
    Problem 3: Dyck Paths. Problem 4: Binary Trees.
    Solution to Problem 1 via Catalan recurison.
    Bijection between Prob. 2 and Problem 3.
    Bijection between Prob. 3 and Problem 4.
    Bijection between Prob. 4 and Problem 1.
    
    Textbook Reading (Feb 1): Slides 1-17 [1] and Slides 1-29 [2].
    Additional References: [1], [2].
    
    Helpful Material for Midterm Study: Sections 2.1 through 2.6 in Combinatorics and Graph Theory by J. Harris, J.L. Hirst, M. Mossinghoff.
    
    
12. Monday Feb 4: The Symmetric Group.
    
    Permutations and Composition of Permutations.
    Definition of the Symmetric group. Examples.
    Groups of Symmetries in geometry. Planar symmetries.
    Symmetry group of the triangle and the Platonic Solids.
    
    
13. Wednesday Feb 6: Midterm Review.
    
    
14. Thursday Feb 7: Special Midterm Review Session 5-7pm.
    
    
15. Friday Feb 8: Midterm Exam.
    
    
16. Monday Feb 11: Introduction to Graph Theory.
    
    Motivation for Graph Theory: Shortest Path Problems, Matching Problems and Colorings.
    Examples of the PageRank algorithm and task assignment problems as vertex colorings.
    Definition of Graph and Examples. Sum-degree Formula (Theorem 7.1.2). Handshaking Lemma.
    
    Textbook Reading (Feb 11): Section 7.1 and 7.2.
    
    
17. Wednesday Feb 13: Euler walks and circuits.
    
    Families of graphs: Complete, Utility, Cyclic and Path graphs.
    Definition of an Euler walk, Euler circuit and examples with the above families.
    Necessary conditions for existence of an Euler walk (and circuit) in terms of degrees.
    Euler's Theorem (Theorem 7.3.1) on the sufficiency of the degree conditions.
    
    Textbook Reading (Feb 13): Section 7.3.
    
    This website is a really nice source for the basics of graph theory. It includes material on Euler walks and circuits and other topics that we are discussing in this class.
    
    
18. Friday Feb 15: Hamiltonian circuits.
    
    Review of the week. Definition of a Hamiltonian Walk and Circuit.
    Examples of Hamiltonian and non-Hamiltonian graphs. Ore's Theorem. Dirac's Theorem.
    Petersen Graph and Herschel Graph. Proof that Herschel is not Hamiltonian.
    
    Additional Resources: This website and here.
    
    
19. Wednesday Feb 20: Trees.
    
    Definition of Trees. Families of Trees: Alkanes, Stars.
    Spanning Trees and examples. Existence of Spanning Trees.
    Characterization of trees in connectedness and acyclicity (Theorem 8.1.1).
    Tree-growing Procedure: all trees grow via this procedure (Theorem 8.2.2).
    
    Textbook Reading (Feb 20): Section 8.1-8.2.
    
    
20. Friday Feb 22: Prufer Correspondence.
    
    Statement of Cayley's Theorem (Theorem 8.3.1).
    The Prufer Correspondence. Storing Trees in Sequences.
    Prufer Code recovers the tree (Lemma 8.4.1). Examples.
    Proof of Cayley's Theorem using the Prufer Correspondence.
    
    Textbook Reading (Feb 22): Section 8.3-8.4.
    
    
21. Monday Feb 25: Perfect Matchings.
    
    Definition of Bipartite Graphs. Matchings and Perfect Matchings.
    Characterization of bipartite graphs in terms of cycles. Examples.
    Matchings in bipartite graphs. Statement of Hall's Theorem.
    
    Textbook Reading (Feb 25): Section 10.1-10.2.
    
    
22. Wednesday Feb 27: Hall's Theorem.
    
    Statement of Hall's Theorem (Theorem 10.3.1). Symmetry in the hypothesis.
    Examples. Detailed proof of Hall's Theorem via reduction on the edges.
    Existence of perfect matchings for regular bipartite graphs (Theorem 10.1.1).
    Statement of application to Latin rectangles and existence of Latin squares.
    
    Textbook Reading (Feb 27): Section 10.3.
    Optional Reading for Greedy Algorithm in Section 10.4.
    
    
23. Friday Mar 1: Planar Graphs.
    
    Definition of a Planar Graph. Classes of Examples.
    Faces of planar embeddings. Statement of Euler's Formula.
    Proof of Euler's Formula (Induction on vertices). Corollaries.
    The Complete Graph K5 is non-planar (Theorem 12.2.1).
    
    Textbook Reading (Mar 1): Chapter 12 with Sections 12.1-12.2.
    
    
24. Mon Mar 4: Coloring Maps and Graphs.
    
    Definition of k-colorings. Examples and non-examples.
    Proof that complete graphs need as many colors as vertices.
    Theorem 13.3.1 on (d+1)-colorability with graphs of degree at most d.
    Proof of Theorem 13.3.1 and questions between planarity and colorability.
    
    Textbook Reading (Mar 4): Chapter 13 with Sections 13.1-13.3.
    
    
25. Mon Mar 6: The Five Color Theorem.
    
    Statement of the Five Color Theorem. Ingredients in the Proof.
    Technical step: existence of a degree five vertex in a planar graph.
    Proof of the Five Color Theorem. Comments on the Four Color Theorem.
    
    Textbook Reading (Mar 6): Section 13.4 in Chapter 13.
    
    
26. Fri Mar 8: Chromatic Polynomials.
    
    The chromatic number of a graph. Function on colors.
    Computation for disconnected, path and cycle graphs.
    The Contraction-Deletion Theorem. Polynomiality of the chromatic function.
    Interpretation of the coefficients of the chromatic polynomial. Examples.
    
    For Reading (Mar 8): These notes and these slides.
    Additional References: This website and Sections 1 and 2 of these notes .
    
    
27. End of Material Expose: Friday March 8.