ii. Matroids

A matroid is exactly the structure on which the sorted greedy is always optimal. Recognising one is a proof of the greedy for free, and matroid intersection solves a class of problems greedy can’t.

Definition

$M=(E,\mathcal{I})$ with:

1. $\varnothing \in \mathcal{I}$;
2. hereditary: subsets of independent sets are independent;
3. exchange: if $A,B\in \mathcal{I}$ and $|A|<|B|$, some $x\in B\setminus A$ has $A+x\in \mathcal{I}$.

Maximal independent sets (bases) all have the same size, the rank. A minimal dependent set is a circuit.

Proof: all bases have the same size

Let $A,B$ be maximal independent sets (bases) with $|A|<|B|$. By the exchange axiom, some $x\in B\setminus A$ has $A+x\in \mathcal{I}$, contradicting that $A$ is maximal (no superset of $A$ is independent). So no two bases have $|A|<|B|$, i.e. all bases have equal size. $■$

Rado-Edmonds: for a hereditary family, “sort by weight descending and add if still independent” finds a maximum-weight independent set for every weight function iff the family is a matroid. For a maximum-weight basis with negative weights allowed, keep adding even negative elements; for a maximum-weight independent set, stop at the first negative.

Proof: the matroid greedy is optimal (the "if" direction of Rado–Edmonds)

Let $G=\{g_1,\dots ,g_k\}$ be the greedy output (elements taken in descending weight order, each added iff independence is preserved) and let $O$ be any maximum-weight independent set, both indexed in descending weight order ($w(g_1)\ge \cdots \ge w(g_k)$, likewise for $O$). Claim: $w(g_i)\ge w(o_i)$ for every $i\le \min (|G|,|O|)$, and $|G|\ge |O|$ when only non-negative weights are kept (the basis variant drops this restriction). Suppose for contradiction $w(g_i)<w(o_i)$ for some smallest such $i$ (so $w(g_j)\ge w(o_j)$ for $j<i$). Consider $A=\{g_1,\dots ,g_{i-1}\}$ and $B=\{o_1,\dots ,o_i\}$: both independent (prefixes of independent sets stay independent by the hereditary axiom), with $|A|=i-1<i=|B|$. By the exchange axiom, some $x\in B\setminus A$ has $A+x$ independent. Since $x\in \{o_1,\dots ,o_i\}$ and $w(o_i)$ is the smallest weight among these (descending order), $w(x)\ge w(o_i)>w(g_i)$. But greedy considers elements in descending weight order and had already placed every element of weight $\ge w(x)$ before deciding on $g_i$ — in particular it considered $x$ (or an equal-weight substitute) no later than step $i$, and since $A+x$ is independent at that point, greedy would have taken some element of weight $\ge w(x)>w(g_i)$ at or before step $i$ rather than $g_i$ — contradicting that greedy’s $i$-th pick has weight exactly $w(g_i)$ (ties broken consistently). So no such $i$ exists, proving the claim, and summing $w(g_i)\ge w(o_i)$ over all $i$ (restricted to positive weights for the independent-set variant, where greedy correctly stops early) gives $w(G)\ge w(O)$; since $O$ was maximum, $w(G)=w(O)$. $■$ (The converse — if greedy is optimal for every weight function then $\mathcal{I}$ is a matroid — is the harder direction of the classical theorem and is not needed for using the greedy; it is stated here only as the reason “iff” is the correct word.)

Common matroids

Matroid	Independent sets	Oracle
uniform $U_{k,n}$	sets of size $\le k$	count
partition	at most $c_i$ from each group	counters
graphic	forests	DSU
cographic (bond)	edge sets whose removal keeps the graph connected	bridges / DSU on the complement
linear	linearly independent vectors (over any field)	Gaussian elimination; XOR basis over ${\mathbb{F}}_2$
transversal	subsets of the left side matchable into the right side	bipartite matching
scheduling (unit jobs)	job sets that can all meet their deadlines	sort by deadline, check the $i$-th job has deadline $\ge i$
gammoid	sets linked by vertex-disjoint paths to a fixed set	max flow

Consequences:

• graphic + DSU is Kruskal;
• linear over ${\mathbb{F}}_2$: “choose numbers with linearly independent XORs maximising total weight”: sort by weight, insert into an XOR basis, keep the ones that insert (XOR Basis);
• scheduling: unit jobs with deadlines and profits, sorted by profit, kept if still feasible (check with a DSU “latest free slot”).

Not matroids: knapsack (weights), matchings in a general graph as edge sets, independent sets of vertices in a graph, paths. If greedy fails on a small example, the structure isn’t a matroid.

Strong basis exchange / bottleneck facts. In a matroid with weights, the greedy basis is simultaneously min-sum and min-max (bottleneck). For MSTs this is “the MST minimises the maximum edge”.

Proof: the min-sum greedy basis is also a min-bottleneck basis

Run greedy for minimum sum by ascending weight (symmetric to the descending-weight version proved above). Let $G$ be its output and $w^{\ast }={\max }_{g\in G}w(g)$. Suppose some basis $B$ has ${\max }_{b\in B}w(b)<w^{\ast }$: then every element of $B$ has weight $<w^{\ast }$. Let $G_{<w^{\ast }}=\{g\in G:w(g)<w^{\ast }\}$, so $|G_{<w^{\ast }}|=\text{rank}(M)-1$ (all of $G$ except the single element achieving $w^{\ast }$, since greedy’s prefix below any weight threshold is a maximal independent set among elements of smaller weight — if it weren’t maximal, greedy would have added more before reaching $w^{\ast }$). But $B$ is independent, every element of $B$ has weight $<w^{\ast }$, and $|B|=\text{rank}(M)>|G_{<w^{\ast }}|$; by the exchange axiom some $x\in B\setminus G_{<w^{\ast }}$ has $G_{<w^{\ast }}+x$ independent, with $w(x)<w^{\ast }$ — so greedy, scanning in ascending order, would have added $x$ before reaching $w^{\ast }$, making $G_{<w^{\ast }}$ not maximal among weight-$<w^{\ast }$ elements after all, a contradiction. So no basis has a strictly smaller bottleneck than $w^{\ast }$, and $G$ achieves the minimum. $■$

Operations

• Restriction / deletion / contraction keep matroids. Contracting an element in a graphic matroid contracts the edge.
• Dual $M^{\ast }$: bases are complements of bases. The dual of graphic is cographic. $\text{rank}(M^{\ast })=|E|-\text{rank}(M)$.

Proof: $\text{rank}(M^{\ast })=|E|-\text{rank}(M)$

Every basis of $M^{\ast }$ is, by definition, the complement $E\setminus B$ of some basis $B$ of $M$. All bases of $M$ have the same size $\text{rank}(M)$ (proved above), so every basis of $M^{\ast }$ has size $|E|-\text{rank}(M)$ — and since all bases of $M^{\ast }$ also have equal size (it is itself a matroid), that common size is $\text{rank}(M^{\ast })$. $■$

• Truncation (keep only sets of size $\le k$) and union $M_1\vee M_2$ (sets splittable into one independent set of each) are matroids. The union has rank ${\min }_A(|E\setminus A|+r_1(A)+r_2(A))$ (Nash-Williams). That gives: $k$ edge-disjoint spanning trees exist iff for every partition $\mathcal{P}$ of the vertices, the number of edges between parts is $\ge k(|\mathcal{P}|-1)$ (Nash-Williams-Tutte).

Matroid intersection

Find a maximum common independent set of two matroids on the same ground set. Greedy fails, but augmenting paths in an exchange graph solve it in $O(r^{2}n)$ oracle calls for the unweighted version, and the weighted version uses shortest augmenting paths with potentials.

Problems that are matroid intersections:

• bipartite matching (two partition matroids), which is why it isn’t a matroid itself;
• rainbow / colourful spanning tree: graphic ∩ partition by colour;
• spanning tree with at most $c_i$ edges of each type;
• arborescences with degree constraints (graphic ∩ partition by head);
• “pick a basis of vectors, at most one from each group”: linear ∩ partition.

Min-max formula: $\max |I|={\min }_{A\subseteq E}(r_1(A)+r_2(E\setminus A))$.

Algorithm details and code: Matroid Intersection. Intersection of three matroids is NP-hard (it includes Hamiltonian path), so problems needing three constraints aren’t solved this way.

Recognising a matroid

Ask: “If $x$ can’t be added now, can adding more elements ever make it addable?” Then try the exchange axiom on small examples by brute force. If both hold, the greedy is optimal. A quick check is to run the greedy against a brute force on random small instances: a matroid passes every time.