Ch.2: Cryptomorphisms
Chapter 2 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 2.1. Cryptomorphisms 2.2. Independent sets to bases and back 2.3. Circuits and independent sets 2.4. Rank, flats, hyperplanes and closure 2.5. Lattice of flats 2.6. Tying it together with the rank function 2.7. Flats, hyperplanes and closure 2.8. Optimization: the greedy algorithm
149 flashcards · Mathematics · by lakesare
Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses
[Cryptomorphisms] What is a cryptomorphism between two axiom systems for matroids?
An explicit translation from each system to the other, showing that both define the same matroids. In the book's words, an "equivalent way to define matroids, yet not straightforward".Example: from the independent sets, take the maximal ones to get the bases; from the bases, take all their subsets to get the independent sets.
[Cryptomorphisms] What does every axiom system for matroids consist of?
A finite ground set EEE , plus a family of subsets of EEE or a function on 2E2^E2E , satisfying one or two easy axioms and one substantial axiom. Example: independent sets: two easy axioms (nonempty, closed under subsets) and the substantial augmentation axiom.
[Cryptomorphisms] Who coined the term "cryptomorphism", and in what form?
Garrett Birkhoff, as "crypto-isomorphism", in 1967. He used it in his book Lattice Theory, for a new lattice-theoretic definition of a simple matroid. The term was later shortened to "cryptomorphism".
[Independent sets to bases and back] A matroid M=(E,I)M = (E, \mathcal{I})M=(E,I) : EEE is a finite set and I\mathcal{I}I is a family of subsets of EEE . Which three axioms must I\mathcal{I}I satisfy?
(I1) Non-triviality I≠∅\mathcal{I} \neq \emptysetI=∅ Example: I={∅}\mathcal{I} = \{\emptyset\}I={∅} is allowed. (I2) Closed under subsets If J∈IJ \in \mathcal{I}J∈I and I⊆JI \subseteq JI⊆J , then I∈II \in \mathcal{I}I∈I . Example: {a,c}∈I\{a, c\} \in \mathcal{I}{a,c}∈I forces {a},{c},∅∈I\{a\}, \{c\}, \emptyset \in \mathcal{I}{a},{c},∅∈I . (I3) Augmentation If I,J∈II, J \in \mathcal{I}I,J∈I with ∣I∣<∣J∣|I| < |J|∣I∣<∣J∣ , then some x∈J−Ix \in J - Ix∈J−I has I∪{x}∈II \cup \{x\} \in \mathcal{I}I∪{…
[Independent sets to bases and back] What is a set system (E,I)(E, \mathcal{I})(E,I) ?
I\mathcal{I}I is a non-empty family of subsets of EEE that is closed under taking subsets, i.e. (I1) and (I2). Topologists call a set system a simplicial complex.Example: {∅,{a},{b},{a,b},{c}}\{\emptyset, \{a\}, \{b\}, \{a, b\}, \{c\}\}{∅,{a},{b},{a,b},{c}} is a set system; {∅,{a,b}}\{\emptyset, \{a, b\}\}{∅,{a,b}} is not (it misses {a}\{a\}{a} ).
[Independent sets to bases and back] Why does every set system I\mathcal{I}I (nonempty, closed under subsets) contain ∅\emptyset∅ ?
I\mathcal{I}I contains some set XXX , and ∅⊆X\emptyset \subseteq X∅⊆X .
[Independent sets to bases and back] Proposition 2.3 I\mathcal{I}I (a family of subsets of a finite set EEE ) is the family of independent sets of a matroid if and only if (I2) holds (closed under subsets) and which two other axioms … ?
(I1′) ∅∈I\emptyset \in \mathcal{I}∅∈I and (I3′) if I,J∈II, J \in \mathcal{I}I,J∈I with ∣J∣=∣I∣+1|J| = |I| + 1∣J∣=∣I∣+1 , then some x∈J−Ix \in J - Ix∈J−I has I∪{x}∈II \cup \{x\} \in \mathcal{I}I∪{x}∈I . (I3′) is augmentation only for sets whose sizes differ by exactly 1.
[Independent sets to bases and back] (I3): if I,J∈II, J \in \mathcal{I}I,J∈I with ∣I∣<∣J∣|I| < |J|∣I∣<∣J∣ , some x∈J−Ix \in J - Ix∈J−I has I∪{x}∈II \cup \{x\} \in \mathcal{I}I∪{x}∈I . (I3′): the same, but only for ∣J∣=∣I∣+1|J| = |I| + 1∣J∣=∣I∣+1 .For a family I\mathcal{I}I closed under subsets, how does (I3′) give (I3)?
Take any I′⊆JI' \subseteq JI′⊆J with ∣I′∣=∣I∣+1|I'| = |I| + 1∣I′∣=∣I∣+1 ; I′∈II' \in \mathcal{I}I′∈I by closure under subsets, so (I3′) gives x∈I′−I⊆J−Ix \in I' - I \subseteq J - Ix∈I′−I⊆J−I with I∪{x}∈II \cup \{x\} \in \mathcal{I}I∪{x}∈I . Without closure under subsets this fails. Example: {∅,{b,c}}\{\emptyset, \{b, c\}\}{∅,{b,c}} satisfies (I3′) (no two sets differ in size by 1) but not (I3).
[Independent sets to bases and back] In a family of sets, what is the difference between a maximal and a maximum set?
Maximal: contained in no other set of the family. Maximum: has the largest size in the family. A maximum set is maximal, but not conversely.Example: in {∅,{a},{c},{a,b}}\{\emptyset, \{a\}, \{c\}, \{a, b\}\}{∅,{a},{c},{a,b}} , both {a,b}\{a, b\}{a,b} and {c}\{c\}{c} are maximal, only {a,b}\{a, b\}{a,b} is maximum.
[Independent sets to bases and back] Why are all maximal independent sets of a matroid the same size?
If maximal independent B1,B2B_1, B_2B1,B2 had ∣B1∣<∣B2∣|B_1| < |B_2|∣B1∣<∣B2∣ , augmentation (I3) would give x∈B2−B1x \in B_2 - B_1x∈B2−B1 with B1∪{x}B_1 \cup \{x\}B1∪{x} independent, so B1B_1B1 would not be maximal. So for independent sets, maximal = maximum.
[Independent sets to bases and back] What is a basis of a matroid M=(E,I)M = (E, \mathcal{I})M=(E,I) ?
A maximal independent set. All subsets of EEE ordered by inclusion, from ∅\emptyset∅ (bottom) to EEE (top): the bases are the top layer of the independent sets.Example: for I={∅,a,b,c,ac,bc}\mathcal{I} = \{\emptyset, a, b, c, ac, bc\}I={∅,a,b,c,ac,bc} , the bases are acacac and bcbcbc .
[Independent sets to bases and back] A family of subsets of a set, no one of which is a subset of another, is called a clutter.
Example: {{a,b},{b,c},{d}}\{\{a, b\}, \{b, c\}, \{d\}\}{{a,b},{b,c},{d}} is a clutter; {{a},{a,b}}\{\{a\}, \{a, b\}\}{{a},{a,b}} is not.
[Independent sets to bases and back] The bases B\mathcal{B}B of a matroid on EEE satisfy which three axioms?
(B1) Non-triviality B≠∅\mathcal{B} \neq \emptysetB=∅ (B2) Clutter If B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B and B1⊆B2B_1 \subseteq B_2B1⊆B2 , then B1=B2B_1 = B_2B1=B2 . Example: acacac and abcabcabc cannot both be bases. (B3) Weak basis exchange If B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B and x∈B1−B2x \in B_1 - B_2x∈B1−B2 , then some y∈B2−B1y \in B_2 - B_1y∈B2−B1 has B1−x∪{y}∈BB_1 - x \cup \{y\} \in \mathcal{B}B1−x∪{y}∈B . Example: bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace…
[Independent sets to bases and back] What is the axiom (B2′) Equicardinal for a family of bases B\mathcal{B}B , and how does it relate to (B2) (Clutter)?
(B2′): if B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B then ∣B1∣=∣B2∣|B_1| = |B_2|∣B1∣=∣B2∣ . Together with (B1) and (B3), it is equivalent to (B2) (Proposition 2.5). (B2′) implies (B2) directly: a proper subset has fewer elements.
[Independent sets to bases and back] The cryptomorphism between independent sets I\mathcal{I}I and bases B\mathcal{B}B : how is each family defined from the other?
B\mathcal{B}B = the maximal members of I\mathcal{I}I ; I\ \mathcal{I} I = all subsets of members of B\mathcal{B}B . B={B∈I∣B⊆A∈I implies B=A}\mathcal{B} = \{B \in \mathcal{I} \mid B \subseteq A \in \mathcal{I} \text{ implies } B = A\}B={B∈I∣B⊆A∈I implies B=A} , I={I∣I⊆B for some B∈B}\ \mathcal{I} = \{I \mid I \subseteq B \text{ for some } B \in \mathcal{B}\} I={I∣I⊆B for some B∈B}
[Independent sets to bases and back] Proving a cryptomorphism between independent sets and bases: which four things must be shown, besides the two definitions ( f(I)f(\mathcal{I})f(I) = maximal members, g(B)g(\mathcal{B})g(B) = all subsets)?
f(I)f(\mathcal{I})f(I) is a family of bases (B1), (B2′), (B3) follow from (I1), (I2), (I3). g(B)g(\mathcal{B})g(B) is a family of independent sets (I1), (I2), (I3) follow from (B1), (B2′), (B3). g(f(I))=Ig(f(\mathcal{I})) = \mathcal{I}g(f(I))=I f(g(B))=Bf(g(\mathcal{B})) = \mathcal{B}f(g(B))=B The two compositions show that the translations are inverse to each other ( f,g:22E→22Ef, g : 2^{2^E} \to 2^{2^E}f,g:22E→22E ).
[Independent sets to bases and back] Theorem 2.6 Let EEE be a finite set and B\mathcal{B}B a family of subsets of EEE satisfying (B1) non-triviality, (B2) clutter, (B3) weak basis exchange. Then … ?
B\mathcal{B}B is the collection of bases of a matroid M=(E,I)M = (E, \mathcal{I})M=(E,I) , and (E,B)(E, \mathcal{B})(E,B) is cryptomorphic to MMM . So a matroid can be defined by its bases.
[Independent sets to bases and back] B\mathcal{B}B = the maximal independent sets of a matroid (finite EEE ). Why is B≠∅\mathcal{B} \neq \emptysetB=∅ ?
∅\emptyset∅ is independent and EEE is finite, so some independent set is contained in no larger independent set.
[Independent sets to bases and back] B\mathcal{B}B = the maximal independent sets of a matroid; all members of B\mathcal{B}B have the same size. (I2): subsets of independent sets are independent. (I3): augmentation.Why does B\mathcal{B}B satisfy weak basis exchange: for B1,B2∈BB_1, B_2 \in \mathcal{B}B1,B2∈B and x∈B1−B2x \in B_1 - B_2x∈B1−B2 , some y∈B2−B1y \in B_2 - B_1y∈B2−B1 has B1−x∪{y}∈BB_1 - x \cup \{y\} \in \mathcal{B}B1−x∪{y}∈B ?
B1−xB_1 - xB1−x is independent and smaller than B2B_2B2 , so (I3) gives y∈B2−(B1−x)y \in B_2 - (B_1 - x)y∈B2−(B1−x) with B1−x∪{y}B_1 - x \cup \{y\}B1−x∪{y} independent; this set has size ∣B1∣|B_1|∣B1∣ , so it is a basis. An independent set of the size of a basis is contained in a basis of the same size, so equals it. And y≠xy \neq xy=x since x∉B2x \notin B_2x∈/B2 .
[Independent sets to bases and back] B\mathcal{B}B satisfies the basis axioms and I={I∣I⊆B for some B∈B}\mathcal{I} = \{I \mid I \subseteq B \text{ for some } B \in \mathcal{B}\}I={I∣I⊆B for some B∈B} . Why do (I1) non-triviality and (I2) closed under subsets hold?
(I1): B≠∅\mathcal{B} \neq \emptysetB=∅ and B⊆I\mathcal{B} \subseteq \mathcal{I}B⊆I . (I2): if I′⊆I⊆BI' \subseteq I \subseteq BI′⊆I⊆B then I′⊆BI' \subseteq BI′⊆B .
[Independent sets to bases and back] B\mathcal{B}B satisfies (B1), (B2′) equicardinal, (B3) weak basis exchange; I\mathcal{I}I = all subsets of members of B\mathcal{B}B . To prove (I3), take I1,I2∈II_1, I_2 \in \mathcal{I}I1,I2∈I with ∣I1∣<∣I2∣|I_1| < |I_2|∣I1∣<∣I2∣ , suppose (I3) fails for them, and pick bases B1⊇I1B_1 \supseteq I_1B1⊇I1 , B2⊇I2B_2 \supseteq I_2B2⊇I2 .Why may we assume I1∩I2=B1∩I2I_1 \cap I_2 = B_1 \cap I_2I1∩I2=B1∩I2 ?
Otherwise some x∈(I2∩B1)−I1x \in (I_2 \cap B_1) - I_1x∈(I2∩B1)−I1 exists, and then I1∪{x}⊆B1I_1 \cup \{x\} \subseteq B_1I1∪{x}⊆B1 is independent, so (I3) holds. The hatched part (I2∩B1)−I1(I_2 \cap B_1) - I_1(I2∩B1)−I1 is empty.
[Independent sets to bases and back] Proof of (I3) from the basis axioms: I1⊆B1I_1 \subseteq B_1I1⊆B1 , I2⊆B2I_2 \subseteq B_2I2⊆B2 , ∣I1∣<∣I2∣|I_1| < |I_2|∣I1∣<∣I2∣ , I1∩I2=B1∩I2I_1 \cap I_2 = B_1 \cap I_2I1∩I2=B1∩I2 , and (I3) is assumed to fail for I1,I2I_1, I_2I1,I2 . Among bases containing I2I_2I2 , B2B_2B2 minimizes ∣B2−(I2∪B1)∣|B_2 - (I_2 \cup B_1)|∣B2−(I2∪B1)∣ .Why is B2−(I2∪B1)=∅B_2 - (I_2 \cup B_1) = \emptysetB2−(I2∪B1)=∅ ?
If x∈B2−(I2∪B1)x \in B_2 - (I_2 \cup B_1)x∈B2−(I2∪B1) , weak basis exchange gives y∈B1−B2y \in B_1 - B_2y∈B1−B2 with B3=B2−x∪{y}B_3 = B_2 - x \cup \{y\}B3=B2−x∪{y} a basis; B3⊇I2B_3 \supseteq I_2B3⊇I2 and B3B_3B3 has one fewer element outside I2∪B1I_2 \cup B_1I2∪B1 , contradicting the choice of B2B_2B2 . In the same way, B1B_1B1 can be chosen with B1−(I1∪B2)=∅B_1 - (I_1 \cup B_2) = \emptysetB1−(I1∪B2)=∅ .
[Independent sets to bases and back] Proof of (I3) from the basis axioms: I1⊆B1I_1 \subseteq B_1I1⊆B1 , I2⊆B2I_2 \subseteq B_2I2⊆B2 , ∣I1∣<∣I2∣|I_1| < |I_2|∣I1∣<∣I2∣ , and the choices give I2−B1=I2−I1I_2 - B_1 = I_2 - I_1I2−B1=I2−I1 , B2−(I2∪B1)=∅B_2 - (I_2 \cup B_1) = \emptysetB2−(I2∪B1)=∅ , B1−(I1∪B2)=∅B_1 - (I_1 \cup B_2) = \emptysetB1−(I1∪B2)=∅ .How does the proof reach the contradiction ∣I2∣≤∣I1∣|I_2| \le |I_1|∣I2∣≤∣I1∣ ?
B2−B1=I2−I1B_2 - B_1 = I_2 - I_1B2−B1=I2−I1 and B1−B2⊆I1−I2B_1 - B_2 \subseteq I_1 - I_2B1−B2⊆I1−I2 ; since ∣B1∣=∣B2∣|B_1| = |B_2|∣B1∣=∣B2∣ , ∣B2−B1∣=∣B1−B2∣|B_2 - B_1| = |B_1 - B_2|∣B2−B1∣=∣B1−B2∣ , so ∣I2−I1∣≤∣I1−I2∣|I_2 - I_1| \le |I_1 - I_2|∣I2−I1∣≤∣I1−I2∣ . The cross-hatched parts and the hatched part are empty.
[Independent sets to bases and back] In the cryptomorphism between independent sets and bases ( fff : take maximal members, ggg : take all subsets), why do g(f(I))=Ig(f(\mathcal{I})) = \mathcal{I}g(f(I))=I and f(g(B))=Bf(g(\mathcal{B})) = \mathcal{B}f(g(B))=B hold?
g∘fg \circ fg∘f is the identity on every family closed under subsets; f∘gf \circ gf∘g is the identity on every clutter. No matroid axiom is needed beyond these: every member of a subset-closed family lies in a maximal member, and in a clutter every member is maximal among the subsets of members.Example: {ac,bc}undefinedg{∅,a,b,c,ac,bc}undefinedf{ac,bc}\{ac, bc\} \xrightarrow{g} \{\emptyset, a, b, c, ac, bc\} \xrightarrow{f} \{ac, bc\}{ac,bc}g{∅,a,b,c,ac,bc}f{ac,bc}
[Independent sets to bases and back] How are dependent sets and circuits obtained from independent sets, and back?
Dependent sets = the sets that are not independent; circuits = the minimal dependent sets. Back: dependent sets = all supersets of circuits.
[Independent sets to bases and back] What are an isthmus and a loop of a matroid MMM on EEE ?
Isthmus: an element of EEE in every basis. Loop: an element of EEE in no basis. An isthmus is also called a coloop (anticipating duality). Both terms come from graph theory.Example: with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde on E={a,…,f}E = \{a, \dots, f\}E={a,…,f} : eee is an isthmus, fff is a loop.
[Independent sets to bases and back] Equivalently, an element xxx is an isthmus if and only if it can be added to … ?
every independent set not containing xxx , giving again an independent set. And a loop is in no independent set at all.
[Independent sets to bases and back] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde ( ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). How is MMM drawn?
a,ba, ba,b a double point and c,dc, dc,d on one line; eee off the line; fff a loop. The bases are exactly the sets of three non-collinear points: eee plus two points of the line other than the pair a,ba, ba,b .
[Circuits and independent sets] What is a circuit of a matroid?
A dependent set all of whose proper subsets are independent, i.e. a minimal dependent set. Example: three collinear points form a circuit; a loop {f}\{f\}{f} is a circuit of size 1.
[Circuits and independent sets] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). Which sets are the circuits of MMM ?
f, ab, acd, bcd\boldsymbol{f, \ ab, \ acd, \ bcd}f, ab, acd, bcd fff is a loop, a,ba, ba,b are parallel, and a,c,da, c, da,c,d and b,c,db, c, db,c,d are collinear triples. Listing circuits is often an efficient way to describe a matroid.
[Circuits and independent sets] Do all circuits of a matroid have the same size, like bases?
No: a minimal dependent set need not have minimum size. Example: with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde on E={a,…,f}E = \{a, \dots, f\}E={a,…,f} , the circuits fff , ababab , acdacdacd have sizes 1, 2, 3, and the isthmus eee is in no circuit.
[Circuits and independent sets] The family C\mathcal{C}C of circuits of a matroid satisfies which three axioms?
(C1) Non-triviality ∅∉C\emptyset \notin \mathcal{C}∅∈/C (C2) Clutter If C1,C2∈CC_1, C_2 \in \mathcal{C}C1,C2∈C and C1⊆C2C_1 \subseteq C_2C1⊆C2 , then C1=C2C_1 = C_2C1=C2 . (C3) Circuit elimination If C1≠C2C_1 \neq C_2C1=C2 are circuits and x∈C1∩C2x \in C_1 \cap C_2x∈C1∩C2 , then some circuit C3⊆C1∪C2−xC_3 \subseteq C_1 \cup C_2 - xC3⊆C1∪C2−x . Example: circuits ababab and bcdbcdbcd share bbb ; the circuit acd⊆abcd−bacd \subseteq abcd - bacd⊆abcd−b .
[Circuits and independent sets] The cryptomorphism between independent sets I\mathcal{I}I and circuits C\mathcal{C}C : how is each defined from the other?
C\mathcal{C}C = the minimal subsets of EEE that are not independent; I\ \mathcal{I} I = the subsets of EEE containing no circuit. C={C⊆E∣C∉I and if I⊊C then I∈I}\mathcal{C} = \{C \subseteq E \mid C \notin \mathcal{I} \text{ and if } I \subsetneq C \text{ then } I \in \mathcal{I}\}C={C⊆E∣C∈/I and if I⊊C then I∈I} , I={I⊆E∣∀C∈C, C⊈I}\ \mathcal{I} = \{I \subseteq E \mid \forall C \in \mathcal{C}, \ C \not\subseteq I\} I={I⊆E∣∀C∈C, C⊆I} Example: circuits f,ab,acd,bcdf, ab, acd, bcdf,ab,acd,bcd on…
[Circuits and independent sets] Theorem 2.10 Let C\mathcal{C}C be a family of subsets of a finite set EEE satisfying (C1) ∅∉C\emptyset \notin \mathcal{C}∅∈/C , (C2) clutter, (C3) circuit elimination. Then … ?
C\mathcal{C}C is the collection of circuits of a matroid M=(E,I)M = (E, \mathcal{I})M=(E,I) , and (E,C)(E, \mathcal{C})(E,C) is cryptomorphic to MMM . The proof has the same structure as for bases: circuits from independent sets satisfy (C1)–(C3), independent sets from circuits satisfy (I1)–(I3), and the two translations compose to the identity.
[Circuits and independent sets] What does strong basis exchange (B3′) say?
If B1,B2B_1, B_2B1,B2 are bases and x∈B1−B2x \in B_1 - B_2x∈B1−B2 , some y∈B2−B1y \in B_2 - B_1y∈B2−B1 makes both B1−x∪{y}B_1 - x \cup \{y\}B1−x∪{y} and B2−y∪{x}B_2 - y \cup \{x\}B2−y∪{x} bases. It implies weak basis exchange (B3), and holds in every matroid.Example: bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde ; B1=aceB_1 = aceB1=ace , B2=bdeB_2 = bdeB2=bde , x=ax = ax=a : y=by = by=b gives bcebcebce and adeadeade , both bases.
[Circuits and independent sets] What does strong circuit elimination (C3′) say?
If C1,C2C_1, C_2C1,C2 are circuits, y∈C1−C2y \in C_1 - C_2y∈C1−C2 and x∈C1∩C2x \in C_1 \cap C_2x∈C1∩C2 , some circuit C3⊆C1∪C2C_3 \subseteq C_1 \cup C_2C3⊆C1∪C2 has y∈C3y \in C_3y∈C3 and x∉C3x \notin C_3x∈/C3 . It implies circuit elimination (C3), and holds in every matroid.Example: circuits acdacdacd and ababab , y=cy = cy=c , x=ax = ax=a : C3=bcdC_3 = bcdC3=bcd .
[Circuits and independent sets] Which two strengthened axioms imply weak basis exchange (B3) and circuit elimination (C3), and still hold in every matroid?
Strong basis exchange (B3′) and strong circuit elimination (C3′). (B3′) is used for duality, (C3′) for circuit transitivity (both in the chapter on new matroids from old).
[Circuits and independent sets] MMM (left) equals M(G)M(G)M(G) , the cycle matroid of the graph GGG (right). What corresponds in GGG to the bases, the circuits, the isthmus eee and the loop fff of MMM ?
Bases spanning trees of GGG Example: {a,c,e}\{a, c, e\}{a,c,e} . Circuits cycles of GGG Example: the double edge ababab , the triangle bcdbcdbcd . Isthmus eee an edge whose removal separates a vertex from the rest of GGG Loop fff a loop edge of GGG
[Circuits and independent sets] Circuits C1={a,b}C_1 = \{a, b\}C1={a,b} and C2={b,c,d}C_2 = \{b, c, d\}C2={b,c,d} of this graph share bbb . Which circuit does circuit elimination give inside C1∪C2−bC_1 \cup C_2 - bC1∪C2−b ?
{a,c,d}\boldsymbol{\{a, c, d\}}{a,c,d} , the triangle through the other parallel edge. In a graph, (C1∪C2)−(C1∩C2)(C_1 \cup C_2) - (C_1 \cap C_2)(C1∪C2)−(C1∩C2) is always a disjoint union of cycles.
[Circuits and independent sets] Is the graph GGG with a given cycle matroid M=M(G)M = M(G)M=M(G) unique?
No. Here the loop fff could sit at any vertex, and the isthmus eee could be attached at other vertices (as long as it forms no cycle). When two graphs give the same cycle matroid was answered by Whitney.
[Rank, flats, hyperplanes and closure] What is the rank r(A)r(A)r(A) of a subset AAA of the ground set of a matroid (E,I)(E, \mathcal{I})(E,I) ?
The size of a largest independent subset of AAA : r(A)=max{∣I∣:I∈I, I⊆A}r(A) = \max\{|I| : I \in \mathcal{I}, \ I \subseteq A\}r(A)=max{∣I∣:I∈I, I⊆A} . r:2E→N∪{0}r : 2^E \to \mathbb{N} \cup \{0\}r:2E→N∪{0} . The rank of the matroid is r(M)=r(E)r(M) = r(E)r(M)=r(E) , the size of any basis.Example: with a,ba, ba,b parallel and ccc another point, r({a,b})=1r(\{a, b\}) = 1r({a,b})=1 , r({a,b,c})=2r(\{a, b, c\}) = 2r({a,b,c})=2 .
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). What are r(abf)r(abf)r(abf) , r(abe)r(abe)r(abe) , r(acdf)r(acdf)r(acdf) and r(cde)r(cde)r(cde) ?
1, 2, 2, 3\boldsymbol{1, \ 2, \ 2, \ 3}1, 2, 2, 3 abfabfabf : a double point plus a loop. abeabeabe : the 2-point line aeaeae . acdfacdfacdf : the 4-point line. cdecdecde : a basis.
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). How many of the 64 subsets of EEE have rank 0, 1, 2 and 3?
2, 12, 30, 20\boldsymbol{2, \ 12, \ 30, \ 20}2, 12, 30, 20 Adding the loop fff never changes rank, so count subsets of abcdeabcdeabcde and double. Rank 0: ∅\emptyset∅ . Rank 1: a,b,c,d,e,aba, b, c, d, e, aba,b,c,d,e,ab . Rank 2: 10 subsets of abcdabcdabcd (size ≥2\ge 2≥2 except ababab ) and ae,be,ce,de,abeae, be, ce, de, abeae,be,ce,de,abe . Rank 3: eee with one of those 10. 2+12+30+20=642 + 12 + 30 + 20 = 642+12+30+20=64
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). Which subsets of EEE are maximal among the subsets of rank 2?
abcdf, abef, cef, def\boldsymbol{abcdf, \ abef, \ cef, \ def}abcdf, abef, cef, def Each spans a line (the 2-point lines aeaeae , cecece , dedede are usually not drawn), and adding any element raises the rank to 3.
[Rank, flats, hyperplanes and closure] Proposition 2.14 How are loops and isthmuses characterized by the rank function rrr of a matroid on EEE ?
Loop xxx is a loop if and only if r(A∪{x})=r(A)r(A \cup \{x\}) = r(A)r(A∪{x})=r(A) for all A⊆EA \subseteq EA⊆E with x∉Ax \notin Ax∈/A . Example: loop fff , r(abf)=r(ab)=1r(abf) = r(ab) = 1r(abf)=r(ab)=1 . Isthmus xxx is an isthmus if and only if r(A∪{x})=r(A)+1r(A \cup \{x\}) = r(A) + 1r(A∪{x})=r(A)+1 for all A⊆EA \subseteq EA⊆E with x∉Ax \notin Ax∈/A . Example: isthmus eee off the line through a,b,ca, b, ca,b,c : r(abce)=r(abc)+1=3r(abce) = r(abc) + 1 = 3r(abce)=r(abc)+1=3 .
[Rank, flats, hyperplanes and closure] Theorem 2.15. An integer-valued function rrr on the subsets of a finite set EEE is the rank function of a matroid if and only if, for all A,B⊆EA, B \subseteq EA,B⊆E , which three axioms hold?
(r1) Normalization 0≤r(A)≤∣A∣0 \le r(A) \le |A|0≤r(A)≤∣A∣ (r2) Increasing If A⊆BA \subseteq BA⊆B , then r(A)≤r(B)r(A) \le r(B)r(A)≤r(B) . (r3) Semimodular r(A∪B)+r(A∩B)≤r(A)+r(B)r(A \cup B) + r(A \cap B) \le r(A) + r(B)r(A∪B)+r(A∩B)≤r(A)+r(B) Example: a,ba, ba,b parallel, c,dc, dc,d on a line with them, eee off the line. A=abceA = abceA=abce , B=abdB = abdB=abd : r(A∪B)+r(A∩B)=3+1=4≤3+2=5r(A \cup B) + r(A \cap B) = 3 + 1 = 4 \le 3 + 2 = 5r(A∪B)+r(A∩B)=3+1=4≤3+2=5 .
[Rank, flats, hyperplanes and closure] Given only the rank function rrr of a matroid, which sets are independent?
The sets III with r(I)=∣I∣r(I) = |I|r(I)=∣I∣ . Example: E={a,b,c}E = \{a, b, c\}E={a,b,c} , r(∅)=0r(\emptyset) = 0r(∅)=0 , r(a)=r(b)=r(c)=r(ab)=1r(a) = r(b) = r(c) = r(ab) = 1r(a)=r(b)=r(c)=r(ab)=1 , r(ac)=r(bc)=r(abc)=2r(ac) = r(bc) = r(abc) = 2r(ac)=r(bc)=r(abc)=2 : the independent sets are ∅,a,b,c,ac,bc\emptyset, a, b, c, ac, bc∅,a,b,c,ac,bc .
[Rank, flats, hyperplanes and closure] Take any function r:2E→N∪{0}r : 2^E \to \mathbb{N} \cup \{0\}r:2E→N∪{0} and call III "independent" when r(I)=∣I∣r(I) = |I|r(I)=∣I∣ . Does this always give a matroid?
No, only when rrr satisfies (r1) normalization, (r2) increasing and (r3) semimodularity.
[Rank, flats, hyperplanes and closure] What is a flat of a matroid with rank function rrr ?
A set FFF with r(F∪{x})>r(F)r(F \cup \{x\}) > r(F)r(F∪{x})>r(F) for every x∉Fx \notin Fx∈/F : adding any new element raises the rank. Also called a closed set. Flats are the points, lines, planes and higher-dimensional planes of the geometry.Example: with a,b,c,da, b, c, da,b,c,d on a line, abcdabcdabcd is a flat, abcabcabc is not ( r(abcd)=r(abc)r(abcd) = r(abc)r(abcd)=r(abc) ).
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). What are the flats of MMM , by rank?
Rank 0 fff Rank 1 abf, cf, df, efabf, \ cf, \ df, \ efabf, cf, df, ef Rank 2 abcdf, abef, cef, defabcdf, \ abef, \ cef, \ defabcdf, abef, cef, def Rank 3 abcdefabcdefabcdef
[Rank, flats, hyperplanes and closure] Which facts about loops and flats hold in every matroid MMM on EEE ?
Loops Every loop is in every flat. Rank 0 There is exactly one flat of rank 0: the set of all loops. Example: with loop fff , the rank 0 flat is {f}\{f\}{f} . Empty set ∅\emptyset∅ is a flat if and only if MMM has no loops. Ground set EEE is the unique flat of rank r(M)r(M)r(M) .
[Rank, flats, hyperplanes and closure] eee is an isthmus and FFF a flat of a matroid. Which sets are then also flats?
F∪{e}F \cup \{e\}F∪{e} if e∉Fe \notin Fe∈/F , and F−{e}F - \{e\}F−{e} if e∈Fe \in Fe∈F . Example: with isthmus eee and loop fff , the flat abefabefabef gives the flat abfabfabf , and the flat cfcfcf gives the flat cefcefcef .
[Rank, flats, hyperplanes and closure] How does a partition Π\PiΠ of the vertices of a graph GGG give a flat of the cycle matroid M(G)M(G)M(G) ?
The flat is the set of edges whose two endpoints lie in the same block of Π\PiΠ . A block is a part of the partition. Adding any other edge joins two components, so the rank rises.Example: the partition of all vertices into singletons gives the flat of all loops.
[Rank, flats, hyperplanes and closure] Which flat of M(G)M(G)M(G) does the vertex partition Π={16,234,57}\Pi = \{16, 234, 57\}Π={16,234,57} give?
FΠ={b,c,f,h,k}\boldsymbol{F_\Pi = \{b, c, f, h, k\}}FΠ={b,c,f,h,k} Block 16: fff . Block 234: b,c,hb, c, hb,c,h . Block 57: kkk . Its rank is 7−3=47 - 3 = 47−3=4 (vertices minus components).
[Rank, flats, hyperplanes and closure] Which partition of the vertices of GGG gives the flat abef={a,b,e,f}abef = \{a, b, e, f\}abef={a,b,e,f} of M(G)M(G)M(G) ?
Two blocks: the two ends of aaa and bbb , and the two ends of eee . Every loop ( fff ) is in every such flat, since both its ends lie in the same block.
[Rank, flats, hyperplanes and closure] Proposition 2.19. If F1F_1F1 and F2F_2F2 are flats of a matroid, what is F1∩F2F_1 \cap F_2F1∩F2 ?
A flat. Example: lines abcdfabcdfabcdf and abefabefabef meet in the flat abfabfabf (a point with the loop fff ).
[Rank, flats, hyperplanes and closure] Proposition 2.20. FFF is a flat of a matroid and x∉Fx \notin Fx∈/F . What is r(F∪{x})r(F \cup \{x\})r(F∪{x}) ?
r(F)+1\boldsymbol{r(F) + 1}r(F)+1 Example: line abcdfabcdfabcdf (rank 2) plus the point eee off the line: rank 3.
[Rank, flats, hyperplanes and closure] A flat FFF satisfies r(F∪{x})>r(F)r(F \cup \{x\}) > r(F)r(F∪{x})>r(F) for each x∉Fx \notin Fx∈/F .Why is then r(F∪{x})≤r(F)+1r(F \cup \{x\}) \le r(F) + 1r(F∪{x})≤r(F)+1 ?
A largest independent I⊆F∪{x}I \subseteq F \cup \{x\}I⊆F∪{x} must contain xxx (else r(F)≥∣I∣r(F) \ge |I|r(F)≥∣I∣ ), so I−xI - xI−x is an independent subset of FFF of size r(F∪{x})−1r(F \cup \{x\}) - 1r(F∪{x})−1 .
[Rank, flats, hyperplanes and closure] Given only the flats of a matroid, how do you compute the rank r(A)r(A)r(A) of a set AAA ?
Find the smallest flat FAF_AFA containing AAA ; r(A)r(A)r(A) is the length of a maximal chain of flats F0⊊F1⊊⋯⊊Fr=FAF_0 \subsetneq F_1 \subsetneq \dots \subsetneq F_r = F_AF0⊊F1⊊⋯⊊Fr=FA . The length is one less than the number of flats in the chain; F0F_0F0 is the rank 0 flat. Example: flats f⊊abf⊊abcdff \subsetneq abf \subsetneq abcdff⊊abf⊊abcdf give r(ac)=2r(ac) = 2r(ac)=2 , since abcdfabcdfabcdf is the smallest flat containing acacac .
[Rank, flats, hyperplanes and closure] A matroid on E={a,b,c}E = \{a, b, c\}E={a,b,c} has flats ∅,ab,c,abc\emptyset, ab, c, abc∅,ab,c,abc ( ab={a,b}ab = \{a, b\}ab={a,b} ). What are r(a)r(a)r(a) , r(ab)r(ab)r(ab) , r(ac)r(ac)r(ac) and r(M)r(M)r(M) ?
r(a)=1, r(ab)=1, r(ac)=2, r(M)=2\boldsymbol{r(a) = 1, \ r(ab) = 1, \ r(ac) = 2, \ r(M) = 2}r(a)=1, r(ab)=1, r(ac)=2, r(M)=2 ∅\emptyset∅ is a flat, so there are no loops. No flat lies strictly between ∅\emptyset∅ and ababab , so r(ab)=1r(ab) = 1r(ab)=1 : a,ba, ba,b form a double point. The maximal chain ∅⊊ab⊊abc\emptyset \subsetneq ab \subsetneq abc∅⊊ab⊊abc has length 2.
[Rank, flats, hyperplanes and closure] What is a hyperplane of a matroid MMM ?
A flat HHH with r(H)=r(M)−1r(H) = r(M) - 1r(H)=r(M)−1 , i.e. a maximal flat other than EEE . Example: in a rank 3 matroid drawn in the plane, the hyperplanes are the lines (2-point lines included), each together with all loops.
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). What are the hyperplanes of MMM ?
abcdf, abef, cef, def\boldsymbol{abcdf, \ abef, \ cef, \ def}abcdf, abef, cef, def r(M)=3r(M) = 3r(M)=3 , so these are the rank 2 flats: the lines, each with the loop fff included. They have different sizes, so maximal = maximum fails for hyperplanes.
[Rank, flats, hyperplanes and closure] How do you get the hyperplanes from the flats F\mathcal{F}F of a matroid on EEE , and the flats from the hyperplanes?
Hyperplanes: the maximal members of F−{E}\mathcal{F} - \{E\}F−{E} . Flats: all intersections of collections of hyperplanes. EEE itself is the empty intersection. As in Euclidean space: a line is the intersection of two planes, a point of three.
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). Hyperplanes of MMM : abcdf,abef,cef,defabcdf, abef, cef, defabcdf,abef,cef,def .Write the rank 1 flats abf,cf,df,efabf, cf, df, efabf,cf,df,ef and the rank 0 flat fff as intersections of hyperplanes.
abf=abcdf∩abef, cf=abcdf∩cef, df=abcdf∩def, ef=cef∩def\boldsymbol{abf = abcdf \cap abef, \ cf = abcdf \cap cef, \ df = abcdf \cap def, \ ef = cef \cap def}abf=abcdf∩abef, cf=abcdf∩cef, df=abcdf∩def, ef=cef∩def fff is the intersection of all four hyperplanes. Each rank 1 flat is the meeting point of two lines in the picture.
[Rank, flats, hyperplanes and closure] What is a cocircuit of a matroid?
The complement E−HE - HE−H of a hyperplane HHH . Also called a bond (from graph theory). Equivalently, a set minimal with respect to not being contained in any basis complement.Example: hyperplanes abcdf,abef,cef,defabcdf, abef, cef, defabcdf,abef,cef,def of a matroid on {a,…,f}\{a, \dots, f\}{a,…,f} give the cocircuits e,cd,abd,abce, cd, abd, abce,cd,abd,abc .
[Rank, flats, hyperplanes and closure] What is the closure A‾\overline{A}A of a subset AAA of the ground set of a matroid with flats F\mathcal{F}F ?
The smallest flat containing AAA , i.e. A‾=⋂F∈F{F:A⊆F}\overline{A} = \bigcap_{F \in \mathcal{F}} \{F : A \subseteq F\}A=⋂F∈F{F:A⊆F} . Example: with a,b,c,da, b, c, da,b,c,d on a line and a loop fff , ad‾=abcdf\overline{ad} = abcdfad=abcdf .
[Rank, flats, hyperplanes and closure] Lemma 2.25. For a set AAA in a matroid with flats F\mathcal{F}F , why do the two descriptions of the closure, "the unique smallest flat containing AAA " and "the intersection of all flats containing AAA ", agree?
The intersection of flats is a flat, so the intersection of all flats containing AAA is a flat containing AAA and contained in every such flat. Only closure under intersection is used, so every intersection-closed family has such a closure operator. Defining a matroid by closure needs more axioms.
[Rank, flats, hyperplanes and closure] MMM is the matroid on E={a,b,c,d,e,f}E = \{a, b, c, d, e, f\}E={a,b,c,d,e,f} with bases ace,ade,bce,bde,cdeace, ade, bce, bde, cdeace,ade,bce,bde,cde (shorthand: ace={a,c,e}ace = \{a, c, e\}ace={a,c,e} ). What are ad‾\overline{ad}ad and a‾\overline{a}a ?
ad‾=abcdf, a‾=abf\boldsymbol{\overline{ad} = abcdf, \ \ \overline{a} = abf}ad=abcdf, a=abf The flats containing adadad are abcdfabcdfabcdf and EEE . The flats containing aaa are abfabfabf , abefabefabef , abcdfabcdfabcdf and EEE ; their intersection is abfabfabf .
[Rank, flats, hyperplanes and closure] How do you get the flats of a matroid from its closure operator?
The flats are the sets FFF with F‾=F\overline{F} = FF=F . Also A⊆A‾A \subseteq \overline{A}A⊆A and A‾‾=A‾\overline{\overline{A}} = \overline{A}A=A for every AAA , but these two properties alone do not define a matroid.
[Rank, flats, hyperplanes and closure] Which seven key concepts can each be used to define a matroid, and where do they come from?
Independent sets, bases, circuits, rank function (linear algebra, graph theory); flats, hyperplanes, closure operator (geometry, topology).
[Lattice of flats] What is a binary relation RRR on a set EEE ?
A subset of E×EE \times EE×E , the set of all ordered pairs (a,b)(a, b)(a,b) with a,b∈Ea, b \in Ea,b∈E . (a,b)∈R(a, b) \in R(a,b)∈R is read " aaa is related to bbb under RRR ".Example: on E={1,2}E = \{1, 2\}E={1,2} , R={(1,1),(1,2)}R = \{(1, 1), (1, 2)\}R={(1,1),(1,2)} is a binary relation.
[Lattice of flats] Which four properties may a binary relation RRR on a set EEE have?
Reflexive (a,a)∈R(a, a) \in R(a,a)∈R for all a∈Ea \in Ea∈E . Example: ≤\le≤ on Z\mathbb{Z}Z , since a≤aa \le aa≤a . Symmetric If (a,b)∈R(a, b) \in R(a,b)∈R , then (b,a)∈R(b, a) \in R(b,a)∈R . Example: "has the same parity as" on Z\mathbb{Z}Z . Antisymmetric If (a,b)∈R(a, b) \in R(a,b)∈R and (b,a)∈R(b, a) \in R(b,a)∈R , then a=ba = ba=b . Example: ≤\le≤ on Z\mathbb{Z}Z : a≤ba \le ba≤b and b≤ab \le ab≤a give a=ba = ba=b . Transitive If (a,b)∈R(a, b) \in R(a,b)∈R and (b,c)∈R(b, c) \in R(b,c)∈R , t…
[Lattice of flats] E={a,b,c,d}E = \{a, b, c, d\}E={a,b,c,d} and R={(a,a),(b,b),(c,c),(d,d),(a,b),(a,c),(a,d)}R = \{(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d)\}R={(a,a),(b,b),(c,c),(d,d),(a,b),(a,c),(a,d)} . Which of reflexive, symmetric, antisymmetric, transitive does RRR have?
Reflexive, antisymmetric and transitive, but not symmetric. (a,b)∈R(a, b) \in R(a,b)∈R but (b,a)∉R(b, a) \notin R(b,a)∈/R . So RRR is a partial order, with aaa below each of b,c,db, c, db,c,d .
[Lattice of flats] What is an equivalence relation?
A binary relation that is reflexive, symmetric and transitive. The most important one for matroids: on the ground set EEE , aaa is related to bbb if and only if a=ba = ba=b or some circuit contains both aaa and bbb .
[Lattice of flats] What is a partial order, and what is a poset (E,⪯)(E, \preceq)(E,⪯) ?
Partial order: a binary relation that is reflexive, antisymmetric and transitive. A poset is a set with a partial order. "Poset" abbreviates "partially ordered set".Example: subsets of {1,2}\{1, 2\}{1,2} ordered by ⊆\subseteq⊆ .
[Lattice of flats] What is the poset (Dn,∣)(D_n, |)(Dn,∣) ?
The positive divisors of nnn , ordered by divisibility. Example: D12={1,2,3,4,6,12}D_{12} = \{1, 2, 3, 4, 6, 12\}D12={1,2,3,4,6,12} ; 2∣42 \mid 42∣4 , but 4∤64 \nmid 64∤6 , so 4 and 6 are unrelated.
[Lattice of flats] In a poset, when does yyy cover xxx (written x⋖yx \lessdot yx⋖y )?
x≺yx \prec yx≺y , and no element zzz satisfies x≺z≺yx \prec z \prec yx≺z≺y . Example: in (D12,∣)(D_{12}, |)(D12,∣) , 6 covers 2, but 12 doesn't cover 2, since 2∣6∣122 \mid 6 \mid 122∣6∣12 .
[Lattice of flats] How is the Hasse diagram of a finite poset drawn?
One dot per element, and a segment going upwards from xxx to yyy whenever yyy covers xxx . By transitivity the covers determine the whole order: x⪯yx \preceq yx⪯y if and only if there is an upward path from xxx to yyy . Example: the Hasse diagram of (D12,∣)(D_{12}, |)(D12,∣) .
[Lattice of flats] What are a maximal element and a greatest element 1^\hat{1}1^ of a poset? (Minimal and least 0^\hat{0}0^ are analogous.)
Maximal: no element is above it ( x⪯yx \preceq yx⪯y implies x=yx = yx=y ). Greatest 1^\hat{1}1^ : every element is below it. Every finite poset has at least one maximal and one minimal element; a finite poset with exactly one maximal element has that element as 1^\hat{1}1^ .Example: {1,2,3}\{1, 2, 3\}{1,2,3} ordered by divisibility has maximal elements 2 and 3, no 1^\hat{1}1^ , and 0^=1\hat{0} = 10^=1 .
[Lattice of flats] What are a chain and a maximal chain in a poset?
Chain: distinct elements x1⪯x2⪯⋯⪯xkx_1 \preceq x_2 \preceq \cdots \preceq x_kx1⪯x2⪯⋯⪯xk . Maximal chain: a chain contained in no longer chain. Example: in (D12,∣)(D_{12}, |)(D12,∣) , 1,2,6,121, 2, 6, 121,2,6,12 is a maximal chain; 1,6,121, 6, 121,6,12 is a chain that is not maximal.
[Lattice of flats] When is a chain x1⪯⋯⪯xkx_1 \preceq \cdots \preceq x_kx1⪯⋯⪯xk saturated, and when is a poset graded?
Saturated: each xi+1x_{i+1}xi+1 covers xix_ixi . Graded: for all x,yx, yx,y , all saturated chains from xxx to yyy have the same length. The length of a saturated chain is its number of covering steps, k−1k - 1k−1 . (The book writes kkk , but then ρ(0^)\rho(\hat{0})ρ(0^) would be 1, not 0.)Example: (D12,∣)(D_{12}, |)(D12,∣) is graded: 1,2,4,121, 2, 4, 121,2,4,12 and 1,2,6,121, 2, 6, 121,2,6,12 and 1,3,6,121, 3, 6, 121,3,6,12 all have length 3.
[Lattice of flats] In a graded poset with least element 0^\hat{0}0^ , what is the rank ρ(x)\rho(x)ρ(x) of an element xxx ?
The length of a saturated chain from 0^\hat{0}0^ to xxx . Well defined because the poset is graded.Example: in (D12,∣)(D_{12}, |)(D12,∣) , ρ(1)=0\rho(1) = 0ρ(1)=0 , ρ(2)=ρ(3)=1\rho(2) = \rho(3) = 1ρ(2)=ρ(3)=1 , ρ(4)=ρ(6)=2\rho(4) = \rho(6) = 2ρ(4)=ρ(6)=2 , ρ(12)=3\rho(12) = 3ρ(12)=3 .
[Lattice of flats] What is the Boolean lattice BnB_nBn , and what are its 0^\hat{0}0^ , 1^\hat{1}1^ and rank function?
All subsets of [n]={1,…,n}[n] = \{1, \dots, n\}[n]={1,…,n} ordered by ⊆\subseteq⊆ ; 0^=∅\hat{0} = \varnothing0^=∅ , 1^=[n]\hat{1} = [n]1^=[n] , ρ(A)=∣A∣\boldsymbol{\rho(A) = |A|}ρ(A)=∣A∣ . BBB covers AAA if and only if B=A∪{x}B = A \cup \{x\}B=A∪{x} for some x∉Ax \notin Ax∈/A .Example: in B3B_3B3 , {1,2}\{1, 2\}{1,2} covers {1}\{1\}{1} and {2}\{2\}{2} , and ρ({1,2})=2\rho(\{1, 2\}) = 2ρ({1,2})=2 .
[Lattice of flats] In the Boolean lattice BnB_nBn (subsets of [n][n][n] under ⊆\subseteq⊆ ): how many maximal chains are there, and how many elements does a kkk -set AAA cover, and how many cover AAA ?
n!n!n! maximal chains; AAA covers kkk elements and is covered by n−kn - kn−k . A maximal chain adds the elements of [n][n][n] one at a time, in one of n!n!n! orders.Example: in B3B_3B3 , {1}\{1\}{1} covers ∅\varnothing∅ and is covered by {1,2}\{1, 2\}{1,2} and {1,3}\{1, 3\}{1,3} .
[Lattice of flats] BnB_nBn : subsets of [n][n][n] ordered by ⊆\subseteq⊆ . It has n!n!n! maximal chains.How do the maximal chains of BnB_nBn prove that there are n!k!(n−k)!\displaystyle\frac{n!}{k!(n-k)!}k!(n−k)!n! subsets of size kkk ?
Each of the n!n!n! maximal chains passes through exactly one kkk -set, and through each kkk -set pass k!(n−k)!k!(n-k)!k!(n−k)! of them. k!k!k! chains from ∅\varnothing∅ to the kkk -set times (n−k)!(n-k)!(n−k)! chains from it to [n][n][n] . So m⋅k!(n−k)!=n!m \cdot k!(n-k)! = n!m⋅k!(n−k)!=n! for mmm the number of kkk -sets.Example: n=3n = 3n=3 , k=1k = 1k=1 : m⋅1!⋅2!=6m \cdot 1! \cdot 2! = 6m⋅1!⋅2!=6 , so m=3m = 3m=3 .
[Lattice of flats] In a poset, what are the join x∨yx \vee yx∨y and the meet x∧yx \wedge yx∧y ?
Join: the least element of {z:x⪯z, y⪯z}\{z : x \preceq z, \ y \preceq z\}{z:x⪯z, y⪯z} . Meet: the greatest element of {w:w⪯x, w⪯y}\{w : w \preceq x, \ w \preceq y\}{w:w⪯x, w⪯y} . Each exists only if that element exists. Example: in (D12,∣)(D_{12}, |)(D12,∣) , 4∨6=124 \vee 6 = 124∨6=12 and 4∧6=24 \wedge 6 = 24∧6=2 .
[Lattice of flats] The join is also called the least upper bound or supremum; the meet is also called the greatest lower bound or infimum.
Both operations are associative, so a∨b∨ca \vee b \vee ca∨b∨c is unambiguous.
[Lattice of flats] What are A∨BA \vee BA∨B and A∧BA \wedge BA∧B in the Boolean lattice BnB_nBn , and a∨ba \vee ba∨b , a∧ba \wedge ba∧b in the divisor poset (Dn,∣)(D_n, |)(Dn,∣) ?
BnB_nBn : A∪BA \cup BA∪B and A∩BA \cap BA∩B . DnD_nDn : lcm(a,b)\operatorname{lcm}(a, b)lcm(a,b) and gcd(a,b)\gcd(a, b)gcd(a,b) . Example: in D12D_{12}D12 , 4∨6=lcm(4,6)=124 \vee 6 = \operatorname{lcm}(4, 6) = 124∨6=lcm(4,6)=12 and 4∧6=gcd(4,6)=24 \wedge 6 = \gcd(4, 6) = 24∧6=gcd(4,6)=2 .
[Lattice of flats] In this poset, what are a∨ba \vee ba∨b , d∧ed \wedge ed∧e and a∨ca \vee ca∨c ?
a∨b=d\boldsymbol{a \vee b = d}a∨b=d , d∧e=b\boldsymbol{d \wedge e = b}d∧e=b , a∨ca \vee ca∨c is not defined. The only upper bound of aaa other than aaa is ddd , and the elements above ccc are ccc and eee : no common upper bound. a∧ca \wedge ca∧c is not defined either.
[Lattice of flats] What is a lattice?
A finite poset in which every pair of elements has a join and a meet. Example: (Dn,∣)(D_n, |)(Dn,∣) and BnB_nBn are lattices.
[Lattice of flats] Why does a finite non-empty lattice LLL have a greatest element 1^\hat{1}1^ ?
The join of all its elements, x1∨x2∨⋯∨xmx_1 \vee x_2 \vee \cdots \vee x_mx1∨x2∨⋯∨xm , is above every element. Dually, the meet of all elements is the least element 0^\hat{0}0^ .Example: in (D12,∣)(D_{12}, |)(D12,∣) , 1∨2∨3∨4∨6∨12=12=1^1 \vee 2 \vee 3 \vee 4 \vee 6 \vee 12 = 12 = \hat{1}1∨2∨3∨4∨6∨12=12=1^ .
[Lattice of flats] What are the atoms and the coatoms of a lattice?
Atoms: the elements that cover 0^\hat{0}0^ . Coatoms: the elements covered by 1^\hat{1}1^ . Example: the atoms of (Dn,∣)(D_n, |)(Dn,∣) are the primes dividing nnn ; the atoms of BnB_nBn are the 1-element subsets.
[Lattice of flats] When is a lattice atomic?
Every element is a join of atoms. BnB_nBn is atomic: each AAA is the join of the singletons in AAA .Example: (D12,∣)(D_{12}, |)(D12,∣) is not atomic: its atoms are 2 and 3, and their joins are only 2, 3 and 6, so 4 is not a join of atoms.
[Lattice of flats] LLL is a lattice with rank function ρ\rhoρ . When is LLL semimodular, and when modular?
Semimodular: ρ(x∨y)+ρ(x∧y)≤ρ(x)+ρ(y)\rho(x \vee y) + \rho(x \wedge y) \le \rho(x) + \rho(y)ρ(x∨y)+ρ(x∧y)≤ρ(x)+ρ(y) for all x,yx, yx,y . Modular: the same with === . Modular lattices are semimodular, not conversely.Example: BnB_nBn is modular: ∣A∪B∣+∣A∩B∣=∣A∣+∣B∣|A \cup B| + |A \cap B| = |A| + |B|∣A∪B∣+∣A∩B∣=∣A∣+∣B∣ .
[Lattice of flats] What is a geometric lattice?
A lattice that is semimodular and atomic. Atomic: every element is a join of atoms. Semimodular: ρ(x∨y)+ρ(x∧y)≤ρ(x)+ρ(y)\rho(x \vee y) + \rho(x \wedge y) \le \rho(x) + \rho(y)ρ(x∨y)+ρ(x∧y)≤ρ(x)+ρ(y) .Example: BnB_nBn , which is atomic and modular.
[Lattice of flats] Theorem 2.45 Let M=(E,F)M = (E, \mathcal{F})M=(E,F) be a matroid with flats F\mathcal{F}F . Then (F,⊆)(\mathcal{F}, \subseteq)(F,⊆) is … ?
A geometric lattice (the lattice of flats of MMM ). Its 0^\hat{0}0^ is ∅‾\overline{\varnothing}∅ (the loops), its 1^\hat{1}1^ is EEE , its atoms are the rank 1 flats, and its rank function is the matroid rank.Garrett Birkhoff introduced geometric lattices, "stimulated by the matroid concept", and also called them matroid lattices.
[Lattice of flats] Is this lattice ( ∅,a,b,c,ab,bc,abc\varnothing, a, b, c, ab, bc, abc∅,a,b,c,ab,bc,abc under ⊆\subseteq⊆ ) geometric?
No: semimodularity fails for aaa and ccc . a∨c=abca \vee c = abca∨c=abc and a∧c=∅a \wedge c = \varnothinga∧c=∅ , so ρ(a∨c)+ρ(a∧c)=3+0>1+1=ρ(a)+ρ(c)\rho(a \vee c) + \rho(a \wedge c) = 3 + 0 > 1 + 1 = \rho(a) + \rho(c)ρ(a∨c)+ρ(a∧c)=3+0>1+1=ρ(a)+ρ(c) . (It is atomic.)
[Lattice of flats] This geometric lattice, with elements ∅,a,b,c,d,ad,bd,cd,abc,abcd\varnothing, a, b, c, d, ad, bd, cd, abc, abcd∅,a,b,c,d,ad,bd,cd,abc,abcd , is the lattice of flats of a matroid on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} . Which matroid?
Rank 3: a,b,ca, b, ca,b,c on a line, ddd off that line. The rank 2 flats abc,ad,bd,cdabc, ad, bd, cdabc,ad,bd,cd are the lines. This lattice is even modular.
[Lattice of flats] MMM is the rank 3 matroid drawn here: a,ba, ba,b are parallel (a double point), a,b,c,da, b, c, da,b,c,d lie on a line, eee is off that line, and fff is a loop (the cloud). What are the 0^\hat{0}0^ and the atoms of its lattice of flats?
0^=f\boldsymbol{\hat{0} = f}0^=f ; atoms: abfabfabf , cfcfcf , dfdfdf , efefef . Every flat contains the loop fff , and the parallel points a,ba, ba,b lie in the same flats. The lines (rank 2 flats) are abcdfabcdfabcdf , abefabefabef , cefcefcef , defdefdef .
[Tying it together with the rank function] Through which chain of cryptomorphisms does the book connect independent sets I\mathcal{I}I to hyperplanes H\mathcal{H}H ?
I↔rank r↔closure↔F↔H\boldsymbol{\mathcal{I} \leftrightarrow \text{rank } r \leftrightarrow \text{closure} \leftrightarrow \mathcal{F} \leftrightarrow \mathcal{H}}I↔rank r↔closure↔F↔H Rank is the bridge between the "linear algebraic" concepts (independent sets, bases, circuits) and the "geometric" ones (flats, hyperplanes, closure).