Home MATH 340 HTSEFP: How to solve every problem

HTSEFP: How to solve every problem CC-BY-NC

Maintainer: admin

1Graph matchings

1.1Perfect matchings

What is a perfect matching?

1.1.1General 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.2Examples

  • Practice Exam 1, question 1 (a)

1.2Presence of perfect matchings

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

1.2.1General 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.2Examples

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

1.3Hall's theorem

State it and prove it.

1.3.1General 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.2Examples

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

2Planar graphs

2.1Kuratowski's theorem

State it

2.1.1General solution

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

2.1.2Examples

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

2.2Euler's formula

State it

2.2.1General 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.2Examples

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

2.3Planarity proofs

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

2.3.1General 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.2Examples

  • Practice Exam 1, question 2 (b)

2.4Determining planarity

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

2.4.1General 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.2Examples

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

3Probability

3.1Bayes theorem

State it, use it

3.1.1General 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.2Examples

  • Practice Exam 2, question 3 (a)

3.2Coins or dice

Some question about tossing coins or rolling dice

3.2.1General solution

Might need to use Bayes' formula.

Don't forget linearity of expectation.

3.2.2Examples

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

3.3Boole's inequality

State it (also known as union bound)

3.3.1General solution

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

3.3.2Examples

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

3.4Chernoff 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.1General solution

3.4.2Examples

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

3.5Graph probability

Some probability question related to graphs

3.5.1General solution

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

3.5.2Examples

  • Practice Exam 2, question 4 (b)

3.6Balls and bins

Some question about it

3.6.1General 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.2Examples

  • Practice Exam 1, question 4 (b)

4Combinatorics

4.1Binomial theorem

State it

4.1.1General 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.2Examples

  • Practice Exam 1, question 5 (a)

4.2Proving binomial equalities

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

4.2.1General 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.2Examples

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

4.3Generating 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.1General 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.2Examples

  • Practice Exam 1, question 6
  • Practice Exam 2, question 6