Things to know for the final

1Graph matchings¶

1.1Stable marriage¶

Gale-Shapley: male choice method, male-optimal, female-pessimal (lemma: no woman leaves/rejects a valid partner)

1.2Matching cardinality¶

Match $M$ is maximal $\iff$ no augmenting path for $M$. Proof: ($\Rightarrow$) just switch $M$ and not $M$ in the path. ($\Leftarrow$) Symmetric diff with $M$ and $M^*$ (a theoretical maximal matching); all vertices have deg $\leq 2$, so there are only disjoint paths and cycles. Specifically, we have even-length paths, even-length cycles, and odd-length paths ending in $M^*$ - but the latter is augmenting wrt $M$.

1.3Bipartite graphs¶

No odd cycles. Can be separated into 2 groups, each edge spans both.

1.3.1Hall's theorem¶

Bipartite graph has a PM $\iff$ $\forall A \subseteq X$, $|\Gamma(A)| \geq |A|$. Proof: sort of by induction on $X$, it's weird

1.3.2Regular graphs¶

$d$-regular: all vertices have $\deg d$. Any $d$-reg bipartite graph can be decomposed into $d$ edge-disjoint PMs. Proof by induction: if it has a PM $M$, can apply IH to $G-M$ (since it's $(d-1)$-regular) and then throw $M$ back in there. To prove it has a PM, show that Hall's holds.

1.3.3Latin rectangles¶

Extending to a square: $X$ = columns, $Y$ = numbers. Edge between column and number if the number is not in the column. Results in a $(n-r)$ regular graph, decomposes into PMs, make those into new rows.

1.3.4Edge colouring¶

Bipartite graph: $\chi^E(G) = \Delta(G)$ (max deg); proof by adding dummy edges until it's $d$-regular and then decomposing

1.3.5Systems of distinct representatives¶

SDR exists $\iff$ union of any sets $\geq$ size of any one set. Proof by Hall's.

1.3.6The house-selling problem¶

Bipartite graph. Find a perfect matching. If you can't, find an unsuppliable set $A \subseteq X$; increase house prices in $\Gamma(A)$ and decrease house prices of undemanded houses; continue until PM is found.

1.3.7Telecommunication networks¶

Crossbar: $N$ inputs/outputs; $N^2$ connections, $O(N^4)$ crossovers.

Clos: $r$ $n\times m$, then $m$ $r\times r$, then $r$ $m \times n$. Fewer connections, fewer crossovers. If $m=2n-1$, all packets can be routed online. For offline routing, create a bipartite graph, edge between $(i, \pi_i)$, use Hall's.

1.3.8König-Egerváry¶

Largest matching = smallest vertex cover

2Planar graphs¶

2.1Euler's formula¶

$m+2=n+f$. Proof by induction: base case = tree; otherwise, cycle - remove an edge and apply IH.

2.2Other formulas¶

Any planar graph: $m \leq 3n-6$ for $n \geq 4$. Proof: by Euler. An edge has at most 2 faces; face has at least 3 edges.

Bipartite planar graph: $m \leq 2n-4$. There are no odd cycles, so, any face has at least 4 edges.

2.3Platonic solids¶

Only 5. Proof: Euler's formula, using $2m=n \cdot d$ (cus regular) and $2m=f\cdot p$ (cus an edge has 2 faces).

2.4Vertex-colouring¶

Six-colourability proof: using Euler's, min degree $< 6$; remove, apply IH, add back.

2.5Art gallery theorem¶

$n$ walls $\to$ $\lfloor n/3 \rfloor$ guards. Proof: split up floor into triangle, prove 3-colourability by induction.

2.6Planar duals¶

Swap faces and vertices.

2.7Graph minors¶

Contracting edges is basically all you need. Equivalent to contracting trees.

2.8Kuratowski's theorem¶

Planar $\iff$ no $K_3$ or $K_{5,5}$ minor. Proof by minimum counterexample.

2.9Fáry's theorem¶

Any planar graph has a straight line drawing. Proof by induction?

2.10Menger's theorem¶

Max flow min cut basically

3Probability¶

3.1Union and intersection¶

$$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

3.2Conditional¶

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

3.3Bayes' theorem¶

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

3.4Discrete random variables¶

Linearity of expectation: $E(aX + bY) = aE(X) + bE(Y)$

For independent events: $E(XY) = E(X)E(Y)$

3.5Binomial distribution¶

Bernouilli trial: success with prob $p$.

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

3.6Random walks¶

Markov chain model. Just matrix multiplication. Stationary distribution with $d_v/2m$ for any $v$.

3.7Markov's inequality¶

$$P(Z > c \cdot E(Z)) \leq \frac{1}{c}$$

3.8Chernoff bounds¶

Ind. Bernouilli trials $X = X_1 + X_2 + \ldots + X_j$, $\mu = E(X)$. Then:

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

Proof: let $f(x) = e^{tx}$ for some $t$, apply to both sides of inequality of LHS. Use Markov's, simply with $p$. Use the fact that $1+x \leq e^x$ (or $1-x \leq e^{-x}$ for the $<$ inequality). Take the deriv of the exponent, set to 0 to find $t$.

Corollary: $1 > \delta > 0$, $P(X > (1+\delta)\mu) \leq e^{-1/3\mu\delta^2}$. Proof by Taylor series.

Another: $b \geq 6 \mu$, $P(X > b) \leq 2^{-b}$. Proof since $2e < 6$.

4Combinatorics¶

4.1Calatan numbers¶

+-+-+ etc with each partial sum (from the left) being positive.

$$C(n) = \frac{1}{n+1} \binom{2n}{n}$$

Proof: Using $D(n)$, the reflection thing, etc.

4.2Generating functions¶

4.2.1Ordinary¶

For counting labelled objects

$$F(x) = \sum_{n \geq 0} f(x) x^n$$

4.3Exponential¶

For counting unlabelled objects

$$F(x) = \sum_{n \geq 0} f(x) \frac{x^n}{x!}$$

4.4Binomial theorem¶

$$(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$$

Generalised: let $\displaystyle \binom{n}{k} = \frac{n \cdot (n-1)\cdots (n-k+1)}{k!}$