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!}$