MATH 239: Introduction to Combinatorics
Combinatorial proof: To show A and B refer to the same set, show
- Basically, show that they show the same set
- Some nice notes https://www.richardwu.ca/notes/math239-final-notes.pdf by Richard Wu
Chapter 1: Enumeration
- Generating Series
- Sum Lemma, Product Lemma, String Lemma
- Regular Expression Chapter 2: Graph Theory
- Handshaking Lemma
- Hamiltonian Cycle
- Bipartite Graph
- Hypercube Graph
- Graph Cut
- Eulerian Circuit
- Planar Graph
- Graph Colouring
- Graph Matching
Things that i need to work on:
- Bijection proof, revisit tutorial 8-4
- Product lemma, string lemma, and sum lemma. When do you use these in proofs?
- Overlap case…?
Other things to practice:
- Hall’s theorem
I believe the key to mastering this final is being able to problem solve SUPER quickly. I struggled with the midterm for that. This is why you need to do lots of problems and just time yourself. Know the different theorems like the back of your hand, and when to use them. Build strong Intuition.
Get good at induction. It seems that a lot of the proof require the use of induction.
Final: I need to go through
- all the assignments again,
- as well as the practice final,
- as well as other sample finals
- as well as the tutorials
And then you should be good to go.
- Practice doing the Bipartite Matching Algorithm
- Practice applying Kuratowski Theorem
- I think I got it, but gotta do a few more. I always just use
- Really master all of the theorems
- Prove that “Every tree is bipartite” (use induction)
Template for strong induction
Inductive Hypothesis: Assume that X holds for any tree/graph with less than edges. Base Case: When , …, so the result holds Inductive Step: …