Ch.6: Matroids
From the lecture notes "Combinatorics, Graphs, Matroids" (University of Bonn, winter term 2025/26) 6.1. Independence Systems and Matroids 6.2. Dual Independence Systems 6.3. The Greedy Algorithm 6.4. Matroid Intersection 6.5. Matroid Partitioning
142 flashcards · Mathematics · by lakesare
Part of University of Bonn › V3C2: Combinatorics, Graphs, Matroids · 6 courses
[Independence Systems and Matroids] Matroids generalize which two classical families of sets?
Linearly independent sets of vectors in a vector space, and edge sets of forests in a graph. The name (due to H. Whitney) comes from vectors as the columns of a matrix: matroids are “matrix-like” structures.
[Independence Systems and Matroids] What is a set system, and when is it an independence system?
A set system is a pair (E,F)(E, \mathcal{F})(E,F) with EEE a nonempty finite set and F\mathcal{F}F a family of subsets of EEE . It is an independence system if (M1) ∅∈F\emptyset \in \mathcal{F}∅∈F and (M2) X⊆Y∈FX \subseteq Y \in \mathcal{F}X⊆Y∈F implies X∈FX \in \mathcal{F}X∈F . So F\mathcal{F}F is nonempty and closed under taking subsets.
[Independence Systems and Matroids] In an independence system (E,F)(E, \mathcal{F})(E,F) , which sets are independent and which are dependent?
Independent: the elements of F\mathcal{F}F . Dependent: the elements of 2E∖F2^E \setminus \mathcal{F}2E∖F .
[Independence Systems and Matroids] In an independence system, minimal dependent sets are called circuits and maximal independent sets are called bases.
For X⊆EX \subseteq EX⊆E , the maximal independent subsets of XXX are the bases of XXX .
[Independence Systems and Matroids] (E,F)(E, \mathcal{F})(E,F) is an independence system and X⊆EX \subseteq EX⊆E . What is the rank r(X)r(X)r(X) ?
r(X)=max{∣Y∣:Y⊆X, Y∈F}\boldsymbol{r(X) = \max\{|Y| : Y \subseteq X,\ Y \in \mathcal{F}\}}r(X)=max{∣Y∣:Y⊆X, Y∈F} The size of a largest independent subset of XXX .
[Independence Systems and Matroids] (E,F)(E, \mathcal{F})(E,F) is an independence system with rank function rrr , and X⊆EX \subseteq EX⊆E . What is the closure σ(X)\sigma(X)σ(X) ?
σ(X)={y∈E:r(X∪{y})=r(X)}\boldsymbol{\sigma(X) = \{y \in E : r(X \cup \{y\}) = r(X)\}}σ(X)={y∈E:r(X∪{y})=r(X)} The elements whose addition does not raise the rank. In particular X⊆σ(X)X \subseteq \sigma(X)X⊆σ(X) .
[Independence Systems and Matroids] State the Maximization Problem for independence systems.
Given an independence system (E,F)(E, \mathcal{F})(E,F) and c:E→Rc : E \to \mathbb{R}c:E→R , find X∈FX \in \mathcal{F}X∈F with c(X)=∑e∈Xc(e)c(X) = \sum_{e \in X} c(e)c(X)=∑e∈Xc(e) maximum.
[Independence Systems and Matroids] State the Minimization Problem for independence systems.
Given an independence system (E,F)(E, \mathcal{F})(E,F) and c:E→Rc : E \to \mathbb{R}c:E→R , find a basis BBB with c(B)c(B)c(B) minimum.
[Independence Systems and Matroids] Why does the Minimization Problem for independence systems ask for a minimum-weight basis, while the Maximization Problem allows any independent set?
With nonnegative weights, the minimum over all independent sets would just be ∅\emptyset∅ . And with positive weights, every optimum of the Maximization Problem is automatically a basis.
[Independence Systems and Matroids] In optimization problems on an independence system (E,F)(E, \mathcal{F})(E,F) , how is F\mathcal{F}F usually given as input?
By an oracle that decides, for a given X⊆EX \subseteq EX⊆E , whether X∈FX \in \mathcal{F}X∈F , not by a list of all members of F\mathcal{F}F . F\mathcal{F}F can be exponentially large in ∣E∣|E|∣E∣ .
[Independence Systems and Matroids] The Maximum Weight Stable Set Problem (given GGG and c:V(G)→Rc : V(G) \to \mathbb{R}c:V(G)→R , find a stable set of maximum weight) as an optimization problem over an independence system: what are EEE and F\mathcal{F}F ?
E=V(G)\boldsymbol{E = V(G)}E=V(G) , F={F⊆E:F is stable in G}\ \boldsymbol{\mathcal{F} = \{F \subseteq E : F \text{ is stable in } G\}} F={F⊆E:F is stable in G} ; a Maximization Problem. A stable set is a set of pairwise nonadjacent vertices.
[Independence Systems and Matroids] The Shortest Path Problem (shortest sss - ttt -path in GGG with respect to edge weights ccc ) as an optimization problem over an independence system: what are EEE and F\mathcal{F}F ?
E=E(G)\boldsymbol{E = E(G)}E=E(G) , F={F⊆E:F is a subset of the edge set of an s-t-path}\ \boldsymbol{\mathcal{F} = \{F \subseteq E : F \text{ is a subset of the edge set of an } s\text{-}t\text{-path}\}} F={F⊆E:F is a subset of the edge set of an s-t-path} ; a Minimization Problem. The bases are exactly the edge sets of sss - ttt -paths (one sss - ttt -path's edge set can't properly contain another's).
[Independence Systems and Matroids] The Minimum Spanning Tree Problem ( GGG connected) and the Maximum-Weight Forest Problem as optimization problems over an independence system: what are EEE and F\mathcal{F}F ?
In both: E=E(G)\boldsymbol{E = E(G)}E=E(G) , F={F⊆E:(V(G),F) is a forest}\ \boldsymbol{\mathcal{F} = \{F \subseteq E : (V(G), F) \text{ is a forest}\}} F={F⊆E:(V(G),F) is a forest} . Spanning trees are the bases (for connected GGG ), so the Minimum Spanning Tree Problem is the Minimization Problem; the Maximum-Weight Forest Problem is the Maximization Problem.
[Independence Systems and Matroids] The Maximum-Weight Matching Problem as an optimization problem over an independence system: what are EEE and F\mathcal{F}F ?
E=E(G)\boldsymbol{E = E(G)}E=E(G) , F={F⊆E:F is a matching in G}\ \boldsymbol{\mathcal{F} = \{F \subseteq E : F \text{ is a matching in } G\}} F={F⊆E:F is a matching in G} ; a Maximization Problem.
[Independence Systems and Matroids] When is an independence system (E,F)(E, \mathcal{F})(E,F) a matroid?
(M3): if X,Y∈FX, Y \in \mathcal{F}X,Y∈F and ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ , then there is an x∈X∖Yx \in X \setminus Yx∈X∖Y with Y∪{x}∈FY \cup \{x\} \in \mathcal{F}Y∪{x}∈F . The exchange (or augmentation) property: a smaller independent set can always be grown from a larger one.
[Independence Systems and Matroids] EEE is the set of columns of a matrix AAA over a field KKK , and F\mathcal{F}F = the sets of columns that are linearly independent over KKK . What is (E,F)(E, \mathcal{F})(E,F) called?
The vector matroid of AAA . A matroid that is the vector matroid of some matrix over a field KKK (formally: isomorphic to one) is representable over KKK . (M3) is the linear algebra fact that a smaller independent set extends from a larger one.
[Independence Systems and Matroids] When are two matroids (E,F)(E, \mathcal{F})(E,F) and (E~,F~)(\tilde{E}, \tilde{\mathcal{F}})(E~,F~) isomorphic?
There is a bijection ϕ:E→E~\phi : E \to \tilde{E}ϕ:E→E~ such that XXX is independent if and only if {ϕ(x):x∈X}\{\phi(x) : x \in X\}{ϕ(x):x∈X} is independent, for every X⊆EX \subseteq EX⊆E .
[Independence Systems and Matroids] What is the cycle matroid of a graph GGG , and when is a matroid graphic?
Cycle matroid: E=E(G)E = E(G)E=E(G) , F={F⊆E:(V(G),F) is a forest}\mathcal{F} = \{F \subseteq E : (V(G), F) \text{ is a forest}\}F={F⊆E:(V(G),F) is a forest} . Graphic: (isomorphic to) the cycle matroid of some graph, loops allowed. The cycle matroid of GGG is written M(G)\mathcal{M}(G)M(G) . Its circuits are the edge sets of cycles.
[Independence Systems and Matroids] GGG is a graph, X,Y⊆E(G)X, Y \subseteq E(G)X,Y⊆E(G) are edge sets of forests with ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ . Why is there an e∈X∖Ye \in X \setminus Ye∈X∖Y with Y∪{e}Y \cup \{e\}Y∪{e} a forest?
(V(G),X)(V(G), X)(V(G),X) has fewer components than (V(G),Y)(V(G), Y)(V(G),Y) , so some component CCC of (V(G),X)(V(G), X)(V(G),X) meets two components of (V(G),Y)(V(G), Y)(V(G),Y) ; an edge eee of G[C]G[C]G[C] joining two of these components can be added to YYY without creating a cycle. A forest with edge set FFF has ∣V(G)∣−∣F∣|V(G)| - |F|∣V(G)∣−∣F∣ components. This shows forests form a matroid.
[Independence Systems and Matroids] EEE is a finite set and k∈Nk \in \mathbb{N}k∈N . What is (E,{F⊆E:∣F∣≤k})(E, \{F \subseteq E : |F| \le k\})(E,{F⊆E:∣F∣≤k}) called, and why does it satisfy (M3)?
A uniform matroid. (M3) is trivial: if ∣Y∣<∣X∣≤k|Y| < |X| \le k∣Y∣<∣X∣≤k , adding any element of X∖YX \setminus YX∖Y to YYY gives size ≤k\le k≤k . (M3): for independent X,YX, YX,Y with ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ there is x∈X∖Yx \in X \setminus Yx∈X∖Y with Y∪{x}Y \cup \{x\}Y∪{x} independent.
[Independence Systems and Matroids] GGG is a graph, SSS is a stable set in GGG , and ks∈Nk_s \in \mathbb{N}ks∈N for s∈Ss \in Ss∈S . δF(s)\delta_F(s)δF(s) denotes the edges of FFF incident with sss . Is F={F⊆E(G):∣δF(s)∣≤ks for all s∈S}\mathcal{F} = \{F \subseteq E(G) : |\delta_F(s)| \le k_s \text{ for all } s \in S\}F={F⊆E(G):∣δF(s)∣≤ks for all s∈S} a matroid on E(G)E(G)E(G) ?
Yes. Degree bounds at the vertices of a stable set.
[Independence Systems and Matroids] SSS is a stable set in a graph GGG , ks∈Nk_s \in \mathbb{N}ks∈N for s∈Ss \in Ss∈S , and F={F⊆E(G):∣δF(s)∣≤ks for all s∈S}\mathcal{F} = \{F \subseteq E(G) : |\delta_F(s)| \le k_s \text{ for all } s \in S\}F={F⊆E(G):∣δF(s)∣≤ks for all s∈S} ( δF(s)\delta_F(s)δF(s) : edges of FFF at sss ). X,Y∈FX, Y \in \mathcal{F}X,Y∈F with ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ . How do you find e∈X∖Ye \in X \setminus Ye∈X∖Y with Y∪{e}∈FY \cup \{e\} \in \mathcal{F}Y∪{e}∈F ?
Let S′={s∈S:∣δY(s)∣=ks}S' = \{s \in S : |\delta_Y(s)| = k_s\}S′={s∈S:∣δY(s)∣=ks} be the vertices where YYY is saturated; some e∈X∖Ye \in X \setminus Ye∈X∖Y is incident with no vertex of S′S'S′ , and this eee can be added. SSS stable makes the sets δ(s)\delta(s)δ(s) disjoint, so XXX has at most ∑s∈S′ks\sum_{s \in S'} k_s∑s∈S′ks edges at S′S'S′ , as many as YYY . Since ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ , XXX has more edges than YYY outside δ(S′)\delta(S')δ(S′) .
[Independence Systems and Matroids] F={F⊆E(G):∣δF(s)∣≤ks for all s∈S}\mathcal{F} = \{F \subseteq E(G) : |\delta_F(s)| \le k_s \text{ for all } s \in S\}F={F⊆E(G):∣δF(s)∣≤ks for all s∈S} is a matroid when SSS is a stable set of GGG .Give an example showing that it can fail to be a matroid when SSS is not stable.
Edges ua,uv,vbua, uv, vbua,uv,vb , S={u,v}S = \{u, v\}S={u,v} , ku=kv=1k_u = k_v = 1ku=kv=1 : X={ua,vb}X = \{ua, vb\}X={ua,vb} and Y={uv}Y = \{uv\}Y={uv} violate (M3). Adding uauaua or vbvbvb to YYY gives uuu or vvv two edges. The proof needs the sets δ(s)\delta(s)δ(s) , s∈Ss \in Ss∈S , to be disjoint.
[Independence Systems and Matroids] DDD is a digraph, S⊆V(D)S \subseteq V(D)S⊆V(D) , ks∈Nk_s \in \mathbb{N}ks∈N , and F={F⊆E(D):∣δF−(s)∣≤ks for all s∈S}\mathcal{F} = \{F \subseteq E(D) : |\delta^-_F(s)| \le k_s \text{ for all } s \in S\}F={F⊆E(D):∣δF−(s)∣≤ks for all s∈S} (indegree bounds). Why is this a matroid without requiring SSS to be stable?
Every arc enters exactly one vertex, so the sets δ−(s)\delta^-(s)δ−(s) are always disjoint. That disjointness is all the undirected proof (with SSS stable) used.
[Independence Systems and Matroids] (E,F)(E, \mathcal{F})(E,F) is an independence system. Besides (M3), state the two equivalent exchange conditions (M3') and (M3'').
(M3'): if X,Y∈FX, Y \in \mathcal{F}X,Y∈F and ∣X∣=∣Y∣+1|X| = |Y| + 1∣X∣=∣Y∣+1 , some x∈X∖Yx \in X \setminus Yx∈X∖Y has Y∪{x}∈FY \cup \{x\} \in \mathcal{F}Y∪{x}∈F . (M3''): for each X⊆EX \subseteq EX⊆E , all bases of XXX have the same cardinality. (M3): the same as (M3') but for any ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ .
[Independence Systems and Matroids] For an independence system, why does (M3'') “for each X⊆EX \subseteq EX⊆E , all bases of XXX have the same size” imply (M3) “if X,Y∈FX, Y \in \mathcal{F}X,Y∈F , ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ , some x∈X∖Yx \in X \setminus Yx∈X∖Y has Y∪{x}∈FY \cup \{x\} \in \mathcal{F}Y∪{x}∈F ”?
YYY can't be a basis of X∪YX \cup YX∪Y , since XXX is a larger independent subset of X∪YX \cup YX∪Y . So some x∈(X∪Y)∖Y=X∖Yx \in (X \cup Y) \setminus Y = X \setminus Yx∈(X∪Y)∖Y=X∖Y has Y∪{x}∈FY \cup \{x\} \in \mathcal{F}Y∪{x}∈F . Conversely (M3) gives (M3''): a smaller basis of XXX could be extended from a larger one, contradicting maximality.
[Independence Systems and Matroids] (E,F)(E, \mathcal{F})(E,F) is an independence system and X⊆EX \subseteq EX⊆E . What is the lower rank ρ(X)\rho(X)ρ(X) ?
ρ(X)=min{∣Y∣:Y is a basis of X}\boldsymbol{\rho(X) = \min\{|Y| : Y \text{ is a basis of } X\}}ρ(X)=min{∣Y∣:Y is a basis of X} The rank r(X)r(X)r(X) is the maximum size of a basis of XXX , so ρ(X)≤r(X)\rho(X) \le r(X)ρ(X)≤r(X) .
[Independence Systems and Matroids] What is the rank quotient q(E,F)q(E, \mathcal{F})q(E,F) of an independence system?
q(E,F)=minF⊆Eρ(F)r(F)\boldsymbol{q(E, \mathcal{F}) = \min_{F \subseteq E} \frac{\rho(F)}{r(F)}}q(E,F)=minF⊆Er(F)ρ(F) , with 00:=1\frac{0}{0} := 100:=1 . ρ(F)\rho(F)ρ(F) is the smallest and r(F)r(F)r(F) the largest size of a basis of FFF .
[Independence Systems and Matroids] What do you know about the rank quotient q(E,F)=minF⊆Eρ(F)/r(F)q(E, \mathcal{F}) = \min_{F \subseteq E} \rho(F) / r(F)q(E,F)=minF⊆Eρ(F)/r(F) of an independence system ( ρ\rhoρ : smallest basis size, rrr : largest), and when does equality hold?
q(E,F)≤1\boldsymbol{q(E, \mathcal{F}) \le 1}q(E,F)≤1 , with equality if and only if (E,F)(E, \mathcal{F})(E,F) is a matroid. ρ≤r\rho \le rρ≤r always; and q=1q = 1q=1 says that all bases of every FFF have the same size, which is (M3'').
[Independence Systems and Matroids] GGG is the path x−y−zx - y - zx−y−z and F\mathcal{F}F is the family of stable sets of GGG . What is the rank quotient q(V(G),F)q(V(G), \mathcal{F})q(V(G),F) ?
12\boldsymbol{\frac{1}{2}}21 F=V(G)F = V(G)F=V(G) has the bases {y}\{y\}{y} and {x,z}\{x, z\}{x,z} , so ρ(F)/r(F)=1/2\rho(F) / r(F) = 1/2ρ(F)/r(F)=1/2 ; no ratio is smaller, since every FFF has r(F)≤2r(F) \le 2r(F)≤2 and ρ(F)≥1\rho(F) \ge 1ρ(F)≥1 if F≠∅F \ne \emptysetF=∅ . In particular stable sets don't form a matroid.
[Independence Systems and Matroids] (E,F)(E, \mathcal{F})(E,F) is an independence system such that for every A∈FA \in \mathcal{F}A∈F and e∈Ee \in Ee∈E , the set A∪{e}A \cup \{e\}A∪{e} contains at most ppp circuits. What follows for the rank quotient q(E,F)q(E, \mathcal{F})q(E,F) ?
q(E,F)≥1p\boldsymbol{q(E, \mathcal{F}) \ge \frac{1}{p}}q(E,F)≥p1 q(E,F)=minFρ(F)/r(F)q(E, \mathcal{F}) = \min_F \rho(F) / r(F)q(E,F)=minFρ(F)/r(F) , the worst ratio of smallest to largest basis size.
[Independence Systems and Matroids] If every A∪{e}A \cup \{e\}A∪{e} ( A∈FA \in \mathcal{F}A∈F , e∈Ee \in Ee∈E ) contains at most ppp circuits, then q(E,F)≥1pq(E, \mathcal{F}) \ge \frac{1}{p}q(E,F)≥p1 . J,KJ, KJ,K are bases of some F⊆EF \subseteq EF⊆E , and J∖K={e1,…,et}J \setminus K = \{e_1, \dots, e_t\}J∖K={e1,…,et} . Which sequence of sets does the proof build, and how?
Independent sets K=K0,K1,…,KtK = K_0, K_1, \dots, K_tK=K0,K1,…,Kt : Ki+1=(Ki∖X)∪{ei+1}K_{i+1} = (K_i \setminus X) \cup \{e_{i+1}\}Ki+1=(Ki∖X)∪{ei+1} , where X⊆Ki∖JX \subseteq K_i \setminus JX⊆Ki∖J , ∣X∣≤p|X| \le p∣X∣≤p , contains one element of each circuit in Ki∪{ei+1}K_i \cup \{e_{i+1}\}Ki∪{ei+1} . Each circuit of Ki∪{ei+1}K_i \cup \{e_{i+1}\}Ki∪{ei+1} meets Ki∖JK_i \setminus JKi∖J : otherwise it would lie inside the independent set JJJ . All KiK_iKi keep J∩KJ \cap KJ∩K and the e…
[Independence Systems and Matroids] If every A∪{e}A \cup \{e\}A∪{e} ( A∈FA \in \mathcal{F}A∈F , e∈Ee \in Ee∈E ) contains at most ppp circuits, then q(E,F)≥1pq(E, \mathcal{F}) \ge \frac{1}{p}q(E,F)≥p1 . Proof: for bases J,KJ, KJ,K of FFF with J∖K={e1,…,et}J \setminus K = \{e_1, \dots, e_t\}J∖K={e1,…,et} , build independent K=K0,…,KtK = K_0, \dots, K_tK=K0,…,Kt , where KiK_iKi is Ki−1K_{i-1}Ki−1 plus eie_iei minus at most ppp elements of Ki−1∖JK_{i-1} \setminus JKi−1∖J .How does the proo…
J⊆KtJ \subseteq K_tJ⊆Kt , and JJJ is a basis of FFF , so J=KtJ = K_tJ=Kt : every element of K∖JK \setminus JK∖J was removed, at most ppp per step, so ∣K∖J∣≤pt=p∣J∖K∣|K \setminus J| \le pt = p|J \setminus K|∣K∖J∣≤pt=p∣J∖K∣ . Then ∣K∣=∣K∩J∣+∣K∖J∣≤∣K∩J∣+p∣J∖K∣≤p∣J∣|K| = |K \cap J| + |K \setminus J| \le |K \cap J| + p|J \setminus K| \le p|J|∣K∣=∣K∩J∣+∣K∖J∣≤∣K∩J∣+p∣J∖K∣≤p∣J∣ .
[Independence Systems and Matroids] State the basis axioms: when is B⊆2E\mathcal{B} \subseteq 2^EB⊆2E ( EEE finite, nonempty) the set of bases of some matroid on EEE ?
(B1) B≠∅\mathcal{B} \ne \emptysetB=∅ ; (B2) for B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B and x∈B1∖B2x \in B_1 \setminus B_2x∈B1∖B2 , there is y∈B2∖B1y \in B_2 \setminus B_1y∈B2∖B1 with (B1∖{x})∪{y}∈B(B_1 \setminus \{x\}) \cup \{y\} \in \mathcal{B}(B1∖{x})∪{y}∈B .
[Independence Systems and Matroids] Why do the bases of a matroid satisfy (B2): for bases B1,B2B_1, B_2B1,B2 and x∈B1∖B2x \in B_1 \setminus B_2x∈B1∖B2 there is y∈B2∖B1y \in B_2 \setminus B_1y∈B2∖B1 with (B1∖{x})∪{y}(B_1 \setminus \{x\}) \cup \{y\}(B1∖{x})∪{y} a basis?
∣B2∣>∣B1∖{x}∣|B_2| > |B_1 \setminus \{x\}|∣B2∣>∣B1∖{x}∣ , so (M3) adds some y∈B2∖B1y \in B_2 \setminus B_1y∈B2∖B1 to B1∖{x}B_1 \setminus \{x\}B1∖{x} , and the result is a basis because all bases have the same size.
[Independence Systems and Matroids] B⊆2E\mathcal{B} \subseteq 2^EB⊆2E satisfies (B1) B≠∅\mathcal{B} \ne \emptysetB=∅ and (B2) for B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B , x∈B1∖B2x \in B_1 \setminus B_2x∈B1∖B2 , some y∈B2∖B1y \in B_2 \setminus B_1y∈B2∖B1 has (B1∖{x})∪{y}∈B(B_1 \setminus \{x\}) \cup \{y\} \in \mathcal{B}(B1∖{x})∪{y}∈B .Why do all members of B\mathcal{B}B have the same size?
Take B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B with ∣B1∣>∣B2∣|B_1| > |B_2|∣B1∣>∣B2∣ and ∣B1∩B2∣|B_1 \cap B_2|∣B1∩B2∣ maximum; exchanging x∈B1∖B2x \in B_1 \setminus B_2x∈B1∖B2 by (B2) gives B1′B_1'B1′ with ∣B1′∣=∣B1∣|B_1'| = |B_1|∣B1′∣=∣B1∣ and a larger intersection with B2B_2B2 . Contradiction. B1∖B2≠∅B_1 \setminus B_2 \ne \emptysetB1∖B2=∅ because ∣B1∣>∣B2∣|B_1| > |B_2|∣B1∣>∣B2∣ , and the new element yyy lies in B2B_2B2 .
[Independence Systems and Matroids] B⊆2E\mathcal{B} \subseteq 2^EB⊆2E satisfies (B1) B≠∅\mathcal{B} \ne \emptysetB=∅ and (B2) for B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B , x∈B1∖B2x \in B_1 \setminus B_2x∈B1∖B2 , some y∈B2∖B1y \in B_2 \setminus B_1y∈B2∖B1 has (B1∖{x})∪{y}∈B(B_1 \setminus \{x\}) \cup \{y\} \in \mathcal{B}(B1∖{x})∪{y}∈B .Which independence system has B\mathcal{B}B as its bases, and how does the proof get (M3)?
F={F⊆E:F⊆B for some B∈B}\mathcal{F} = \{F \subseteq E : F \subseteq B \text{ for some } B \in \mathcal{B}\}F={F⊆E:F⊆B for some B∈B} . For X⊆B1X \subseteq B_1X⊆B1 , Y⊆B2Y \subseteq B_2Y⊆B2 , ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ , with ∣B1∩B2∣|B_1 \cap B_2|∣B1∩B2∣ maximum: B2B_2B2 meets X∖YX \setminus YX∖Y , and any yyy there has Y∪{y}⊆B2Y \cup \{y\} \subseteq B_2Y∪{y}⊆B2 . If B2∩(X∖Y)=∅B_2 \cap (X \setminus Y) = \emptysetB2∩(X∖Y)=∅ , counting gives an element of (B2∖B1)∖Y(B_2 \setminus B_1) \setminus…
[Independence Systems and Matroids] State the rank axioms (R1)–(R3): when is r:2E→Nr : 2^E \to \mathbb{N}r:2E→N the rank function of a matroid?
For all X,Y⊆EX, Y \subseteq EX,Y⊆E : (R1) r(X)≤∣X∣r(X) \le |X|r(X)≤∣X∣ ; (R2) X⊆Y⇒r(X)≤r(Y)X \subseteq Y \Rightarrow r(X) \le r(Y)X⊆Y⇒r(X)≤r(Y) ; (R3) r(X∪Y)+r(X∩Y)≤r(X)+r(Y)r(X \cup Y) + r(X \cap Y) \le r(X) + r(Y)r(X∪Y)+r(X∩Y)≤r(X)+r(Y) .
[Independence Systems and Matroids] A function r:2E→Nr : 2^E \to \mathbb{N}r:2E→N with r(X∪Y)+r(X∩Y)≤r(X)+r(Y)r(X \cup Y) + r(X \cap Y) \le r(X) + r(Y)r(X∪Y)+r(X∩Y)≤r(X)+r(Y) for all X,Y⊆EX, Y \subseteq EX,Y⊆E is called submodular.
Rank functions of matroids are submodular; rank functions of general independence systems need not be.
[Independence Systems and Matroids] State the local rank axioms (R1')–(R3'), which (like (R1)–(R3)) characterize rank functions r:2E→Nr : 2^E \to \mathbb{N}r:2E→N of matroids.
(R1') r(∅)≤0r(\emptyset) \le 0r(∅)≤0 ; (R2') r(X)≤r(X∪{x})≤r(X)+1r(X) \le r(X \cup \{x\}) \le r(X) + 1r(X)≤r(X∪{x})≤r(X)+1 ; (R3') if r(X∪{x})=r(X∪{y})=r(X)r(X \cup \{x\}) = r(X \cup \{y\}) = r(X)r(X∪{x})=r(X∪{y})=r(X) then r(X∪{x,y})=r(X)r(X \cup \{x, y\}) = r(X)r(X∪{x,y})=r(X) .
[Independence Systems and Matroids] rrr is the rank function of a matroid. How does the proof show submodularity r(X∪Y)+r(X∩Y)≤r(X)+r(Y)r(X \cup Y) + r(X \cap Y) \le r(X) + r(Y)r(X∪Y)+r(X∩Y)≤r(X)+r(Y) ?
Extend a basis AAA of X∩YX \cap YX∩Y to a basis A∪˙BA \mathbin{\dot\cup} BA∪˙B of XXX , then to a basis A∪˙B∪˙CA \mathbin{\dot\cup} B \mathbin{\dot\cup} CA∪˙B∪˙C of X∪YX \cup YX∪Y ; then A∪C⊆YA \cup C \subseteq YA∪C⊆Y is independent. r(X)+r(Y)≥∣A∪B∣+∣A∪C∣=∣A∪B∪C∣+∣A∣=r(X∪Y)+r(X∩Y)r(X) + r(Y) \ge |A \cup B| + |A \cup C| = |A \cup B \cup C| + |A| = r(X \cup Y) + r(X \cap Y)r(X)+r(Y)≥∣A∪B∣+∣A∪C∣=∣A∪B∪C∣+∣A∣=r(X∪Y)+r(X∩Y) . Extending uses (M3).
[Independence Systems and Matroids] r:2E→Nr : 2^E \to \mathbb{N}r:2E→N satisfies (R1) r(X)≤∣X∣r(X) \le |X|r(X)≤∣X∣ , (R2) monotonicity and (R3) submodularity. Why does r(X∪{y})≤r(X)+1r(X \cup \{y\}) \le r(X) + 1r(X∪{y})≤r(X)+1 hold?
r(X∪{y})≤r(X)+r({y})−r(X∩{y})≤r(X)+r({y})≤r(X)+1\boldsymbol{r(X \cup \{y\}) \le r(X) + r(\{y\}) - r(X \cap \{y\}) \le r(X) + r(\{y\}) \le r(X) + 1}r(X∪{y})≤r(X)+r({y})−r(X∩{y})≤r(X)+r({y})≤r(X)+1 Submodularity with the sets XXX and {y}\{y\}{y} , then (R1) for {y}\{y\}{y} .
[Independence Systems and Matroids] r:2E→Nr : 2^E \to \mathbb{N}r:2E→N is monotone and submodular, and r(X∪{x})=r(X∪{y})=r(X)r(X \cup \{x\}) = r(X \cup \{y\}) = r(X)r(X∪{x})=r(X∪{y})=r(X) . Why is r(X∪{x,y})=r(X)r(X \cup \{x, y\}) = r(X)r(X∪{x,y})=r(X) ?
2r(X)≤r(X)+r(X∪{x,y})≤r(X∪{x})+r(X∪{y})=2r(X)\boldsymbol{2r(X) \le r(X) + r(X \cup \{x, y\}) \le r(X \cup \{x\}) + r(X \cup \{y\}) = 2r(X)}2r(X)≤r(X)+r(X∪{x,y})≤r(X∪{x})+r(X∪{y})=2r(X) Monotonicity, then submodularity for X∪{x}X \cup \{x\}X∪{x} and X∪{y}X \cup \{y\}X∪{y} (union X∪{x,y}X \cup \{x, y\}X∪{x,y} , intersection XXX when x≠yx \ne yx=y ).
[Independence Systems and Matroids] r:2E→Nr : 2^E \to \mathbb{N}r:2E→N satisfies (R1') r(∅)≤0r(\emptyset) \le 0r(∅)≤0 , (R2') r(X)≤r(X∪{x})≤r(X)+1r(X) \le r(X \cup \{x\}) \le r(X) + 1r(X)≤r(X∪{x})≤r(X)+1 and (R3'). Which matroid has rrr as its rank function?
F={F⊆E:r(F)=∣F∣}\boldsymbol{\mathcal{F} = \{F \subseteq E : r(F) = |F|\}}F={F⊆E:r(F)=∣F∣} (M1) from r(∅)=0r(\emptyset) = 0r(∅)=0 ; (M2) because by (R2') removing an element lowers rrr by at most 1 while r(X)≤∣X∣r(X) \le |X|r(X)≤∣X∣ . Finally, for a maximum Y⊆XY \subseteq XY⊆X with r(Y)=∣Y∣r(Y) = |Y|r(Y)=∣Y∣ , every x∈X∖Yx \in X \setminus Yx∈X∖Y has r(Y∪{x})=r(Y)r(Y \cup \{x\}) = r(Y)r(Y∪{x})=r(Y) , and (R3') repeatedly gives r(X)=∣Y∣r(X) = |Y|r(X)=∣Y∣ .
[Independence Systems and Matroids] rrr satisfies (R2') r(X)≤r(X∪{x})≤r(X)+1r(X) \le r(X \cup \{x\}) \le r(X) + 1r(X)≤r(X∪{x})≤r(X)+1 and (R3') if r(X∪{x})=r(X∪{y})=r(X)r(X \cup \{x\}) = r(X \cup \{y\}) = r(X)r(X∪{x})=r(X∪{y})=r(X) then r(X∪{x,y})=r(X)r(X \cup \{x, y\}) = r(X)r(X∪{x,y})=r(X) . F={F:r(F)=∣F∣}\mathcal{F} = \{F : r(F) = |F|\}F={F:r(F)=∣F∣} .Why does F\mathcal{F}F satisfy (M3'): for X,Y∈FX, Y \in \mathcal{F}X,Y∈F with ∣X∣=∣Y∣+1|X| = |Y| + 1∣X∣=∣Y∣+1 , some x∈X∖Yx \in X \setminus Yx…
Otherwise r(Y∪{xi})=r(Y)r(Y \cup \{x_i\}) = r(Y)r(Y∪{xi})=r(Y) for every xi∈X∖Yx_i \in X \setminus Yxi∈X∖Y , and (R3') repeatedly gives r(X∪Y)=r(Y)=∣Y∣<∣X∣=r(X)r(X \cup Y) = r(Y) = |Y| < |X| = r(X)r(X∪Y)=r(Y)=∣Y∣<∣X∣=r(X) , contradicting monotonicity.
[Independence Systems and Matroids] State the closure axioms (S1)–(S4): when is σ:2E→2E\sigma : 2^E \to 2^Eσ:2E→2E the closure operator of a matroid? (For all X,Y⊆EX, Y \subseteq EX,Y⊆E , x,y∈Ex, y \in Ex,y∈E .)
(S1) X⊆σ(X)X \subseteq \sigma(X)X⊆σ(X) ; (S2) X⊆Y⇒σ(X)⊆σ(Y)X \subseteq Y \Rightarrow \sigma(X) \subseteq \sigma(Y)X⊆Y⇒σ(X)⊆σ(Y) ; (S3) σ(X)=σ(σ(X))\sigma(X) = \sigma(\sigma(X))σ(X)=σ(σ(X)) ; (S4) if y∉σ(X)y \notin \sigma(X)y∈/σ(X) and y∈σ(X∪{x})y \in \sigma(X \cup \{x\})y∈σ(X∪{x}) then x∈σ(X∪{y})x \in \sigma(X \cup \{y\})x∈σ(X∪{y}) . (S4) is the exchange property of the closure. Closure: σ(X)={y:r(X∪{y})=r(X)}\sigma(X) = \{y : r(X \cup \{y\}) = r(X)\}σ(X)={y:r(X∪{y})=r(X)} .
[Independence Systems and Matroids] rrr is the rank function of a matroid and σ(X)={y:r(X∪{y})=r(X)}\sigma(X) = \{y : r(X \cup \{y\}) = r(X)\}σ(X)={y:r(X∪{y})=r(X)} . Why is σ\sigmaσ monotone: X⊆YX \subseteq YX⊆Y implies σ(X)⊆σ(Y)\sigma(X) \subseteq \sigma(Y)σ(X)⊆σ(Y) ?
Submodularity: for z∈σ(X)z \in \sigma(X)z∈σ(X) , r(X)+r(Y)=r(X∪{z})+r(Y)≥r((X∪{z})∩Y)+r(Y∪{z})≥r(X)+r(Y∪{z})\ r(X) + r(Y) = r(X \cup \{z\}) + r(Y) \ge r((X \cup \{z\}) \cap Y) + r(Y \cup \{z\}) \ge r(X) + r(Y \cup \{z\}) r(X)+r(Y)=r(X∪{z})+r(Y)≥r((X∪{z})∩Y)+r(Y∪{z})≥r(X)+r(Y∪{z}) . So r(Y∪{z})≤r(Y)r(Y \cup \{z\}) \le r(Y)r(Y∪{z})≤r(Y) , i.e. z∈σ(Y)z \in \sigma(Y)z∈σ(Y) . The last step uses X⊆(X∪{z})∩YX \subseteq (X \cup \{z\}) \cap YX⊆(X∪{z})∩Y and monotonicity.
[Independence Systems and Matroids] In a matroid with rank rrr and closure σ(X)={y:r(X∪{y})=r(X)}\sigma(X) = \{y : r(X \cup \{y\}) = r(X)\}σ(X)={y:r(X∪{y})=r(X)} : why is r(σ(X))=r(X)r(\sigma(X)) = r(X)r(σ(X))=r(X) , and why does that give σ(σ(X))=σ(X)\sigma(\sigma(X)) = \sigma(X)σ(σ(X))=σ(X) ?
Adding the elements of σ(X)\sigma(X)σ(X) one at a time never raises the rank (by (R3'), two non-raising elements together don't raise it). So for x∈σ(σ(X))x \in \sigma(\sigma(X))x∈σ(σ(X)) : r(X)≤r(X∪{x})≤r(σ(X)∪{x})=r(σ(X))=r(X)r(X) \le r(X \cup \{x\}) \le r(\sigma(X) \cup \{x\}) = r(\sigma(X)) = r(X)r(X)≤r(X∪{x})≤r(σ(X)∪{x})=r(σ(X))=r(X) . (R3'): if r(X∪{x})=r(X∪{y})=r(X)r(X \cup \{x\}) = r(X \cup \{y\}) = r(X)r(X∪{x})=r(X∪{y})=r(X) then r(X∪{x,y})=r(X)r(X \cup \{x, y\}) = r(X)r(X∪{x,y})=r(X) .
[Independence Systems and Matroids] Why does the closure of a matroid satisfy (S4): if y∉σ(X)y \notin \sigma(X)y∈/σ(X) and y∈σ(X∪{x})y \in \sigma(X \cup \{x\})y∈σ(X∪{x}) , then x∈σ(X∪{y})x \in \sigma(X \cup \{y\})x∈σ(X∪{y}) ?
Otherwise r(X∪{x})=r(X∪{x,y})=r(X∪{y})+1=r(X)+2r(X \cup \{x\}) = r(X \cup \{x, y\}) = r(X \cup \{y\}) + 1 = r(X) + 2r(X∪{x})=r(X∪{x,y})=r(X∪{y})+1=r(X)+2 , but adding one element raises the rank by at most 1. The three hypotheses give, in turn: r(X∪{y})=r(X)+1r(X \cup \{y\}) = r(X) + 1r(X∪{y})=r(X)+1 , r(X∪{x,y})=r(X∪{x})r(X \cup \{x, y\}) = r(X \cup \{x\})r(X∪{x,y})=r(X∪{x}) , r(X∪{x,y})=r(X∪{y})+1r(X \cup \{x, y\}) = r(X \cup \{y\}) + 1r(X∪{x,y})=r(X∪{y})+1 .
[Independence Systems and Matroids] σ:2E→2E\sigma : 2^E \to 2^Eσ:2E→2E satisfies the closure axioms (S1)–(S4).Which independent sets define the matroid whose closure operator is σ\sigmaσ ?
F={X⊆E:x∉σ(X∖{x}) for all x∈X}\boldsymbol{\mathcal{F} = \{X \subseteq E : x \notin \sigma(X \setminus \{x\}) \text{ for all } x \in X\}}F={X⊆E:x∈/σ(X∖{x}) for all x∈X} No element of XXX is spanned by the rest. The proof shows this is a matroid and then that its closure operator equals σ\sigmaσ .
[Independence Systems and Matroids] σ\sigmaσ satisfies (S1)–(S4) and F={X:x∉σ(X∖{x}) ∀x∈X}\mathcal{F} = \{X : x \notin \sigma(X \setminus \{x\}) \ \forall x \in X\}F={X:x∈/σ(X∖{x}) ∀x∈X} .Which claim is the key step for (M3), and how is it proved?
Claim: if X∈FX \in \mathcal{F}X∈F and ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ , then X⊈σ(Y)X \not\subseteq \sigma(Y)X⊆σ(Y) . By induction on ∣Y∖X∣|Y \setminus X|∣Y∖X∣ . Base: Y⊊XY \subsetneq XY⊊X , and any x∈X∖Yx \in X \setminus Yx∈X∖Y has x∉σ(X∖{x})⊇σ(Y)x \notin \sigma(X \setminus \{x\}) \supseteq \sigma(Y)x∈/σ(X∖{x})⊇σ(Y) . Step: for y∈Y∖Xy \in Y \setminus Xy∈Y∖X , induction gives x∈X∖σ(Y∖{y})x \in X \setminus \sigma(Y \setminus \{y\})x∈X∖σ(Y∖{y}) ; if x∈σ(Y)x \in \sigma(Y)x∈σ(Y) , (S4) gives σ(Y)⊆σ((Y∖{y}…
[Independence Systems and Matroids] σ\sigmaσ satisfies (S1)–(S4), F={X:x∉σ(X∖{x}) ∀x∈X}\mathcal{F} = \{X : x \notin \sigma(X \setminus \{x\}) \ \forall x \in X\}F={X:x∈/σ(X∖{x}) ∀x∈X} , and if X∈FX \in \mathcal{F}X∈F , ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ then X⊈σ(Y)X \not\subseteq \sigma(Y)X⊆σ(Y) . X,Y∈FX, Y \in \mathcal{F}X,Y∈F with ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ . Which element can be added to YYY , and why does the result lie in F\mathcal{F}F ?
Any x∈X∖σ(Y)x \in X \setminus \sigma(Y)x∈X∖σ(Y) . For z∈Yz \in Yz∈Y : z∉σ(Y∖{z})z \notin \sigma(Y \setminus \{z\})z∈/σ(Y∖{z}) and x∉σ(Y)x \notin \sigma(Y)x∈/σ(Y) , so by (S4) z∉σ((Y∖{z})∪{x})z \notin \sigma((Y \setminus \{z\}) \cup \{x\})z∈/σ((Y∖{z})∪{x}) . For z=xz = xz=x : x∉σ(Y)x \notin \sigma(Y)x∈/σ(Y) by choice. (S4): if y∉σ(X)y \notin \sigma(X)y∈/σ(X) and y∈σ(X∪{x})y \in \sigma(X \cup \{x\})y∈σ(X∪{x}) then x∈σ(X∪{y})x \in \sigma(X \cup \{y\})x∈σ(X∪{y}) .
[Independence Systems and Matroids] When is a family C⊆2E\mathcal{C} \subseteq 2^EC⊆2E the set of circuits of an independence system (namely of F={F:no C∈C has C⊆F}\mathcal{F} = \{F : \text{no } C \in \mathcal{C} \text{ has } C \subseteq F\}F={F:no C∈C has C⊆F} )?
(C1) ∅∉C\emptyset \notin \mathcal{C}∅∈/C ; (C2) C1⊆C2C_1 \subseteq C_2C1⊆C2 for C1,C2∈CC_1, C_2 \in \mathcal{C}C1,C2∈C implies C1=C2C_1 = C_2C1=C2 . (C1) makes ∅\emptyset∅ independent; (C2) makes every member of C\mathcal{C}C a minimal dependent set.
[Independence Systems and Matroids] C\mathcal{C}C is the set of circuits of an independence system (E,F)(E, \mathcal{F})(E,F) . When is (E,F)(E, \mathcal{F})(E,F) a matroid, in terms of a set X∈FX \in \mathcal{F}X∈F and an element e∈Ee \in Ee∈E ?
If and only if X∪{e}X \cup \{e\}X∪{e} contains at most one circuit, for every X∈FX \in \mathcal{F}X∈F and e∈Ee \in Ee∈E . ⇐\Leftarrow⇐ is the rank-quotient bound with p=1p = 1p=1 : then q(E,F)≥1q(E, \mathcal{F}) \ge 1q(E,F)≥1 , and q=1q = 1q=1 means matroid.
[Independence Systems and Matroids] State the circuit elimination axiom (C3), and its strong form (C3'), for the circuits C\mathcal{C}C of a matroid.
(C3): for C1≠C2C_1 \ne C_2C1=C2 in C\mathcal{C}C and e∈C1∩C2e \in C_1 \cap C_2e∈C1∩C2 , some C3∈CC_3 \in \mathcal{C}C3∈C has C3⊆(C1∪C2)∖{e}C_3 \subseteq (C_1 \cup C_2) \setminus \{e\}C3⊆(C1∪C2)∖{e} . (C3'): moreover, for any given f∈C1∖C2f \in C_1 \setminus C_2f∈C1∖C2 , such a C3C_3C3 exists with f∈C3f \in C_3f∈C3 . For the circuits of an independence system, each of (C3), (C3') is equivalent to being a matroid.
[Independence Systems and Matroids] C1≠C2C_1 \ne C_2C1=C2 are circuits of a matroid with rank rrr , e∈C1∩C2e \in C_1 \cap C_2e∈C1∩C2 and f∈C1∖C2f \in C_1 \setminus C_2f∈C1∖C2 . How does the proof find a circuit C3C_3C3 with f∈C3⊆(C1∪C2)∖{e}f \in C_3 \subseteq (C_1 \cup C_2) \setminus \{e\}f∈C3⊆(C1∪C2)∖{e} ?
Submodularity (twice) gives r((C1∪C2)∖{e,f})=r(C1∪C2)r((C_1 \cup C_2) \setminus \{e, f\}) = r(C_1 \cup C_2)r((C1∪C2)∖{e,f})=r(C1∪C2) , so a basis BBB of (C1∪C2)∖{e,f}(C_1 \cup C_2) \setminus \{e, f\}(C1∪C2)∖{e,f} is a basis of C1∪C2C_1 \cup C_2C1∪C2 , and B∪{f}B \cup \{f\}B∪{f} contains a circuit C3C_3C3 , which must contain fff . The rank computation uses r(C)=r(C∖{x})=∣C∣−1r(C) = r(C \setminus \{x\}) = |C| - 1r(C)=r(C∖{x})=∣C∣−1 for a circuit CCC .
[Independence Systems and Matroids] Why does circuit elimination (for C1≠C2C_1 \ne C_2C1=C2 and e∈C1∩C2e \in C_1 \cap C_2e∈C1∩C2 some circuit lies in (C1∪C2)∖{e}(C_1 \cup C_2) \setminus \{e\}(C1∪C2)∖{e} ) imply that X∪{e}X \cup \{e\}X∪{e} contains at most one circuit for XXX independent?
Two circuits C1,C2C_1, C_2C1,C2 in X∪{e}X \cup \{e\}X∪{e} both contain eee , so elimination gives a circuit inside (C1∪C2)∖{e}⊆X(C_1 \cup C_2) \setminus \{e\} \subseteq X(C1∪C2)∖{e}⊆X , contradicting independence of XXX .
[Independence Systems and Matroids] (E,F)(E, \mathcal{F})(E,F) is a matroid, X∈FX \in \mathcal{F}X∈F , e∈Ee \in Ee∈E . What does C(X,e)C(X, e)C(X,e) denote?
The unique circuit in X∪{e}X \cup \{e\}X∪{e} if X∪{e}∉FX \cup \{e\} \notin \mathcal{F}X∪{e}∈/F ; C(X,e)=∅C(X, e) = \emptysetC(X,e)=∅ if X∪{e}∈FX \cup \{e\} \in \mathcal{F}X∪{e}∈F . Unique because in a matroid X∪{e}X \cup \{e\}X∪{e} contains at most one circuit. It contains eee .
[Dual Independence Systems] What is the dual (E,F∗)(E, \mathcal{F}^*)(E,F∗) of an independence system (E,F)(E, \mathcal{F})(E,F) ?
F∗={F⊆E:some basis B of (E,F) has F∩B=∅}\boldsymbol{\mathcal{F}^* = \{F \subseteq E : \text{some basis } B \text{ of } (E, \mathcal{F}) \text{ has } F \cap B = \emptyset\}}F∗={F⊆E:some basis B of (E,F) has F∩B=∅} The sets avoiding some basis, i.e. contained in the complement of a basis. (E,F∗)(E, \mathcal{F}^*)(E,F∗) is again an independence system.
[Dual Independence Systems] (E,F)(E, \mathcal{F})(E,F) is an independence system. What are the bases of its dual (E,F∗)(E, \mathcal{F}^*)(E,F∗) ?
The complements E∖BE \setminus BE∖B of the bases BBB of (E,F)(E, \mathcal{F})(E,F) . F∈F∗F \in \mathcal{F}^*F∈F∗ means F⊆E∖BF \subseteq E \setminus BF⊆E∖B for a basis BBB ; and E∖B⊆E∖B′E \setminus B \subseteq E \setminus B'E∖B⊆E∖B′ forces B′⊆BB' \subseteq BB′⊆B , so B′=BB' = BB′=B .
[Dual Independence Systems] What is (E,F∗∗)(E, \mathcal{F}^{**})(E,F∗∗) , the dual of the dual of an independence system (E,F)(E, \mathcal{F})(E,F) , and why?
(E,F∗∗)=(E,F)\boldsymbol{(E, \mathcal{F}^{**}) = (E, \mathcal{F})}(E,F∗∗)=(E,F) F∈F∗∗F \in \mathcal{F}^{**}F∈F∗∗ ⇔\Leftrightarrow⇔ FFF misses a basis B∗B^*B∗ of F∗\mathcal{F}^*F∗ ⇔\Leftrightarrow⇔ FFF misses E∖BE \setminus BE∖B for a basis BBB of F\mathcal{F}F ⇔\Leftrightarrow⇔ F⊆BF \subseteq BF⊆B ⇔\Leftrightarrow⇔ F∈FF \in \mathcal{F}F∈F .
[Dual Independence Systems] (E,F)(E, \mathcal{F})(E,F) is a matroid with rank function rrr . Is its dual a matroid, and what is the dual's rank function r∗r^*r∗ ?
Yes (and conversely), and r∗(F)=∣F∣+r(E∖F)−r(E)\boldsymbol{r^*(F) = |F| + r(E \setminus F) - r(E)}r∗(F)=∣F∣+r(E∖F)−r(E) .
[Dual Independence Systems] (E,F)(E, \mathcal{F})(E,F) is a matroid with rank rrr , and q(F)=∣F∣+r(E∖F)−r(E)q(F) = |F| + r(E \setminus F) - r(E)q(F)=∣F∣+r(E∖F)−r(E) .How does the proof show that the dual (E,F∗)(E, \mathcal{F}^*)(E,F∗) is a matroid with rank function qqq ?
qqq satisfies the rank axioms (R1)–(R3), so it is the rank function of a matroid, whose independent sets are {F:q(F)=∣F∣}\{F : q(F) = |F|\}{F:q(F)=∣F∣} ; and q(F)=∣F∣ ⟺ r(E∖F)=r(E) ⟺ F∈F∗q(F) = |F| \iff r(E \setminus F) = r(E) \iff F \in \mathcal{F}^*q(F)=∣F∣⟺r(E∖F)=r(E)⟺F∈F∗ . r(E∖F)=r(E)r(E \setminus F) = r(E)r(E∖F)=r(E) means E∖FE \setminus FE∖F contains a basis, i.e. FFF misses a basis. Submodularity of qqq follows from that of rrr applied to E∖XE \setminus XE∖X and E∖YE \setminus YE∖Y .
[Dual Independence Systems] EEE has nnn elements and F={F⊆E:∣F∣≤k}\mathcal{F} = \{F \subseteq E : |F| \le k\}F={F⊆E:∣F∣≤k} (a uniform matroid, k≤nk \le nk≤n ). What is its dual?
The uniform matroid {F⊆E:∣F∣≤n−k}\{F \subseteq E : |F| \le n - k\}{F⊆E:∣F∣≤n−k} . The bases are the kkk -sets, so the dual's bases are their complements, the (n−k)(n-k)(n−k) -sets.
[Dual Independence Systems] GGG is a connected planar graph with planar dual G∗G^*G∗ (for some embedding), and M(⋅)\mathcal{M}(\cdot)M(⋅) is the cycle matroid (edge sets of forests). How are M(G∗)\mathcal{M}(G^*)M(G∗) and M(G)\mathcal{M}(G)M(G) related?
M(G∗)=(M(G))∗\boldsymbol{\mathcal{M}(G^*) = (\mathcal{M}(G))^*}M(G∗)=(M(G))∗ , the dual matroid. Identifying each edge with its dual edge: the complement of a spanning tree of GGG corresponds to a spanning tree of G∗G^*G∗ , so bases of M(G∗)\mathcal{M}(G^*)M(G∗) are complements of bases of M(G)\mathcal{M}(G)M(G) .
[Dual Independence Systems] Is the dual of a graphic matroid always graphic?
No: the dual of the cycle matroid of GGG is graphic only if GGG is planar. e.g. the duals of the cycle matroids of K5K_5K5 and K3,3K_{3,3}K3,3 are not graphic.
[Dual Independence Systems] GGG is a connected planar graph with nnn vertices, mmm edges and fff faces; rrr is the rank of its cycle matroid and r∗r^*r∗ the dual's rank, r∗(F)=∣F∣+r(E∖F)−r(E)r^*(F) = |F| + r(E \setminus F) - r(E)r∗(F)=∣F∣+r(E∖F)−r(E) . How does this give Euler's formula?
f−1=r∗(E(G))=m+r(∅)−r(E(G))=m−n+1\boldsymbol{f - 1 = r^*(E(G)) = m + r(\emptyset) - r(E(G)) = m - n + 1}f−1=r∗(E(G))=m+r(∅)−r(E(G))=m−n+1 r∗(E(G))r^*(E(G))r∗(E(G)) is the size of a spanning tree of the dual G∗G^*G∗ , which has fff vertices; r(E(G))=n−1r(E(G)) = n - 1r(E(G))=n−1 . So n−m+f=2n - m + f = 2n−m+f=2 .
[The Greedy Algorithm] An oracle that decides, for a given F⊆EF \subseteq EF⊆E , whether F∈FF \in \mathcal{F}F∈F is called an independence oracle.
[The Greedy Algorithm] State the Best-In-Greedy Algorithm (input: independence system (E,F)(E, \mathcal{F})(E,F) given by an independence oracle, weights c:E→R≥0c : E \to \mathbb{R}_{\ge 0}c:E→R≥0 ).
Sort c(e1)≥⋯≥c(en)c(e_1) \ge \dots \ge c(e_n)c(e1)≥⋯≥c(en) ; start with F=∅F = \emptysetF=∅ ; for i=1,…,ni = 1, \dots, ni=1,…,n , add eie_iei to FFF if F∪{ei}∈FF \cup \{e_i\} \in \mathcal{F}F∪{ei}∈F . For the Maximization Problem: try the heaviest elements first.
[The Greedy Algorithm] Why is the output of the Best-In-Greedy Algorithm a basis of EEE , and more precisely, why is Gj=G∩{e1,…,ej}G_j = G \cap \{e_1, \dots, e_j\}Gj=G∩{e1,…,ej} a basis of {e1,…,ej}\{e_1, \dots, e_j\}{e1,…,ej} ?
Each rejected eie_iei had F∪{ei}∉FF \cup \{e_i\} \notin \mathcal{F}F∪{ei}∈/F at its step, and later sets FFF only grow, so by (M2) no rejected element can be added at the end, and none of e1,…,eje_1, \dots, e_je1,…,ej can be added to GjG_jGj . GGG is the output, e1,…,ene_1, \dots, e_ne1,…,en the sorted order. (M2): subsets of independent sets are independent.
[The Greedy Algorithm] An oracle that decides, for a given F⊆EF \subseteq EF⊆E , whether FFF contains a basis is called a basis-superset oracle.
[The Greedy Algorithm] State the Worst-Out-Greedy Algorithm for the Maximization Problem (input: independence system given by a basis-superset oracle, weights c:E→R≥0c : E \to \mathbb{R}_{\ge 0}c:E→R≥0 ).
Sort c(e1)≤⋯≤c(en)c(e_1) \le \dots \le c(e_n)c(e1)≤⋯≤c(en) ; start with F=EF = EF=E ; for i=1,…,ni = 1, \dots, ni=1,…,n , remove eie_iei from FFF if F∖{ei}F \setminus \{e_i\}F∖{ei} still contains a basis. The output is a basis: an element eee of the final FFF outside a basis it contains would have been removed when eee was tried.
[The Greedy Algorithm] When the greedy algorithms are used for the Minimization Problem (find a minimum-weight basis), in which order are elements tried?
Best-In-Greedy: cheapest first. Worst-Out-Greedy: most expensive first. In both cases the “best” element is the one that is cheapest for minimization.
[The Greedy Algorithm] Besides the independence and basis-superset oracles, which four oracles can specify an independence system?
Rank oracle (return r(F)r(F)r(F) ), closure oracle (return σ(F)\sigma(F)σ(F) ), basis oracle (is FFF a basis of EEE ?), circuit oracle (is FFF a circuit?).
[The Greedy Algorithm] When are two oracles for independence systems polynomially equivalent?
Each can be simulated by a polynomial-time oracle algorithm using the other.
[The Greedy Algorithm] E=E(Kn)E = E(K_n)E=E(Kn) and F\mathcal{F}F = the subsets of edge sets of Hamilton circuits of KnK_nKn . Which of the independence oracle and the basis-superset oracle is easy here?
The independence oracle is easy; the basis-superset oracle solves an NP-complete problem. Independent: FFF is a Hamilton circuit or a disjoint union of paths. Containing a basis: the graph (V,F)(V, F)(V,F) has a Hamilton circuit. So if P≠NPP \ne NPP=NP the two oracles are not polynomially equivalent in general.
[The Greedy Algorithm] GGG is a graph with vertices s,ts, ts,t , ttt reachable from sss , and F\mathcal{F}F = the subsets of edge sets of sss - ttt -paths. Which of the independence oracle and the basis-superset oracle is easy here?
The basis-superset oracle is easy; the independence oracle solves an NP-complete problem (Korte and Monma, 1979). FFF contains a basis iff ttt is reachable from sss in (V(G),F)(V(G), F)(V(G),F) .
[The Greedy Algorithm] For matroids, are the independence oracle and the basis-superset oracle polynomially equivalent?
Yes. In general independence systems they are not (if P≠NPP \ne NPP=NP ).
[The Greedy Algorithm] (E,F)(E, \mathcal{F})(E,F) is an independence system and (E,F∗)(E, \mathcal{F}^*)(E,F∗) its dual. The Best-In-Greedy Algorithm for the Maximization Problem on (E,F,c)(E, \mathcal{F}, c)(E,F,c) corresponds to which algorithm on the dual?
The Worst-Out-Greedy Algorithm for the Minimization Problem on (E,F∗,c)(E, \mathcal{F}^*, c)(E,F∗,c) . Adding an element to FFF means removing it from the complement E∖FE \setminus FE∖F , and the bases of F∗\mathcal{F}^*F∗ are the complements of bases of F\mathcal{F}F .
[The Greedy Algorithm] Theorem of Jenkyns and Korte–Hausmann. (E,F)(E, \mathcal{F})(E,F) is an independence system, c:E→R≥0c : E \to \mathbb{R}_{\ge 0}c:E→R≥0 , G(E,F,c)G(E, \mathcal{F}, c)G(E,F,c) the cost of a Best-In-Greedy solution for the Maximization Problem and OPT(E,F,c)\operatorname{OPT}(E, \mathcal{F}, c)OPT(E,F,c) the optimum. Bound the ratio.
q(E,F)≤G(E,F,c)OPT(E,F,c)≤1\boldsymbol{q(E, \mathcal{F}) \le \frac{G(E, \mathcal{F}, c)}{\operatorname{OPT}(E, \mathcal{F}, c)} \le 1}q(E,F)≤OPT(E,F,c)G(E,F,c)≤1 (with 00:=1\frac{0}{0} := 100:=1 ), and the lower bound is attained for some ccc and some greedy run. q(E,F)=minFρ(F)/r(F)q(E, \mathcal{F}) = \min_F \rho(F) / r(F)q(E,F)=minFρ(F)/r(F) is the rank quotient (smallest over largest basis size).
[The Greedy Algorithm] Best-In-Greedy vs. optimum: c(e1)≥⋯≥c(en)≥0c(e_1) \ge \dots \ge c(e_n) \ge 0c(e1)≥⋯≥c(en)≥0 , Ej={e1,…,ej}E_j = \{e_1, \dots, e_j\}Ej={e1,…,ej} , greedy solution GnG_nGn with Gj=Gn∩EjG_j = G_n \cap E_jGj=Gn∩Ej , optimum OnO_nOn with Oj=On∩EjO_j = O_n \cap E_jOj=On∩Ej , dj=c(ej)−c(ej+1)d_j = c(e_j) - c(e_{j+1})dj=c(ej)−c(ej+1) , dn=c(en)d_n = c(e_n)dn=c(en) .How does the proof show c(Gn)≥q(E,F) c(On)c(G_n) \ge q(E, \mathcal{F}) \, c(O_n)c(Gn)≥q(E,F)c(On…
c(Gn)=∑j∣Gj∣dj≥∑jρ(Ej)dj≥q∑jr(Ej)dj≥q∑j∣Oj∣dj=q c(On)\boldsymbol{c(G_n) = \sum_j |G_j| d_j \ge \sum_j \rho(E_j) d_j \ge q \sum_j r(E_j) d_j \ge q \sum_j |O_j| d_j = q \, c(O_n)}c(Gn)=∑j∣Gj∣dj≥∑jρ(Ej)dj≥q∑jr(Ej)dj≥q∑j∣Oj∣dj=qc(On) GjG_jGj is a basis of EjE_jEj , so ∣Gj∣≥ρ(Ej)|G_j| \ge \rho(E_j)∣Gj∣≥ρ(Ej) ; OjO_jOj is independent, so ∣Oj∣≤r(Ej)|O_j| \le r(E_j)∣Oj∣≤r(Ej) ; ρ(Ej)≥q r(Ej)\rho(E_j) \ge q \, r(E_j)ρ(Ej)≥qr(Ej) by definition of qqq . All dj≥0d_j \ge 0dj≥0 .
[The Greedy Algorithm] For Best-In-Greedy on the Maximization Problem, q(E,F)≤G/OPT≤1q(E, \mathcal{F}) \le G / \operatorname{OPT} \le 1q(E,F)≤G/OPT≤1 , where q=minFρ(F)/r(F)q = \min_F \rho(F) / r(F)q=minFρ(F)/r(F) .Which cost function shows the lower bound q(E,F)q(E, \mathcal{F})q(E,F) is attained?
Take FFF with bases B1,B2B_1, B_2B1,B2 , ∣B1∣/∣B2∣=q(E,F)|B_1| / |B_2| = q(E, \mathcal{F})∣B1∣/∣B2∣=q(E,F) ; set c=1c = 1c=1 on FFF and 000 elsewhere, and let the greedy order put B1B_1B1 first. Then greedy picks B1B_1B1 (cost ∣B1∣|B_1|∣B1∣ ) while the optimum is ∣B2∣|B_2|∣B2∣ . Slightly perturbing the weights makes every greedy run arbitrarily close to q⋅OPTq \cdot \operatorname{OPT}q⋅OPT .
[The Greedy Algorithm] Edmonds–Rado Theorem. When does the Best-In-Greedy Algorithm solve the Maximization Problem for (E,F,c)(E, \mathcal{F}, c)(E,F,c) optimally for all c:E→R≥0c : E \to \mathbb{R}_{\ge 0}c:E→R≥0 ?
If and only if (E,F)(E, \mathcal{F})(E,F) is a matroid. Greedy is optimal for all ccc iff q(E,F)=1q(E, \mathcal{F}) = 1q(E,F)=1 (by the bound q≤G/OPT≤1q \le G / \operatorname{OPT} \le 1q≤G/OPT≤1 , attained for some ccc ), and q=1q = 1q=1 iff matroid.
[The Greedy Algorithm] (E,F)(E, \mathcal{F})(E,F) is a matroid, c:E→Rc : E \to \mathbb{R}c:E→R , X∈FX \in \mathcal{F}X∈F with ∣X∣=k|X| = k∣X∣=k , and C(X,y)C(X, y)C(X,y) is the circuit in X∪{y}X \cup \{y\}X∪{y} . When does XXX have maximum weight among all independent sets of size kkk ?
Iff (a) c(x)≥c(y)c(x) \ge c(y)c(x)≥c(y) for all y∉Xy \notin Xy∈/X with X∪{y}∉FX \cup \{y\} \notin \mathcal{F}X∪{y}∈/F and x∈C(X,y)x \in C(X, y)x∈C(X,y) , and (b) c(x)≥c(y)c(x) \ge c(y)c(x)≥c(y) for all y∉Xy \notin Xy∈/X with X∪{y}∈FX \cup \{y\} \in \mathcal{F}X∪{y}∈F and all x∈Xx \in Xx∈X . No single exchange improves XXX . Necessity is clear: a violated condition gives a better exchange X−x+yX - x + yX−x+y .
[The Greedy Algorithm] Claim: a size- kkk independent set XXX of a matroid is a maximum-weight size- kkk independent set if no exchange X−x+yX - x + yX−x+y (keeping independence) increases the weight.How does the proof reduce this to the Best-In-Greedy Algorithm?
Run Best-In-Greedy on F′={F∈F:∣F∣≤k}\mathcal{F}' = \{F \in \mathcal{F} : |F| \le k\}F′={F∈F:∣F∣≤k} (a matroid) with weights c′=c+Mc' = c + Mc′=c+M , M=maxe∣c(e)∣M = \max_e |c(e)|M=maxe∣c(e)∣ , breaking ties in favour of elements of XXX ; then show the greedy output X′X'X′ equals XXX . c′≥0c' \ge 0c′≥0 as greedy requires, and for size- kkk sets c′(Y)=c(Y)+kMc'(Y) = c(Y) + kMc′(Y)=c(Y)+kM . By Edmonds–Rado X′X'X′ is optimal. XXX and X′X'X′ agree on e1,…,ei−1e_…
[The Greedy Algorithm] Path x−y−zx - y - zx−y−z with c(x)=1c(x) = 1c(x)=1 , c(y)=2c(y) = 2c(y)=2 , c(z)=1000c(z) = 1000c(z)=1000 ; the bases are the vertex covers {y}\{y\}{y} and {x,z}\{x, z\}{x,z} . What does the Best-In-Greedy Algorithm find for the Minimization Problem, and what does this show?
{x,z}\{x, z\}{x,z} with cost 1001, while {y}\{y\}{y} costs 2: no positive upper bound on G/OPTG / \operatorname{OPT}G/OPT exists for Best-In-Greedy on the Minimization Problem. It picks the cheapest xxx first and then has to complete with zzz .
[The Greedy Algorithm] Korte–Monma theorem. (E,F)(E, \mathcal{F})(E,F) independence system, c≥0c \ge 0c≥0 , GGG the cost of a Worst-Out-Greedy solution for the Minimization Problem, OPT\operatorname{OPT}OPT the optimum; ρ∗,r∗\rho^*, r^*ρ∗,r∗ the lower rank and rank of the dual. Bound G/OPTG / \operatorname{OPT}G/OPT .
1≤G(E,F,c)OPT(E,F,c)≤maxF⊆E∣F∣−ρ∗(F)∣F∣−r∗(F)\boldsymbol{1 \le \frac{G(E, \mathcal{F}, c)}{\operatorname{OPT}(E, \mathcal{F}, c)} \le \max_{F \subseteq E} \frac{|F| - \rho^*(F)}{|F| - r^*(F)}}1≤OPT(E,F,c)G(E,F,c)≤maxF⊆E∣F∣−r∗(F)∣F∣−ρ∗(F) (with 00:=1\frac{0}{0} := 100:=1 ), and the upper bound is attained for some ccc .
[The Greedy Algorithm] Worst-Out-Greedy for the Minimization Problem: c(e1)≥⋯≥c(en)c(e_1) \ge \dots \ge c(e_n)c(e1)≥⋯≥c(en) , Ej={e1,…,ej}E_j = \{e_1, \dots, e_j\}Ej={e1,…,ej} , greedy solution GnG_nGn , Gj=Gn∩EjG_j = G_n \cap E_jGj=Gn∩Ej , optimum OnO_nOn , Oj=On∩EjO_j = O_n \cap E_jOj=On∩Ej . ρ∗,r∗\rho^*, r^*ρ∗,r∗ : lower rank and rank of the dual F∗\mathcal{F}^*F∗ .Which two bounds on ∣Gj∣|G_j|∣Gj∣ and ∣Oj∣|O_j|∣Oj∣ drive the proof, and why do they hold?
∣Gj∣≤∣Ej∣−ρ∗(Ej)\boldsymbol{|G_j| \le |E_j| - \rho^*(E_j)}∣Gj∣≤∣Ej∣−ρ∗(Ej) and ∣Oj∣≥∣Ej∣−r∗(Ej)\boldsymbol{|O_j| \ge |E_j| - r^*(E_j)}∣Oj∣≥∣Ej∣−r∗(Ej) Ej∖GjE_j \setminus G_jEj∖Gj is a basis of EjE_jEj in F∗\mathcal{F}^*F∗ (by how greedy removed elements), and Ej∖OjE_j \setminus O_jEj∖Oj is independent in F∗\mathcal{F}^*F∗ since it avoids the basis OnO_nOn . Then sum with weights dj=c(ej)−c(ej+1)≥0d_j = c(e_j) - c(e_{j+1}) \ge 0dj=c(ej)−c(ej+1)≥0 as for Best-In-Greedy.
[The Greedy Algorithm] Path x−y−zx - y - zx−y−z with c(x)=1c(x) = 1c(x)=1 , c(y)=2c(y) = 2c(y)=2 , c(z)=1000c(z) = 1000c(z)=1000 , F\mathcal{F}F = stable sets. What does the Worst-Out-Greedy Algorithm find for the Maximization Problem, and what does this show?
{y}\{y\}{y} with weight 2, while {x,z}\{x, z\}{x,z} has weight 1001: no positive lower bound on G/OPTG / \operatorname{OPT}G/OPT exists for Worst-Out-Greedy on the Maximization Problem. It removes the cheapest xxx first ( {y,z}\{y, z\}{y,z} still contains the basis {y}\{y\}{y} ), then has to remove zzz .
[Matroid Intersection] What is the intersection of independence systems (E,F1),…,(E,Fk)(E, \mathcal{F}_1), \dots, (E, \mathcal{F}_k)(E,F1),…,(E,Fk) , and is it an independence system?
(E,F1∩⋯∩Fk)\boldsymbol{(E, \mathcal{F}_1 \cap \dots \cap \mathcal{F}_k)}(E,F1∩⋯∩Fk) ; yes, always. But the intersection of matroids is in general not a matroid.
[Matroid Intersection] Which independence systems are the intersection of finitely many matroids?
All of them. Each circuit CCC defines the matroid (E,{F⊆E:C⊈F})(E, \{F \subseteq E : C \not\subseteq F\})(E,{F⊆E:C⊆F}) , and the intersection over all circuits is (E,F)(E, \mathcal{F})(E,F) .
[Matroid Intersection] C⊆EC \subseteq EC⊆E is nonempty. Why is (E,{F⊆E:C⊈F})(E, \{F \subseteq E : C \not\subseteq F\})(E,{F⊆E:C⊆F}) a matroid?
If ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ and every x∈X∖Yx \in X \setminus Yx∈X∖Y had C⊆Y∪{x}C \subseteq Y \cup \{x\}C⊆Y∪{x} , then C∖Y={x}C \setminus Y = \{x\}C∖Y={x} for all such xxx , so X∖Y={x}X \setminus Y = \{x\}X∖Y={x} and Y⊆XY \subseteq XY⊆X ; but then C⊆Y∪{x}⊆XC \subseteq Y \cup \{x\} \subseteq XC⊆Y∪{x}⊆X , a contradiction. ∣X∖Y∣=1|X \setminus Y| = 1∣X∖Y∣=1 and ∣X∣>∣Y∣|X| > |Y|∣X∣>∣Y∣ force Y∖X=∅Y \setminus X = \emptysetY∖X=∅ .
[Matroid Intersection] (E,F)(E, \mathcal{F})(E,F) is the intersection of ppp matroids. What can you say about its rank quotient q(E,F)q(E, \mathcal{F})q(E,F) , and why?
q(E,F)≥1p\boldsymbol{q(E, \mathcal{F}) \ge \frac{1}{p}}q(E,F)≥p1 For X∈FX \in \mathcal{F}X∈F , X∪{e}X \cup \{e\}X∪{e} contains at most one circuit of each of the ppp matroids, so at most ppp circuits of (E,F)(E, \mathcal{F})(E,F) ; and “at most ppp circuits in each A∪{e}A \cup \{e\}A∪{e} ” gives q≥1/pq \ge 1/pq≥1/p .
[Matroid Intersection] GGG is bipartite with sides AAA and BBB . How are the matchings of GGG the intersection of two matroids on E(G)E(G)E(G) ?
F1={F:∣δF(x)∣≤1 ∀x∈A}\boldsymbol{\mathcal{F}_1 = \{F : |\delta_F(x)| \le 1 \ \forall x \in A\}}F1={F:∣δF(x)∣≤1 ∀x∈A} and F2={F:∣δF(x)∣≤1 ∀x∈B}\boldsymbol{\mathcal{F}_2 = \{F : |\delta_F(x)| \le 1 \ \forall x \in B\}}F2={F:∣δF(x)∣≤1 ∀x∈B} . δF(x)\delta_F(x)δF(x) : edges of FFF at xxx . Hence q≥1/2q \ge 1/2q≥1/2 for bipartite matchings, so the Best-In-Greedy Algorithm gets at least half the optimum weight.
[Matroid Intersection] Give a bipartite graph whose matchings have rank quotient exactly 12\frac{1}{2}21 .
The path with three edges. Its edge set has the bases {middle edge}\{\text{middle edge}\}{middle edge} and {two end edges}\{\text{two end edges}\}{two end edges} .
[Matroid Intersection] State the Matroid Intersection Problem.
Given two matroids (E,F1)(E, \mathcal{F}_1)(E,F1) , (E,F2)(E, \mathcal{F}_2)(E,F2) by independence oracles, find F∈F1∩F2F \in \mathcal{F}_1 \cap \mathcal{F}_2F∈F1∩F2 with ∣F∣|F|∣F∣ maximum.
[Matroid Intersection] What is the main idea of the polynomial-time algorithm for the Matroid Intersection Problem?
Start with X=∅X = \emptysetX=∅ and in each iteration augment XXX by one element, keeping it independent in both matroids, which in general requires exchanging whole sets of elements.
[Matroid Intersection] Frank's exchange lemma. (E,F)(E, \mathcal{F})(E,F) matroid, X∈FX \in \mathcal{F}X∈F , x1,…,xs∈Xx_1, \dots, x_s \in Xx1,…,xs∈X , y1,…,ys∈E∖Xy_1, \dots, y_s \in E \setminus Xy1,…,ys∈E∖X , C(X,y)C(X, y)C(X,y) the circuit in X∪{y}X \cup \{y\}X∪{y} . Under which conditions is (X∖{x1,…,xs})∪{y1,…,ys}∈F(X \setminus \{x_1, \dots, x_s\}) \cup \{y_1, \dots, y_s\} \in \mathcal{F}(X∖{x1,…,xs})∪{y1,…,ys}∈F ?
(a) xk∈C(X,yk)x_k \in C(X, y_k)xk∈C(X,yk) for all kkk , and (b) xj∉C(X,yk)x_j \notin C(X, y_k)xj∈/C(X,yk) for 1≤j<k≤s1 \le j < k \le s1≤j<k≤s . Each single swap X−xk+ykX - x_k + y_kX−xk+yk is valid, and no earlier xjx_jxj lies in a later circuit.
[Matroid Intersection] Frank's lemma: if (a) xk∈C(X,yk)x_k \in C(X, y_k)xk∈C(X,yk) for all kkk and (b) xj∉C(X,yk)x_j \notin C(X, y_k)xj∈/C(X,yk) for j<kj < kj<k , then (X∖{x1,…,xs})∪{y1,…,ys}(X \setminus \{x_1, \dots, x_s\}) \cup \{y_1, \dots, y_s\}(X∖{x1,…,xs})∪{y1,…,ys} is independent.What is the proof idea?
Induction on Xr=(X∖{x1,…,xr})∪{y1,…,yr}X_r = (X \setminus \{x_1, \dots, x_r\}) \cup \{y_1, \dots, y_r\}Xr=(X∖{x1,…,xr})∪{y1,…,yr} : by (b), C(X,yr)⊆Xr−1∪{yr}C(X, y_r) \subseteq X_{r-1} \cup \{y_r\}C(X,yr)⊆Xr−1∪{yr} , so it is the unique circuit there, and by (a) removing xrx_rxr destroys it. If Xr−1∪{yr}X_{r-1} \cup \{y_r\}Xr−1∪{yr} is independent, XrX_rXr is a subset of it.
[Matroid Intersection] (E,F1),(E,F2)(E, \mathcal{F}_1), (E, \mathcal{F}_2)(E,F1),(E,F2) are matroids with circuits Ci(X,y)C_i(X, y)Ci(X,y) , and X∈F1∩F2X \in \mathcal{F}_1 \cap \mathcal{F}_2X∈F1∩F2 . What are the arcs of the auxiliary digraph GXG_XGX on vertex set EEE ?
(x,y)\boldsymbol{(x, y)}(x,y) for y∉Xy \notin Xy∈/X , x∈C1(X,y)∖{y}x \in C_1(X, y) \setminus \{y\}x∈C1(X,y)∖{y} , and (y,x)\boldsymbol{(y, x)}(y,x) for y∉Xy \notin Xy∈/X , x∈C2(X,y)∖{y}x \in C_2(X, y) \setminus \{y\}x∈C2(X,y)∖{y} . So (x,y)(x, y)(x,y) means X−x+y∈F1X - x + y \in \mathcal{F}_1X−x+y∈F1 , and (y,x)(y, x)(y,x) means X−x+y∈F2X - x + y \in \mathcal{F}_2X−x+y∈F2 (both while X+yX + yX+y is dependent there).