graph-theory
The greedy algorithm
### Aside: the matrix-tree theorem
How many spanning trees does a graph have? Form the $V\times V$ Laplacian $L$ by \[ L_{vv}=\deg(v), L_{uv}=-(\text{number of edges from $u$ to $v$}) (u\neq v). \] The eigenvalues of $L$ are $0=\lambda_0,\lambda_1,\ldots,\lambda_{n-1}$.
Theorem（Kirchhoff）. The number $\tau(G)$ of spanning trees of $G$ equals $\frac1n\lambda_1\cdots\lambda_{n-1}$, and also equals any cofactor of $L$.
Example. For the graph $K_4$ minus one edge (vertices $a,b,c,d$, missing $bc$):
\[ L=
3&-1&-1&-1\\ -1&2&0&-1\\ -1&0&2&-1\\ -1&-1&-1&3
. \] A cofactor computation gives $\tau(G)=8$. The scan's $3\times 3$ arithmetic is hard to parse. Deleting the first row and column leaves $\det
2&0&-1\\0&2&-1\\-1&-1&3
=2(6-1)-(-1)(0+2)=10-2=8$.
Note. The notes suggest, as a final project, understanding this and its generalization to linear matroids (the Kirchhoff polynomial / basis generating function of a representable matroid).
### Minimum-weight bases
Given a graph $G=(V,E)$ and a weight $w\colon E\to\R_{\ge 0}$, find a minimum-weight spanning tree. A naive-looking strategy works.
Definition（Greedy algorithm）. Start with $I=\varnothing$. Repeatedly add to $I$ a cheapest element $e$ for which $I\cup\{e\}$ remains independent, until $I$ is a basis.
For graphs this is Kruskal's algorithm (1956). For general matroids the same procedure is due to Rado (1957) and Edmonds (1971); the notes attribute the matroid statement to Kruskal as well.
Proposition. Let $M=(E,\mathcal{I})$ be a matroid and $w\colon E\to\mathbb{R}$ any weight function. The greedy algorithm returns a basis of minimum weight.
*Proof.* Let $I=\{i_1,\ldots,i_r\}$ be the greedy basis, in the order chosen, so $w(i_1)\le\cdots\le w(i_r)$. Let $J=\{j_1,\ldots,j_r\}$ be a minimum-weight basis, ordered $w(j_1)\le\cdots\le w(j_r)$. Suppose $w(I)>w(J)$, and let $k$ be the least index with $w(i_k)>w(j_k)$.
The sets $\{i_1,\ldots,i_{k-1}\}$ and $\{j_1,\ldots,j_k\}$ are independent with unequal sizes, so (I3) supplies some $j_s$ with $1\le s\le k$ such that $\{i_1,\ldots,i_{k-1},j_s\}$ is independent. Then \[ w(j_s)\le w(j_k) > *Filled in.* If several elements have equal weight, any cheapest legal choice works: the > proof only needs $w(j_s)\le w(j_k)\le w(i_k)$, and a strict inequality > $w(I)>w(J)$ forces a strict inequality at the first differing position > after ties are broken consistently. ### A cryptomorphism: greedy characterises matroids A simplicial complex on $E$ is a pair $(E,\mathcal{I})$ satisfying (I2) (and usually (I1)). Matroids are exactly the simplicial complexes on which greedy optimisation works. Proposition. A pair $M=(E,\mathcal{I})$ is a matroid if and only if it satisfies (I1), (I2), and 1. for every $w\colon E\to\mathbb{R}$, the greedy algorithm returns a maximum-cardinality independent set of minimum weight. *Proof.* The forward direction is . Conversely, assume (I1), (I2), (I3$'$), and suppose $I,J\in\mathcal{I}$ with $\lvert I\rvert<\lvert J\rvert$ violate (I3): $I\cup\{e\}\notin\mathcal{I}$ for all $e\in J\setminus I$. Let $r$ be the maximum cardinality of an independent set (greedy produces such a set). Define \[ w(e)=\begin{cases} 1 & e\in I,\\ 2 & e\in J\setminus I,\\ N & e\notin I\cup J, \end{cases} \text{with $N>2\lvert E\rvert$.} \] Greedy first takes all of $I$ (weight $1$), then cannot take any element of $J$, then fills the remaining $r-\lvert I\rvert$ places from $E\setminus(I\cup J)$. The resulting weight is $\lvert I\rvert+N(r-\lvert I\rvert)$. On the other hand $J$ is independent, so (I2) and maximality of $r$ together with (I3$'$) applied to the zero weighting, which forces all maximum independent sets to have size $r$ yield a maximum independent set $B\supseteq J$ of size $r$, with weight at most $2\lvert J\rvert+N(r-\lvert J\rvert)$. Then $$ \begin{aligned} 2\lvert J\rvert+N(r-\lvert J\rvert) &< N+N(r-\lvert J\rvert) =N(r-\lvert J\rvert+1)\\ &\le N(r-\lvert I\rvert) \le \lvert I\rvert+N(r-\lvert I\rvert), \end{aligned} $$ since $\lvert I\rvert\le\lvert J\rvert-1$. Thus greedy did not find a minimum-weight maximum independent set, contradicting (I3$'$). > *Supplement.* The number $\tau(G)$ of spanning trees is the evaluation $T_{M(G)}(1,1)$ > of the Tutte polynomial > \[ > T_M(x,y)=\sum_{A\subseteq E}(x-1)^{r(E)-r(A)}(y-1)^{\lvert A\rvert-r(A)}. > \] > It is the universal deletion–contraction invariant: if $e$ is neither a > loop nor a coloop then $T_M=T_{M\setminus e}+T_{M/e}$, while a coloop > contributes a factor of $x$ and a loop a factor of $y$. Specialising > recovers the chromatic polynomial of a graph, the reliability polynomial, > and (for a linear matroid) the weight enumerator of the associated linear > code. The Kirchhoff polynomial mentioned in the notes is the > homogeneous generating function $\sum_{B\in\mathcal{B}}\prod_{e\in B}x_e$, of > which $\tau(G)$ is the all-ones evaluation. > > The final project on the board—extending Kirchhoff from graphs to > linear matroids—is Cauchy–Binet. If a rank-$r$ matroid is represented > by an $r\times n$ matrix $A$ over $\mathbb{R}$, then > \[ > \det(AA^{T})=\sum_{B}(\det A_{B})^{2}, > \] > the sum running over $r$-subsets of columns; the nonzero terms are > precisely the bases, and $\det A_{B}\neq 0$ is the Plucker coordinate > of $B$. For the (reduced) incidence matrix of a connected graph this > identity is the matrix-tree theorem. > > The same augmentation that makes greedy work yields Edmonds' > matroid intersection theorem: for two matroids $M,N$ on the > same ground set, > \[ > \max\{\lvert I\rvert: I\in\mathcal{I}(M)\cap\mathcal{I}(N)\} > =\min_{X\subseteq E}(r_{M}(X)+r_{N}(E\setminus X)). > \] > Common independent sets of size $k$ in a pair of transversal matroids > are matchings in a bipartite graph, so this contains Konig and > Menger.