**Maintainer:**admin

*1*Graph matchings¶

*1.1*Perfect matchings¶

What is a perfect matching?

*1.1.1*General solution¶

A matching $M$ in a graph $G$ is a set of vertex-disjoint edges. A matching $M$ is **perfect** if it covers all the vertices in the graph, i.e., every vertex in $G$ is incident to some edge $M$

*1.1.2*Examples¶

- Practice Exam 1, question 1 (a)

*1.2*Presence of perfect matchings¶

Given a description of some graph, can this graph contain a perfect matching?

*1.2.1*General solution¶

Just think about it. For example, non-bipartite graphs can contain PMs - $K_4$, for example, definitely does (and it's definitely not bipartite).

If there's a vertex with degree 0, there cannot be a PM.

To prove, in the general case, that there is a PM, either use Hall's condition or show that it is $n$-regular.

*1.2.2*Examples¶

- Practice Exam 1, question 1 (b) (bipartite graphs)
- Practice Exam 2, question 2 (b)-(d) (describing the degree of each node)

*1.3*Hall's theorem¶

State it and prove it.

*1.3.1*General solution¶

A bipartite graph with $|X| = |Y|$ has a perfect matching $\iff$ for all $A \subseteq X$, $|\Gamma(A)| \geq |A|$.

Proof: $\Rightarrow$ is trivial. For $\Leftarrow$, suppose Hall's condition is satisfied but there is no perfect matching. Consider some maximal matching $M$. Since it's not perfect, there must be some unmatched vertex $x_1 \in X$. It must have at least one neighbour, $y_1$. $y_1$ must be matched to something, otherwise $M$ wouldn't be maximal (we could just add the $x_1$-$y_1$ edge). Repeat this argument until we conclude that there's an alternating path between vertices in $X$. Keep going, but since the graph is finite, this process cannot go on forever. So there can be unmatched vertex $x_1$.

*1.3.2*Examples¶

- Practice Exam 1, question 1 (c)
- Practice Exam 2, question 2 (a) (just stating it)

*2*Planar graphs¶

*2.1*Kuratowski's theorem¶

State it

*2.1.1*General solution¶

A graph is planar $\iff$ it contains no $K_5$ minor and no $K_{3,3}$ minor.

*2.1.2*Examples¶

- Practice Exam 1, question 2 (a) (i)
- Practice Exam 2, question 1 (a)

*2.2*Euler's formula¶

State it

*2.2.1*General solution¶

A connected planar graph satisfies $2 + m = n + f$ where $n$ = number of vertices, $m$ = number of edges, and $f$ = number of faces.

*2.2.2*Examples¶

- Practice Exam 1, question 2 (a) (ii) and (b)

*2.3*Planarity proofs¶

Prove that some general class of graphs is or is not planar.

*2.3.1*General solution¶

To prove that a graph with $\leq 8$ edges is planar, use the fact that $K_5$ has 10 edges and $K_{3,3}$ has 9 edges.

*2.3.2*Examples¶

- Practice Exam 1, question 2 (b)

*2.4*Determining planarity¶

Given a graph (drawn), determine whether or not it is planar.

*2.4.1*General solution¶

Does this graph satisfy $m\leq 3n-6$ ($m \leq 2n-4$ if the graph is bipartite)? If not, it's definitely not planar. Otherwise, it could still be planar. Try to draw it as a planar graph. If that fails, try to find a $K_5$ minor or a $K_{3, 3}$ minor. For $K_5$, we need 4 vertices, each of which must have 4 neighbours; for $K_{3,3}$, we need 6, each of which must have 3 neighbours (all in a different partition).

*2.4.2*Examples¶

- Practice Exam 1, question 2 (c)
- Practice Exam 2, question 1 (b)

*3*Probability¶

*3.1*Bayes theorem¶

State it, use it

*3.1.1*General solution¶

For any two events $A$ and $B$,

$$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$

To use it, just use it.

*3.1.2*Examples¶

- Practice Exam 2, question 3 (a)

*3.2*Coins or dice¶

Some question about tossing coins or rolling dice

*3.2.1*General solution¶

Might need to use Bayes' formula.

Don't forget linearity of expectation.

*3.2.2*Examples¶

- Practice Exam 1, question 3
- Practice Exam 2, question 3 (b)

*3.3*Boole's inequality¶

State it (also known as union bound)

*3.3.1*General solution¶

$$P\left ( \cup_i X_i \right ) \leq \sum_{i} P(X_i)$$

*3.3.2*Examples¶

- Practice Exam 2, question 4 (a) (i)

*3.4*Chernoff bound¶

Let $X_1, X_2, \ldots, X_n$ be independent Bernoulli trials with $P(X_i = 1) = p_i$. Let $X = \sum X_i$ and $\mu = E(X)$. Then, if $\delta > 0$:

$$P(X > (1+\delta)\mu) \leq \left ( \frac{e^\delta}{(1+\delta)^{(1+\delta)}} \right )^\mu$$

Corollaries:

If $\delta > 1$, we have the weaker bound $\displaystyle P(X > (1+\delta)\mu) \leq e^{-1/3\mu\delta^2}$.

For below the mean, we have $\displaystyle P(X < (1-\delta)\mu) \leq e^{-1/2\mu\delta^2}$

If $b\geq 6\mu$, then we have $\displaystyle P(X > b) \leq 2^{-b}$.

*3.4.1*General solution¶

*3.4.2*Examples¶

- Practice Exam 1, question 4 (a)
- Practice Exam 2, question 4 (a) (ii)

*3.5*Graph probability¶

Some probability question related to graphs

*3.5.1*General solution¶

Use the Chernoff and union bounds. Also just use your brain.

*3.5.2*Examples¶

- Practice Exam 2, question 4 (b)

*3.6*Balls and bins¶

Some question about it

*3.6.1*General solution¶

If we need to give an upper bound on the probability of something, use Chernoff or a corollary.

Expected number of balls to throw before every bin contains one ball: $nH_n$, use linearity of expectation and shit

*3.6.2*Examples¶

- Practice Exam 1, question 4 (b)

*4*Combinatorics¶

*4.1*Binomial theorem¶

State it

*4.1.1*General solution¶

$$(1+x)^n = \sum_{n=0}^n \binom{n}{k}x^k \quad \text{or} \quad (x+y)^n = \sum_{n=0}^n\binom{n}{k}x^ky^{n-k}$$

*4.1.2*Examples¶

- Practice Exam 1, question 5 (a)

*4.2*Proving binomial equalities¶

Given some equality, prove it twice, first using the binomial theorem (or algebraically), then combinatorially.

*4.2.1*General solution¶

To prove it using the binomial theorem, you probably just have to plug in some value for $x$ (and maybe $y$).

To prove it algebraically, use the fact that

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

To prove it combinatorially, explain what each sides counts. Give an example using balls or something.

*4.2.2*Examples¶

- Practice Exam 1, question 5 (b), (c)
- Practice Exam 2, question 5 (a), (b)

*4.3*Generating expressions¶

How many ways are there of doing something for a specific case? If given a recurrence relation, prove that it holds. For the general case, find the gf, then a simple expression for the number.

*4.3.1*General solution¶

The specific case should be obvious, just brute force it.

To prove that a recurrence relation holds, try to find a sub-problem within it which you know how to count, and smuggle that into the recurrence relation somehow.

To find the gf, use the recurrence, and various tricks for manipulating sequences that we saw in class and in the assignments.

To get $f(n)$, you may have to use partial fractions. Basically just figure out the coefficient for $x^n$.

*4.3.2*Examples¶

- Practice Exam 1, question 6
- Practice Exam 2, question 6