Ch.7: Other matroids

Chapter 7 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 7.1. Other matroids 7.2. Transversal matroids 7.3. Matching theory and SDRs 7.4. Finding nice bipartite graphs 7.5. Transversal matroids and geometry 7.6. Deletion, contraction and duality 7.7. Representations of transversal matroids 7.8. Hyperplane arrangements and matroids 7.9. Cutting cheese: counting regions

113 flashcards · Mathematics · by lakesare

Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses

[Other matroids] Besides graphs and matrices, which two combinatorial structures does the chapter "Other matroids" turn into matroids?
Matchings in bipartite graphs (transversal matroids) and hyperplane arrangements in Rn\mathbb{R}^nRn . Hyperplane arrangements are closely related to representable matroids.
[Transversal matroids] GGG is a bipartite graph with vertex bipartition V=X∪YV = X \cup YV=X∪Y . What is a matching NNN , and what does N=(I,J)N = (I, J)N=(I,J) mean?
A set of edges, no two of which share a vertex. N=(I,J)N = (I, J)N=(I,J) : I⊆XI \subseteq XI⊆X and J⊆YJ \subseteq YJ⊆Y are the vertices that NNN uses. Example: in this graph, {ay1, by2, ey3}\{a y_1, \ b y_2, \ e y_3\}{ay1, by2, ey3} is a matching N=({a,b,e},{y1,y2,y3})N = (\{a, b, e\}, \{y_1, y_2, y_3\})N=({a,b,e},{y1,y2,y3}) .
[Transversal matroids] GGG is a bipartite graph with vertex bipartition X∪YX \cup YX∪Y . What is the transversal matroid MGM_GMG ?
Ground set XXX ; independent sets: the sets I⊆XI \subseteq XI⊆X that can be matched, i.e. N=(I,J)N = (I, J)N=(I,J) for some matching NNN . Example: here {a,b,c}\{a, b, c\}{a,b,c} is dependent: a,b,ca, b, ca,b,c are joined only to y1y_1y1 and y2y_2y2 , so at most two of them can be matched.
[Transversal matroids] Which practical problem motivates transversal matroids?
The job assignment problem: which sets of applicants can be hired so that each one fills a different job. XXX = applicants, YYY = jobs, an edge joins an applicant to each job the applicant is qualified for. The sets of applicants that can be hired together are the independent sets of MGM_GMG .
[Transversal matroids] In the book, what do MGM_GMG , M(G)M(G)M(G) and M[A]M[A]M[A] denote, and why is a matching written NNN ?
MGM_GMG : transversal matroid of a bipartite GGG ; M(G)M(G)M(G) : graphic (cycle) matroid of GGG ; M[A]M[A]M[A] : representable matroid of the columns of a matrix AAA . The letter MMM is reserved for the matroid, so a matching is called NNN .
[Transversal matroids] Which transversal matroids do G1G_1G1 and G2G_2G2 give on X={a,b,c,d,e,f}X = \{a, b, c, d, e, f\}X={a,b,c,d,e,f} ?
The same one: rank 3, {a,b,c,d}\{a, b, c, d\}{a,b,c,d} is a four-point line, eee and fff are off the line. ∣Y∣=3|Y| = 3∣Y∣=3 , so the bases are the matchable 3-sets. In both graphs a,b,c,da, b, c, da,b,c,d are joined only to y1,y2y_1, y_2y1,y2 , so no 3-subset of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} can be matched; every other 3-subset can.
[Transversal matroids] MMM has ground set {a,b,c,d,e,f}\{a, b, c, d, e, f\}{a,b,c,d,e,f} and rank 3, and its only dependent 3-sets are the 3-subsets of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} (a four-point line, with eee and fff off the line).How many bases does MMM have?
16 All 3-sets except the 3-subsets of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} : (63)−(43)=20−4=16\binom{6}{3} - \binom{4}{3} = 20 - 4 = 16(36)−(34)=20−4=16 .
[Transversal matroids] MMM has ground set {a,b,c,d,e,f}\{a, b, c, d, e, f\}{a,b,c,d,e,f} and rank 3, and its only dependent 3-sets are the 3-subsets of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} (a four-point line, with eee and fff off the line).Which sets are the circuits of MMM ?
The four 3-subsets of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} , and the six sets {x,y,e,f}\{x, y, e, f\}{x,y,e,f} with x,y∈{a,b,c,d}x, y \in \{a, b, c, d\}x,y∈{a,b,c,d} . A 4-set with exactly two points of the line has only independent 3-subsets, and every 4-set is dependent in rank 3. A 4-set with three or four points of the line contains a dependent 3-set.
[Transversal matroids] Theorem 7.2 Let GGG be a bipartite graph with vertex partition X∪YX \cup YX∪Y , and let I\mathcal{I}I be the collection of sets I⊆XI \subseteq XI⊆X such that III is the set of XXX -vertices of some matching N=(I,J)N = (I, J)N=(I,J) . Then … ?
I\mathcal{I}I satisfies the independent set axioms (I1), (I2), (I3). So the transversal matroid MGM_GMG is a matroid.Example: in a graph with R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(d)={y2}R(d) = \{y_2\}R(d)={y2} , R(e)={y1,y2,y3}R(e) = \{y_1, y_2, y_3\}R(e)={y1,y2,y3} , the set {a,d,e}\{a, d, e\}{a,d,e} can be matched, and so can each of its subsets, as (I2) requires.
[Transversal matroids] GGG is a bipartite graph with X={x1,…,xn}X = \{x_1, \dots, x_n\}X={x1,…,xn} , Y={y1,…,ym}Y = \{y_1, \dots, y_m\}Y={y1,…,ym} .Which matrix AAA does the proof that the matchable subsets of XXX form a matroid use?
Rows indexed by YYY , columns by XXX , and aij=zija_{ij} = z_{ij}aij=zij if an edge joins xjx_jxj to yiy_iyi , aij=0a_{ij} = 0aij=0 otherwise, where the zijz_{ij}zij are independent indeterminates. The proof shows: the linearly independent sets of columns of AAA are exactly the matchable subsets of XXX . Linearly independent column sets are already known to form a matroid M[A]M[A]M[A] .Example: for the graph G1G_1G1 with R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(b)=R(c)={y1,y2}R(b) = R(c) =…
[Transversal matroids] AAA has rows indexed by YYY , columns by XXX , and entry zijz_{ij}zij (an independent indeterminate) where xjyix_j y_ixjyi is an edge of the bipartite graph GGG , 0 elsewhere.Why are the columns of AAA indexed by a matchable set III linearly independent?
The square submatrix on the columns III and their matched rows has determinant ≠0\neq 0=0 . Reorder so that xkx_kxk is matched to yky_kyk . The determinant expansion contains the term ∏i=1∣I∣zii\prod_{i=1}^{|I|} z_{ii}∏i=1∣I∣zii (the matching edges), and no other term cancels it, since the zijz_{ij}zij are independent indeterminates.Example: R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(d)={y2}R(d) = \{y_2\}R(d)={y2} , R(e)={y1,y2,y3}R(e) = \{y_1, y_2, y_3\}R(e)={y1,y2,y3} : columns a,d,ea, d…
[Transversal matroids] AAA has rows indexed by YYY , columns by XXX , and entry zijz_{ij}zij (an independent indeterminate) where xjyix_j y_ixjyi is an edge of the bipartite graph GGG , 0 elsewhere.Why does a linearly independent set III of columns of AAA give a matching of III ?
Some ∣I∣|I|∣I∣ nonzero entries zijz_{ij}zij of these columns lie in distinct rows and distinct columns; their edges form a matching of III . Such entries exist because row reducing the columns of III gives an ∣I∣×∣I∣|I| \times |I|∣I∣×∣I∣ identity matrix (with zero rows below).Example: if a,b,ca, b, ca,b,c are joined only to y1,y2y_1, y_2y1,y2 , their columns are nonzero only in 2 rows, so they are dependent, and indeed {a,b,c}\{a, b, c\}{a,b,c} cannot be matched.
[Transversal matroids] Besides the matrix proof, the fact that matchable sets form a matroid can be proved with the augmenting path algorithm, which also shows directly that all maximal matchable subsets of X have the same size.
Example: R(a)={y1,y2}R(a) = \{y_1, y_2\}R(a)={y1,y2} , R(b)={y1}R(b) = \{y_1\}R(b)={y1} . The matching {ay1}\{a y_1\}{ay1} cannot be extended, but the augmenting path b,y1,a,y2b, y_1, a, y_2b,y1,a,y2 swaps edges and gives {by1,ay2}\{b y_1, a y_2\}{by1,ay2} , so {a}\{a\}{a} is not a maximal matchable set.
[Transversal matroids] Every transversal matroid MMM has a bipartite presentation (a graph GGG with MG=MM_G = MMG=M ) with ∣Y∣=r(M)|Y| = r(M)∣Y∣=r(M) . Why is this rank-2 matroid, with parallel pairs {a,b}\{a, b\}{a,b} , {c,d}\{c, d\}{c,d} , {e,f}\{e, f\}{e,f} , not transversal?
With ∣Y∣=2|Y| = 2∣Y∣=2 , each parallel pair is joined to a single vertex of YYY , and ababab , cdcdcd use different vertices; then e,fe, fe,f share a vertex with aaa or with ccc . If eee and aaa are both joined only to y1y_1y1 , then {a,e}\{a, e\}{a,e} cannot be matched, but {a,e}\{a, e\}{a,e} is independent in this matroid.Why one vertex per pair: if aaa and bbb had different neighbours, {a,b}\{a, b\}{a,b} could be matched.
[Matching theory and SDRs] XXX is a finite set and F={S1,S2,…,Sk}\mathcal{F} = \{S_1, S_2, \dots, S_k\}F={S1,S2,…,Sk} a family of subsets of XXX . When is B={x1,x2,…,xk}⊆XB = \{x_1, x_2, \dots, x_k\} \subseteq XB={x1,x2,…,xk}⊆X a system of distinct representatives (SDR) for F\mathcal{F}F ?
When xi∈Six_i \in S_ixi∈Si for 1≤i≤k1 \le i \le k1≤i≤k . BBB is also called a transversal of F\mathcal{F}F . Interpretation: XXX is a group of people, the SiS_iSi are clubs, and each club gets one representative, nobody representing two clubs.Example: S1={a,b,c,e}S_1 = \{a, b, c, e\}S1={a,b,c,e} , S2={b,c,d,e}S_2 = \{b, c, d, e\}S2={b,c,d,e} , S3={e,f}S_3 = \{e, f\}S3={e,f} : {a,d,e}\{a, d, e\}{a,d,e} is an SDR, since a∈S1a \in S_1a∈S1 , d∈S2d \in S_2d∈S2 , e∈S3e \in S_3e∈S3 .
[Matching theory and SDRs] How do you turn a set system F={S1,…,Sk}\mathcal{F} = \{S_1, \dots, S_k\}F={S1,…,Sk} on a ground set XXX into a bipartite graph?
Vertex classes XXX and Y={S1,…,Sk}Y = \{S_1, \dots, S_k\}Y={S1,…,Sk} ; join xxx to SjS_jSj exactly when x∈Sjx \in S_jx∈Sj . Example: S1={a,b,c,e}S_1 = \{a, b, c, e\}S1={a,b,c,e} , S2={b,c,d,e}S_2 = \{b, c, d, e\}S2={b,c,d,e} , S3={e,f}S_3 = \{e, f\}S3={e,f} give this graph ( yj=Sjy_j = S_jyj=Sj ):
[Matching theory and SDRs] Translate the matroid terms independent set and basis of a transversal matroid into bipartite graphs and into set systems.
Independent set Bipartite graph: a set of XXX -vertices covered by a matching. Set system: a partial transversal (an SDR of a subfamily of F\mathcal{F}F ). Example: S1={a,b,c,e}S_1 = \{a, b, c, e\}S1={a,b,c,e} , S2={b,c,d,e}S_2 = \{b, c, d, e\}S2={b,c,d,e} , S3={e,f}S_3 = \{e, f\}S3={e,f} : {a,d}\{a, d\}{a,d} is a partial transversal ( a∈S1a \in S_1a∈S1 , d∈S2d \in S_2d∈S2 ), matched by ay1a y_1ay1 , dy2d y_2dy2 . Basis Bipartite graph: the XXX -vertices of a matching of largest size. Se…
[Matching theory and SDRs] GGG is a bipartite graph with V=(X,Y)V = (X, Y)V=(X,Y) . What are R(A)R(A)R(A) for A⊆XA \subseteq XA⊆X and R−1(Z)R^{-1}(Z)R−1(Z) for Z⊆YZ \subseteq YZ⊆Y ?
R(A)R(A)R(A) : the vertices of YYY joined to some vertex of AAA ; R−1(Z)R^{-1}(Z)R−1(Z) : the vertices of XXX joined to some vertex of ZZZ . Example: here R({a,b,c})={y1,y2}R(\{a, b, c\}) = \{y_1, y_2\}R({a,b,c})={y1,y2} and R−1({y3})={e,f}R^{-1}(\{y_3\}) = \{e, f\}R−1({y3})={e,f} .
[Matching theory and SDRs] What is the fundamental question of matching theory?
Given a bipartite graph GGG with V=(X,Y)V = (X, Y)V=(X,Y) and A⊆XA \subseteq XA⊆X : when can AAA be matched into YYY ? Hall's theorem answers it: exactly when ∣R(S)∣≥∣S∣|R(S)| \ge |S|∣R(S)∣≥∣S∣ for all S⊆AS \subseteq AS⊆A .
[Matching theory and SDRs] GGG is bipartite with V=(X,Y)V = (X, Y)V=(X,Y) , A⊆XA \subseteq XA⊆X , and R(S)R(S)R(S) is the set of neighbours of SSS . Why can AAA not be matched into YYY if ∣R(S)∣<∣S∣|R(S)| < |S|∣R(S)∣<∣S∣ for some S⊆AS \subseteq AS⊆A ?
By the pigeonhole principle: the ∣S∣|S|∣S∣ vertices of SSS need ∣S∣|S|∣S∣ distinct partners, all in R(S)R(S)R(S) , which has fewer. Example: in a graph where a,b,ca, b, ca,b,c are joined only to y1,y2y_1, y_2y1,y2 , ∣R({a,b,c})∣=2<3|R(\{a, b, c\})| = 2 < 3∣R({a,b,c})∣=2<3 , so {a,b,c}\{a, b, c\}{a,b,c} cannot be matched and is dependent in the transversal matroid.
[Matching theory and SDRs] Hall's Theorem (Theorem 7.6) Let GGG be a bipartite graph with vertices V=(X,Y)V = (X, Y)V=(X,Y) and let A⊆XA \subseteq XA⊆X . Then AAA can be matched into YYY if and only if … ?
∣R(S)∣≥∣S∣\boldsymbol{|R(S)| \ge |S|}∣R(S)∣≥∣S∣ for all S⊆AS \subseteq AS⊆A , where R(S)R(S)R(S) is the set of neighbours of SSS . So the obvious necessary condition is also sufficient. Proved by Philip Hall in 1935.Example: R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(d)={y2}R(d) = \{y_2\}R(d)={y2} , R(e)={y1,y2,y3}R(e) = \{y_1, y_2, y_3\}R(e)={y1,y2,y3} : every S⊆{a,d,e}S \subseteq \{a, d, e\}S⊆{a,d,e} has ∣R(S)∣≥∣S∣|R(S)| \ge |S|∣R(S)∣≥∣S∣ (e.g. R({a,d})={y1,y2}R(\{a, d\}) = \{y_1, y_2\}R({a,d}…
[Matching theory and SDRs] Hall's Theorem is often called the Marriage Theorem.
The two vertex classes are women and men, edges join mutually compatible pairs, and a matching is a set of marriages. Example: women a,ba, ba,b both compatible only with man y1y_1y1 : ∣R({a,b})∣=1<2|R(\{a, b\})| = 1 < 2∣R({a,b})∣=1<2 , so not both can marry.
[Matching theory and SDRs] GGG is bipartite with V=(X,Y)V = (X, Y)V=(X,Y) and R(S)R(S)R(S) is the set of neighbours of SSS . What is the deficiency δ(A)\delta(A)δ(A) of A⊆XA \subseteq XA⊆X ?
δ(A)=max⁡S⊆A(∣S∣−∣R(S)∣)\boldsymbol{\delta(A) = \max_{S \subseteq A} \big(|S| - |R(S)|\big)}δ(A)=maxS⊆A(∣S∣−∣R(S)∣) S=∅S = \emptysetS=∅ gives 0, so δ(A)≥0\delta(A) \ge 0δ(A)≥0 .Example: in G1G_1G1 ( R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(b)=R(c)={y1,y2}R(b) = R(c) = \{y_1, y_2\}R(b)=R(c)={y1,y2} , R(d)={y2}R(d) = \{y_2\}R(d)={y2} , R(e)={y1,y2,y3}R(e) = \{y_1, y_2, y_3\}R(e)={y1,y2,y3} , R(f)={y3}R(f) = \{y_3\}R(f)={y3} ): δ({a,b,c})=3−2=1\delta(\{a, b, c\}) = 3 - 2 = 1δ({a,b,c})=3−2=1…
[Matching theory and SDRs] Ore's Theorem (Theorem 7.7) Let GGG be a bipartite graph with vertices V=(X,Y)V = (X, Y)V=(X,Y) and A⊆XA \subseteq XA⊆X , with deficiency δ(A)=max⁡S⊆A(∣S∣−∣R(S)∣)\delta(A) = \max_{S \subseteq A}(|S| - |R(S)|)δ(A)=maxS⊆A(∣S∣−∣R(S)∣) . The size of the largest subset of AAA that can be matched into YYY is … ?
∣A∣−δ(A)\boldsymbol{|A| - \delta(A)}∣A∣−δ(A) So the rank in the transversal matroid is r(A)=∣A∣−δ(A)r(A) = |A| - \delta(A)r(A)=∣A∣−δ(A) . With δ(A)=0\delta(A) = 0δ(A)=0 this gives Hall's theorem.Example: in G1G_1G1 , δ({a,b,c})=1\delta(\{a, b, c\}) = 1δ({a,b,c})=1 , δ({e})=0\delta(\{e\}) = 0δ({e})=0 , δ(X)=3\delta(X) = 3δ(X)=3 , so r({a,b,c})=2r(\{a, b, c\}) = 2r({a,b,c})=2 , r({e})=1r(\{e\}) = 1r({e})=1 , r(X)=3r(X) = 3r(X)=3 .
[Matching theory and SDRs] G1G_1G1 is the bipartite graph with X={a,b,c,d,e,f}X = \{a, b, c, d, e, f\}X={a,b,c,d,e,f} , Y={y1,y2,y3}Y = \{y_1, y_2, y_3\}Y={y1,y2,y3} and R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(b)=R(c)={y1,y2}R(b) = R(c) = \{y_1, y_2\}R(b)=R(c)={y1,y2} , R(d)={y2}R(d) = \{y_2\}R(d)={y2} , R(e)={y1,y2,y3}R(e) = \{y_1, y_2, y_3\}R(e)={y1,y2,y3} , R(f)={y3}R(f) = \{y_3\}R(f)={y3} ( R(x)R(x)R(x) = neighbours of xxx ).Compute r({a,b,c,d,e})r(\{a, b, c, d, e\})r({a,b,c,d,e})…
r=3\boldsymbol{r = 3}r=3 S={a,b,c,d}S = \{a, b, c, d\}S={a,b,c,d} gives 4−2=24 - 2 = 24−2=2 , and no SSS gives more ( S={a,b,c,d,e}S = \{a, b, c, d, e\}S={a,b,c,d,e} gives 5−3=25 - 3 = 25−3=2 ). So r=5−2=3r = 5 - 2 = 3r=5−2=3 ; e.g. ay1,dy2,ey3a y_1, d y_2, e y_3ay1,dy2,ey3 .
[Finding nice bipartite graphs] What is a presentation of a transversal matroid MMM ?
A bipartite graph GGG with MG=MM_G = MMG=M . A transversal matroid usually has many presentations. Example: G1G_1G1 and G2G_2G2 are two presentations of the same matroid (rank 3, four-point line abcdabcdabcd , points e,fe, fe,f off it).
[Finding nice bipartite graphs] H1H_1H1 and H2H_2H2 present the same transversal matroid MMM . Which matroid is MMM ?
Rank 3: ccc is an isthmus, and a,b,da, b, da,b,d form a three-point line. a,b,da, b, da,b,d are all joined to the same two vertices, so any two of them can be matched but not all three. ccc is the only element joined to the third and fourth vertices of YYY , so ccc is in every basis.
[Finding nice bipartite graphs] Both graphs present the same rank-3 matroid. What is the defect of H1H_1H1 , and how is it removed?
∣Y∣=4>r(M)=3|Y| = 4 > r(M) = 3∣Y∣=4>r(M)=3 : the isthmus ccc is joined to two vertices that no other element uses. Delete one of them. H2H_2H2 is the result, with ∣Y∣=3|Y| = 3∣Y∣=3 . This redundancy at isthmuses is the only obstacle to a presentation with ∣Y∣=r(M)|Y| = r(M)∣Y∣=r(M) .
[Finding nice bipartite graphs] Proposition 7.9 If MMM is a transversal matroid, then there is a presentation in which … ?
∣Y∣=r(M)\boldsymbol{|Y| = r(M)}∣Y∣=r(M) Then the incidence matrix with indeterminates (rows YYY , columns XXX ) has full row rank.Example: the matroid with isthmus ccc and three-point line abdabdabd has rank 3, presented with Y={y1,y2,y3}Y = \{y_1, y_2, y_3\}Y={y1,y2,y3} by R(a)=R(b)=R(d)={y1,y2}R(a) = R(b) = R(d) = \{y_1, y_2\}R(a)=R(b)=R(d)={y1,y2} , R(c)={y3}R(c) = \{y_3\}R(c)={y3} .
[Finding nice bipartite graphs] When is a flat FFF of a matroid MMM cyclic?
When FFF is a union of circuits. Equivalently: r(F−x)=r(F)r(F - x) = r(F)r(F−x)=r(F) for all x∈Fx \in Fx∈F , and r(F∪x)=r(F)+1r(F \cup x) = r(F) + 1r(F∪x)=r(F)+1 for all x∉Fx \notin Fx∈/F .Example: in the rank-3 matroid with four-point line abcdabcdabcd and points e,fe, fe,f off it, {a,b,c,d}\{a, b, c, d\}{a,b,c,d} is a cyclic flat of rank 2 (the union of the circuits abcabcabc , abdabdabd , ...); the flat {a,e}\{a, e\}{a,e} is not cyclic.
[Finding nice bipartite graphs] Lemma 7.10 (1). MMM is a transversal matroid with presentation GGG , R(S)R(S)R(S) is the set of neighbours of SSS , and CCC is a circuit of MMM . ∣R(C)∣= ?|R(C)| = \; ?∣R(C)∣=?
∣R(C)∣=∣C∣−1\boldsymbol{|R(C)| = |C| - 1}∣R(C)∣=∣C∣−1 C−xC - xC−x is matchable, so ∣R(C)∣≥∣C∣−1|R(C)| \ge |C| - 1∣R(C)∣≥∣C∣−1 . CCC is not matchable, so by Hall some S⊆CS \subseteq CS⊆C has ∣R(S)∣<∣S∣|R(S)| < |S|∣R(S)∣<∣S∣ ; proper subsets of CCC are independent, so S=CS = CS=C .Example: if a,b,ca, b, ca,b,c are joined only to y1,y2y_1, y_2y1,y2 , the circuit {a,b,c}\{a, b, c\}{a,b,c} has ∣R({a,b,c})∣=2|R(\{a, b, c\})| = 2∣R({a,b,c})∣=2 .
[Finding nice bipartite graphs] Lemma 7.10 (2). MMM is a transversal matroid, FFF is a cyclic flat of MMM (a flat that is a union of circuits) of rank kkk , and R(F)R(F)R(F) is the set of neighbours of FFF . In any presentation of MMM , ∣R(F)∣= ?|R(F)| = \; ?∣R(F)∣=?
∣R(F)∣=k\boldsymbol{|R(F)| = k}∣R(F)∣=k Example: the four-point line F={a,b,c,d}F = \{a, b, c, d\}F={a,b,c,d} (rank 2) has R(F)={y1,y2}R(F) = \{y_1, y_2\}R(F)={y1,y2} in both presentations G1G_1G1 and G2G_2G2 .
[Finding nice bipartite graphs] FFF is a cyclic flat of rank kkk of a transversal matroid with a presentation GGG . B={x1,…,xk}B = \{x_1, \dots, x_k\}B={x1,…,xk} is a basis of FFF , matched by xiyix_i y_ixiyi , and B′={y1,…,yk}B' = \{y_1, \dots, y_k\}B′={y1,…,yk} .Why is R(x)⊆B′R(x) \subseteq B'R(x)⊆B′ for every x∈F−Bx \in F - Bx∈F−B ?
If xxx were joined to some y∉B′y \notin B'y∈/B′ , then {x,x1,…,xk}\{x, x_1, \dots, x_k\}{x,x1,…,xk} could be matched, so r(F)>kr(F) > kr(F)>k . This is Claim 1 in the proof that ∣R(F)∣=k|R(F)| = k∣R(F)∣=k .
[Finding nice bipartite graphs] FFF is a cyclic flat of rank kkk of a transversal matroid with a presentation GGG . B={x1,…,xk}B = \{x_1, \dots, x_k\}B={x1,…,xk} is a basis of FFF , matched by xiyix_i y_ixiyi , and B′={y1,…,yk}B' = \{y_1, \dots, y_k\}B′={y1,…,yk} . Every circuit CCC has ∣R(C)∣=∣C∣−1|R(C)| = |C| - 1∣R(C)∣=∣C∣−1 .Why is R(B)=B′R(B) = B'R(B)=B′ ?
Suppose x1x_1x1 is joined to y∉B′y \notin B'y∈/B′ . Since FFF is cyclic, x1x_1x1 is in a basic circuit C={x,x1,…,xm}C = \{x, x_1, \dots, x_m\}C={x,x1,…,xm} with x∈F−Bx \in F - Bx∈F−B ; then ∣R(C)∣=m|R(C)| = m∣R(C)∣=m , but R({x1,…,xm})⊇{y1,…,ym,y}R(\{x_1, \dots, x_m\}) \supseteq \{y_1, \dots, y_m, y\}R({x1,…,xm})⊇{y1,…,ym,y} has m+1m + 1m+1 elements. A basic circuit with respect to BBB is the unique circuit in B∪xB \cup xB∪x for an x∉Bx \notin Bx∈/B . Together with R(x)⊆B′R(x) \sub…
[Finding nice bipartite graphs] In any presentation of a transversal matroid, a cyclic flat FFF (a flat that is a union of circuits) of rank kkk has exactly kkk neighbours.How does this prove that every transversal matroid MMM has a presentation with ∣Y∣=r(M)|Y| = r(M)∣Y∣=r(M) ?
Without its isthmuses, MMM is a cyclic flat, so it needs exactly r(M)−ir(M) - ir(M)−i vertices of YYY ( iii isthmuses); then each isthmus gets one new vertex. Without isthmuses every element is in a circuit, and the whole ground set is a flat. The new vertex of an isthmus xxx is joined only to xxx ; each isthmus adds 1 to the rank and 1 vertex to YYY .Example: in a presentation where ccc is an isthmus joined to two private vertices, ccc is joined to one new vertex instead.
[Finding nice bipartite graphs] When is a presentation of a transversal matroid minimal, and when is it maximal?
Minimal: removing any edge changes the matchable subsets of XXX . Maximal: adding any edge changes them. Example: G1G_1G1 is minimal and G2G_2G2 is maximal; both present the rank-3 matroid with four-point line abcdabcdabcd and e,fe, fe,f off it. Adding ay3a y_3ay3 to G2G_2G2 would make {a,b,c}\{a, b, c\}{a,b,c} matchable.
[Transversal matroids and geometry] How do you draw the transversal matroid MGM_GMG of a presentation GGG with vertex classes XXX , YYY ?
Draw a simplex whose vertices are labelled by YYY , and place each x∈Xx \in Xx∈X freely in the interior of the face spanned by R(x)R(x)R(x) (the neighbours of xxx ). A face can be a vertex, an edge, a triangle, ..., or the whole simplex (if R(x)=YR(x) = YR(x)=Y ).Example: ∣Y∣=4|Y| = 4∣Y∣=4 gives a tetrahedron. R(c)={y1,y2}R(c) = \{y_1, y_2\}R(c)={y1,y2} puts ccc on the edge y1y2‾\overline{y_1 y_2}y1y2 ; R(a)={y1}R(a) = \{y_1\}R(a)={y1} puts aaa at the vertex y1y_1y1 .
[Transversal matroids and geometry] Draw MGM_GMG on a tetrahedron with vertices y1,y2,y3,y4y_1, y_2, y_3, y_4y1,y2,y3,y4 : where do aaa , ccc , ddd and ggg go?
aaa at the vertex y1y_1y1 ; ccc on the edge y1y2‾\overline{y_1 y_2}y1y2 ; ddd in the interior of the triangle y1y2y4y_1 y_2 y_4y1y2y4 ; ggg on the edge y2y4‾\overline{y_2 y_4}y2y4 . R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(b)=R(c)={y1,y2}R(b) = R(c) = \{y_1, y_2\}R(b)=R(c)={y1,y2} , R(d)=R(e)={y1,y2,y4}R(d) = R(e) = \{y_1, y_2, y_4\}R(d)=R(e)={y1,y2,y4} , R(f)={y2,y3}R(f) = \{y_2, y_3\}R(f)={y2,y3} , R(g)={y2,y4}R(g) = \{y_2, y_4\}R(g)={y2,y4} .
[Transversal matroids and geometry] GGG has Y={y1,y2,y3,y4}Y = \{y_1, y_2, y_3, y_4\}Y={y1,y2,y3,y4} and R(a)={y1}R(a) = \{y_1\}R(a)={y1} , R(b)=R(c)={y1,y2}R(b) = R(c) = \{y_1, y_2\}R(b)=R(c)={y1,y2} , R(d)=R(e)={y1,y2,y4}R(d) = R(e) = \{y_1, y_2, y_4\}R(d)=R(e)={y1,y2,y4} , R(f)={y2,y3}R(f) = \{y_2, y_3\}R(f)={y2,y3} , R(g)={y2,y4}R(g) = \{y_2, y_4\}R(g)={y2,y4} .What is r(MG)r(M_G)r(MG) , and why is fff an isthmus?
r(MG)=4r(M_G) = 4r(MG)=4 ; fff is the only element joined to y3y_3y3 , so every basis (a set matched onto all of YYY ) contains fff . A matching of size 4: ay1,by2,dy4,fy3a y_1, b y_2, d y_4, f y_3ay1,by2,dy4,fy3 . The other six points lie in a plane (they use only y1,y2,y4y_1, y_2, y_4y1,y2,y4 ), with the three-point line abcabcabc :
[Transversal matroids and geometry] What is the convex hull of a set of points in Euclidean space?
The smallest convex set containing all the points. Example: the convex hull of three non-collinear points in R2\mathbb{R}^2R2 is the filled triangle they span.
[Transversal matroids and geometry] What is an nnn -simplex?
The convex hull of n+1n + 1n+1 points in general position in Rn\mathbb{R}^nRn . Example: a 2-simplex is a triangle, a 3-simplex is a tetrahedron.
[Transversal matroids and geometry] SSS is a simplex in Euclidean space. When is a set EEE of points in Rn\mathbb{R}^nRn free-simplicial?
When all points of EEE are placed freely on faces of various dimensions of SSS (including the interior of SSS ). EEE is a matroid under affine dependence. Example: points a,ba, ba,b at one vertex of a triangle, c,dc, dc,d at another, e,fe, fe,f at the third, and ggg in the interior.
[Transversal matroids and geometry] MMM is a free-simplicial matroid with its points on a simplex SSS . Where do the points of a circuit CCC lie when ∣C∣=2|C| = 2∣C∣=2 , 333 , 444 ?
∣C∣=2|C| = 2∣C∣=2 : both at one vertex; ∣C∣=3|C| = 3∣C∣=3 : on an edge; ∣C∣=4|C| = 4∣C∣=4 : on a two-dimensional face of SSS . In general, a circuit CCC lies on a face of dimension ∣C∣−2|C| - 2∣C∣−2 . Example: {b,c,d}\{b, c, d\}{b,c,d} is a circuit on the edge y1y2‾\overline{y_1 y_2}y1y2 .
[Transversal matroids and geometry] In a free-simplicial set, why must three points in the interior of a face of dimension at least 2 be independent?
There are no accidental dependences: freely placed points satisfy only the dependences forced by the faces that contain them. The independent indeterminates zijz_{ij}zij in the incidence-matrix proof that matchable sets form a matroid play the same role; the free-simplicial picture is a geometric realization of them.Example: d,ed, ed,e in the interior of the triangle y1y2y4y_1 y_2 y_4y1y2y4 and ccc on its edge y1y2‾\overline{y_1 y_2}y1y2 are not collinear; matching: cy1,dy2,ey4c y_1, d y…
[Transversal matroids and geometry] Brylawski's Theorem (Theorem 7.13) A matroid MMM is a transversal matroid if and only if … ?
MMM is isomorphic to a free-simplicial set in Euclidean space. A free-simplicial set: points placed freely on faces of a simplex. Example: the matroid with four-point line abcdabcdabcd and e,fe, fe,f off it, drawn on a triangle.
[Transversal matroids and geometry] Brylawski: MMM is transversal if and only if MMM is isomorphic to a free-simplicial set (points placed freely on faces of a simplex).How does the proof go in each direction?
⇒\Rightarrow⇒ : place each xxx freely on the face spanned by R(x)R(x)R(x) , in a presentation with ∣Y∣=r(M)|Y| = r(M)∣Y∣=r(M) . ⇐\Leftarrow⇐ : join each point to the vertices of its face. A set of ddd points of the picture is independent if and only if the points lie on a face of dimension at least d−1d - 1d−1 , which by the placement happens exactly when the points can be matched.Example: R(c)={y1,y2}R(c) = \{y_1, y_2\}R(c)={y1,y2} puts ccc on the edge y1y2‾\overline{y_1 y_2}y1y2 , and co…
[Transversal matroids and geometry] G1G_1G1 is a minimal and G2G_2G2 a maximal presentation of the same matroid. How do their free-simplicial pictures differ?
Minimal: points on low-dimensional faces ( a,d,fa, d, fa,d,f at vertices). Maximal: points on high-dimensional faces (no point at a vertex; e,fe, fe,f inside the triangle). Both pictures show the same rank-3 matroid: the four-point line abcdabcdabcd and two points e,fe, fe,f off that line.
[Transversal matroids and geometry] Brylawski: MMM is transversal if and only if MMM is isomorphic to a free-simplicial set (points placed freely on faces of a simplex). Why is this rank-2 matroid, with parallel pairs {a,b}\{a, b\}{a,b} , {c,d}\{c, d\}{c,d} , {e,f}\{e, f\}{e,f} , not free-simplicial?
Each parallel pair must sit at a vertex of the simplex, the three pairs at three different vertices, so a,c,ea, c, ea,c,e would have rank 3, not 2. A parallel pair is a 2-element circuit, and those lie at a vertex.So this matroid is not transversal.
[Deletion, contraction and duality] Is the dual of a matroid in each of these classes again in the class: graphic, representable, transversal?
Graphic Not always: M(G)∗M(G)^*M(G)∗ is graphic if and only if GGG is planar. Example: M(K5)∗M(K_5)^*M(K5)∗ is not graphic. Representable Always: the dual of a representable matroid is representable. Example: U2,4∗=U2,4U_{2,4}^* = U_{2,4}U2,4∗=U2,4 , representable over R\mathbb{R}R . Transversal Not always: some transversal matroid has a non-transversal dual. Example: either the rank-3 matroid with double points ab,cd,efab, cd, efab,cd,ef at the corners of a triangle and ggg inside, or the d…
[Deletion, contraction and duality] Proposition 7.14 Suppose MMM is transversal and eee is not an isthmus. Then … ?
M−eM - eM−e is also transversal. Delete the vertex eee from a presentation: the matchable subsets of X−eX - eX−e are exactly the independent sets of M−eM - eM−e .Example: deleting eee from the matroid with four-point line abcdabcdabcd and e,fe, fe,f off it leaves a transversal matroid: the four-point line abcdabcdabcd plus the point fff .
[Deletion, contraction and duality] This rank-3 matroid MMM has double points ababab , cdcdcd , efefef at the corners of a triangle and ggg inside. Why is MMM transversal?
MMM is free-simplicial (points placed freely on the faces of a triangle). A presentation: a,ba, ba,b joined to y1y_1y1 ; c,dc, dc,d to y2y_2y2 ; e,fe, fe,f to y3y_3y3 ; ggg to y1,y2,y3y_1, y_2, y_3y1,y2,y3 .
[Deletion, contraction and duality] MMM is the rank-3 matroid with double points {a,b}\{a, b\}{a,b} , {c,d}\{c, d\}{c,d} , {e,f}\{e, f\}{e,f} at the three corners of a triangle and a point ggg inside the triangle.What is the contraction M/gM/gM/g ?
The rank-2 matroid with parallel pairs {a,b}\{a, b\}{a,b} , {c,d}\{c, d\}{c,d} , {e,f}\{e, f\}{e,f} , which is not transversal. Contracting ggg makes points on a common line through ggg parallel. The lines through ggg are gabgabgab , gcdgcdgcd , gefgefgef .
[Deletion, contraction and duality] MMM is the rank-3 matroid with double points {a,b}\{a, b\}{a,b} , {c,d}\{c, d\}{c,d} , {e,f}\{e, f\}{e,f} at the three corners of a triangle and a point ggg inside the triangle. M/gM/gM/g (three parallel pairs in rank 2) is not transversal. Deleting a non-isthmus from a transversal matroid gives a transversal matroid. (M∗−g)∗=M/g(M^* - g)^* = M/g(M∗−g)∗=M/g .How does this show that some transversal matroid has a non-transversal dual?
If M∗M^*M∗ were transversal, so would be M∗−gM^* - gM∗−g , whose dual M/gM/gM/g is not. So either MMM or M∗−gM^* - gM∗−g is transversal with a non-transversal dual. ggg is not an isthmus of M∗M^*M∗ , because ggg is not a loop of MMM . In fact the second alternative holds: M∗M^*M∗ and M∗−gM^* - gM∗−g are both transversal.
[Deletion, contraction and duality] Is the class of transversal matroids closed under contraction?
No. Example: this matroid MMM (double points ab,cd,efab, cd, efab,cd,ef at the corners of a triangle, ggg inside) is transversal, but M/gM/gM/g (three parallel pairs in rank 2) is not.
[Deletion, contraction and duality] Which classical number-theory proof has the same logical form as " MMM or M∗−gM^* - gM∗−g is a transversal matroid with non-transversal dual, without telling which"?
There are irrational a,ba, ba,b with aba^bab rational: if 22\sqrt{2}^{\sqrt{2}}22 is rational take a=b=2a = b = \sqrt{2}a=b=2 ; otherwise take a=22a = \sqrt{2}^{\sqrt{2}}a=22 , b=2b = \sqrt{2}b=2 . (22)2=22=2\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{2} = 2(22)2=22=2 . The argument does not say which case holds.
[Deletion, contraction and duality] Is the class of transversal matroids closed under deletion, contraction, duality?
Deletion Closed. Example: delete a vertex xxx from a presentation to present M−xM - xM−x . Contraction Not closed. Example: double points ab,cd,efab, cd, efab,cd,ef at the corners of a triangle and ggg inside is transversal; contracting ggg gives three parallel pairs in rank 2, not transversal. Duality Not closed. Example: for the same matroid MMM , the matroid M∗−gM^* - gM∗−g is transversal but its dual M/gM/gM/g is not.
[Deletion, contraction and duality] Why is a class of matroids that is closed under deletion and duality also closed under contraction?
M/e=(M∗−e)∗\boldsymbol{M/e = (M^* - e)^*}M/e=(M∗−e)∗ Dualize, delete, dualize again: each step stays in the class.Example: representable matroids are closed under deletion and duality, so also under contraction. Transversal matroids are closed under deletion but not contraction, so they cannot be closed under duality.
[Representations of transversal matroids] Why is every transversal matroid representable over R\mathbb{R}R ?
Its free-simplicial picture in Rn\mathbb{R}^nRn has no accidental dependences, so the coordinates of the points (ordered nnn -tuples) give an affine representation. A free-simplicial picture: the points placed freely on the faces of a simplex, which exists by Brylawski's theorem.Example: the four-point line abcdabcdabcd with e,fe, fe,f off it: a=(0,0)a = (0, 0)a=(0,0) , b=(1,0)b = (1, 0)b=(1,0) , c=(2,0)c = (2, 0)c=(2,0) , d=(3,0)d = (3, 0)d=(3,0) , e=(0,1)e = (0, 1)e=(0,1) , f=(1,1)f = (1, 1)f…
[Representations of transversal matroids] Why is every transversal matroid representable over Q\mathbb{Q}Q ?
Put the vertices of the simplex at rational points of Rn\mathbb{R}^nRn and choose rational coordinates for all the other points of the free-simplicial picture. The points only need to avoid accidental dependences, and rational points can be chosen to do so.Example: a triangle with vertices (0,0)(0, 0)(0,0) , (1,0)(1, 0)(1,0) , (0,1)(0, 1)(0,1) and a point inside at (13,13)(\tfrac{1}{3}, \tfrac{1}{3})(31,31) .
[Representations of transversal matroids] Theorem 7.16 Let MMM be a transversal matroid. Then there is some positive integer NNN such that if ∣F∣>N|\mathbb{F}| > N∣F∣>N , then … ?
MMM is representable over the field F\mathbb{F}F . So transversal matroids are representable over fields of every characteristic.Example: U2,4U_{2,4}U2,4 (four points on a line, transversal: all four joined to y1,y2y_1, y_2y1,y2 ) is representable over GF(3)GF(3)GF(3) but not over GF(2)GF(2)GF(2) : the field must be large enough.
[Representations of transversal matroids] Theorem: for a transversal matroid MMM there is an NNN such that MMM is representable over every field F\mathbb{F}F with ∣F∣>N|\mathbb{F}| > N∣F∣>N .What is the idea of the proof?
Replace the indeterminates x1,…,xkx_1, \dots, x_kx1,…,xk in the incidence matrix of a presentation by elements ei∈Fe_i \in \mathbb{F}ei∈F that keep the needed subdeterminants nonzero. With the indeterminates, the matrix represents MMM over F(x1,…,xk)\mathbb{F}(x_1, \dots, x_k)F(x1,…,xk) . The indeterminates only ensure that certain sets of columns are linearly independent, i.e. that finitely many subdeterminants are nonzero. A large enough field has values eie_iei that keep all of them no…
[Hyperplane arrangements and matroids] What is a hyperplane in Rd\mathbb{R}^dRd ?
The solution set of one linear equation a1x1+a2x2+⋯+adxd=ba_1x_1 + a_2x_2 + \dots + a_dx_d = ba1x1+a2x2+⋯+adxd=b (with a1,…,ada_1, \dots, a_da1,…,ad not all 0), a (d−1)(d-1)(d−1) -dimensional flat of Rd\mathbb{R}^dRd . The vector (a1,…,ad)(a_1, \dots, a_d)(a1,…,ad) is a normal vector of the hyperplane.Example: in R2\mathbb{R}^2R2 the hyperplanes are the lines; x−y=2x - y = 2x−y=2 has normal vector (1,−1)(1, -1)(1,−1) .
[Hyperplane arrangements and matroids] When is an arrangement A\mathcal{A}A of hyperplanes in Rd\mathbb{R}^dRd central?
When the intersection of all its hyperplanes is non-empty: ⋂H∈AH≠∅\bigcap_{H \in \mathcal{A}} H \neq \emptyset⋂H∈AH=∅ . Example: the planes x=0x = 0x=0 , y=0y = 0y=0 , z=0z = 0z=0 in R3\mathbb{R}^3R3 are central (all contain the origin); the lines x=0x = 0x=0 , y=0y = 0y=0 , x+y=1x + y = 1x+y=1 in R2\mathbb{R}^2R2 are not.
[Hyperplane arrangements and matroids] When is a central arrangement A\mathcal{A}A of hyperplanes in Rd\mathbb{R}^dRd essential?
When the intersection of all its hyperplanes is a single point: ⋂H∈AH={P}\bigcap_{H \in \mathcal{A}} H = \{P\}⋂H∈AH={P} . Example: x=0x = 0x=0 , y=0y = 0y=0 , z=0z = 0z=0 in R3\mathbb{R}^3R3 is essential (intersection: the origin).
[Hyperplane arrangements and matroids] The three planes x=yx = yx=y , x=zx = zx=z and y=zy = zy=z in R3\mathbb{R}^3R3 : central? essential?
Central, but not essential. All three planes contain the whole line x=y=zx = y = zx=y=z , so the intersection is a line, not a point.
[Hyperplane arrangements and matroids] Proposition 7.18 A central arrangement A\mathcal{A}A of hyperplanes in Rd\mathbb{R}^dRd is essential if and only if … ?
The normal vectors of its hyperplanes span Rd\mathbb{R}^dRd . Example: x=yx = yx=y , x=zx = zx=z , y=zy = zy=z have normals (1,−1,0),(1,0,−1),(0,1,−1)(1, -1, 0), (1, 0, -1), (0, 1, -1)(1,−1,0),(1,0,−1),(0,1,−1) , which span only a plane: (1,−1,0)−(1,0,−1)=−(0,1,−1)(1, -1, 0) - (1, 0, -1) = -(0, 1, -1)(1,−1,0)−(1,0,−1)=−(0,1,−1) . The arrangement is not essential.
[Hyperplane arrangements and matroids] Theorem 7.19 Let A\mathcal{A}A be a central arrangement of hyperplanes in Rd\mathbb{R}^dRd . The matroid M(A)M(\mathcal{A})M(A) on the ground set A\mathcal{A}A : which sets III of kkk hyperplanes are independent?
Those with dim⁡(⋂H∈IH)=d−k\dim\left(\bigcap_{H \in I} H\right) = d - kdim(⋂H∈IH)=d−k . Each hyperplane in III lowers the dimension of the intersection by exactly 1.Example: in R3\mathbb{R}^3R3 , the planes x=0x = 0x=0 , y=0y = 0y=0 meet in a line (dimension 1=3−21 = 3 - 21=3−2 ), so they are independent; x=0x = 0x=0 , y=0y = 0y=0 , x−y=0x - y = 0x−y=0 meet in the same line (dimension 1≠3−31 \neq 3 - 31=3−3 ), so they are dependent.
[Hyperplane arrangements and matroids] For a central arrangement A\mathcal{A}A in Rd\mathbb{R}^dRd , a set III of kkk hyperplanes is called independent when dim⁡(⋂H∈IH)=d−k\dim\left(\bigcap_{H \in I} H\right) = d - kdim(⋂H∈IH)=d−k .Why are these the independent sets of a matroid? Key idea of the proof.
III is independent exactly when the kkk normal vectors of its hyperplanes are linearly independent, and linearly independent sets of vectors form a matroid. With the normals as the rows of a k×dk \times dk×d matrix BBB : ⋂H∈IH\bigcap_{H \in I} H⋂H∈IH is the null space N(B)N(B)N(B) , and rank–nullity gives dim⁡N(B)=d−r(B)\dim N(B) = d - r(B)dimN(B)=d−r(B) . So dim⁡N(B)=d−k\dim N(B) = d - kdimN(B)=d−k if and only if r(B)=kr(B) = kr(B)=k .
[Hyperplane arrangements and matroids] To show that a set of hyperplanes of a central arrangement is independent exactly when its normal vectors are, the proof first assumes that all hyperplanes contain the origin.Why is that no restriction?
Translating all hyperplanes by the same vector moves their common point to the origin and keeps the dimension of every intersection. Example: x=1x = 1x=1 and y=2y = 2y=2 meet in the line {(1,2,z)}\{(1, 2, z)\}{(1,2,z)} ; translated by (−1,−2,0)(-1, -2, 0)(−1,−2,0) they become x=0x = 0x=0 and y=0y = 0y=0 , meeting in the zzz -axis, also a line.
[Hyperplane arrangements and matroids] Proposition 7.20 Let AAA be a set of hyperplanes of a central arrangement in Rd\mathbb{R}^dRd . The matroid rank r(A)= ?r(A) = \; ?r(A)=?
r(A)=codim⁡(⋂H∈AH)=d−dim⁡(⋂H∈AH)\boldsymbol{r(A) = \operatorname{codim}\left(\bigcap_{H \in A} H\right) = d - \dim\left(\bigcap_{H \in A} H\right)}r(A)=codim(⋂H∈AH)=d−dim(⋂H∈AH) Example: in R3\mathbb{R}^3R3 , x=0x = 0x=0 , y=0y = 0y=0 , x−y=0x - y = 0x−y=0 meet in the zzz -axis, so their rank is 3−1=23 - 1 = 23−1=2 .
[Hyperplane arrangements and matroids] In the matroid M(A)M(\mathcal{A})M(A) of a central arrangement A\mathcal{A}A , the word "hyperplane" has two meanings. Which two?
A (d−1)(d-1)(d−1) -dimensional subspace of Rd\mathbb{R}^dRd (an element of A\mathcal{A}A ), and a matroid hyperplane (a maximal proper flat of M(A)M(\mathcal{A})M(A) ). For a central, essential arrangement in Rd\mathbb{R}^dRd , the matroid hyperplanes correspond to the lines in Rd\mathbb{R}^dRd that are intersections of hyperplanes of A\mathcal{A}A .Example: for x=0x = 0x=0 , y=0y = 0y=0 , z=0z = 0z=0 in R3\mathbb{R}^3R3 , the matroid hyperplanes {x=0,y=0}\{x = 0, y = 0\}{x=0,y=0} , {x=0,z=0}\{…
[Hyperplane arrangements and matroids] The central arrangement A\mathcal{A}A in R3\mathbb{R}^3R3 consists of the planes a:x=0a: x = 0a:x=0 , b:y=0b: y = 0b:y=0 , c:z=0c: z = 0c:z=0 , d:x−y=0d: x - y = 0d:x−y=0 . Draw the matroid M(A)M(\mathcal{A})M(A) .
Rank 3: a,b,da, b, da,b,d on one line, and ccc off that line (an isthmus). The normals (1,0,0),(0,1,0),(1,−1,0)(1, 0, 0), (0, 1, 0), (1, -1, 0)(1,0,0),(0,1,0),(1,−1,0) of a,b,da, b, da,b,d lie in the xyxyxy -plane, so {a,b,d}\{a, b, d\}{a,b,d} has rank 2. The normal vectors.
[Hyperplane arrangements and matroids] The central arrangement A\mathcal{A}A in R3\mathbb{R}^3R3 consists of the planes a:x=0a: x = 0a:x=0 , b:y=0b: y = 0b:y=0 , c:z=0c: z = 0c:z=0 , d:x−y=0d: x - y = 0d:x−y=0 . Why is ccc an isthmus of M(A)M(\mathcal{A})M(A) ?
The normal (0,0,1)(0, 0, 1)(0,0,1) of ccc is orthogonal to the plane spanned by the other three normals, so ccc lies in no circuit, i.e. every basis contains ccc . The other normals (1,0,0),(0,1,0),(1,−1,0)(1, 0, 0), (0, 1, 0), (1, -1, 0)(1,0,0),(0,1,0),(1,−1,0) span only the xyxyxy -plane, rank 2; ccc raises the rank to 3.
[Hyperplane arrangements and matroids] Why is the matroid M(A)M(\mathcal{A})M(A) of a central hyperplane arrangement always simple?
A loop would need the normal vector (0,…,0)(0, \dots, 0)(0,…,0) , and two parallel elements would need parallel normals, i.e. two identical hyperplanes. Neither occurs: a hyperplane has a nonzero normal, and the hyperplanes of A\mathcal{A}A are distinct.Example: x=0x = 0x=0 and 2x=02x = 02x=0 have parallel normals (1,0,0),(2,0,0)(1, 0, 0), (2, 0, 0)(1,0,0),(2,0,0) , and are the same plane.
[Hyperplane arrangements and matroids] What do the flats of M(A)M(\mathcal{A})M(A) correspond to, for a central arrangement A\mathcal{A}A , and how is the lattice of flats ordered?
To the intersections of hyperplanes of A\mathcal{A}A ; the lattice of flats is the poset of these intersections ordered by reverse inclusion. The flat for an intersection WWW is the set of all hyperplanes of A\mathcal{A}A that contain WWW . Smaller intersections give larger flats.
[Hyperplane arrangements and matroids] The central arrangement A\mathcal{A}A in R3\mathbb{R}^3R3 consists of the planes a:x=0a: x = 0a:x=0 , b:y=0b: y = 0b:y=0 , c:z=0c: z = 0c:z=0 , d:x−y=0d: x - y = 0d:x−y=0 . What is the lattice of flats of M(A)M(\mathcal{A})M(A) ?
Bottom R3\mathbb{R}^3R3 ; atoms a,b,c,da, b, c, da,b,c,d ; rank 2: abd,ac,bc,cdabd, ac, bc, cdabd,ac,bc,cd ; top: the origin 000 . abdabdabd means a∩b∩da \cap b \cap da∩b∩d (the zzz -axis), acacac is the yyy -axis, bcbcbc the xxx -axis, cdcdcd the line x=yx = yx=y in the xyxyxy -plane.
[Hyperplane arrangements and matroids] What changes when a central arrangement of hyperplanes in Rd\mathbb{R}^dRd is not essential?
It still gives a matroid, but of rank less than ddd . The intersection of all hyperplanes is then a line, a plane or a larger subspace, of dimension at least 1.Example: x=yx = yx=y , x=zx = zx=z , y=zy = zy=z in R3\mathbb{R}^3R3 meet in a line, so the matroid has rank 3−1=23 - 1 = 23−1=2 (it is U2,3U_{2,3}U2,3 ).
[Hyperplane arrangements and matroids] Which matroids are the matroids M(A)M(\mathcal{A})M(A) of central hyperplane arrangements A\mathcal{A}A in real spaces Rd\mathbb{R}^dRd ?
Exactly the (simple) matroids representable over R\mathbb{R}R . The hyperplane arrangement with normals v1,…,vnv_1, \dots, v_nv1,…,vn gives the matroid of the vectors v1,…,vnv_1, \dots, v_nv1,…,vn , and every set of distinct nonzero, pairwise non-parallel vectors arises this way.
[Hyperplane arrangements and matroids] Hyperplane arrangements give only real-representable matroids. Which reasons does the book give for studying them anyway?
Oriented matroids Arrangements are important in the theory of oriented matroids, which is closely related to topology. Topology of the complement Rd−⋃H∈AH\mathbb{R}^d - \bigcup_{H \in \mathcal{A}} HRd−⋃H∈AH is an open set studied by topologists.Example: the Orlik–Solomon algebra is an invariant of an arrangement. Enumeration Example: into how many pieces can nnn straight cuts divide a cube of cheese? Groups For several groups, the geometric dual of a Cayley graph is given by the open regions o…
[Hyperplane arrangements and matroids] How many planes of symmetry does a cube in R3\mathbb{R}^3R3 with vertices (±1,±1,±1)(\pm 1, \pm 1, \pm 1)(±1,±1,±1) have, and what are their equations?
Nine: x=0, y=0, z=0, x±y=0, x±z=0, y±z=0\boldsymbol{x = 0, \ y = 0, \ z = 0, \ x \pm y = 0, \ x \pm z = 0, \ y \pm z = 0}x=0, y=0, z=0, x±y=0, x±z=0, y±z=0 Three planes parallel to faces, and six through pairs of opposite edges. All contain the origin, so they form a central arrangement.
[Hyperplane arrangements and matroids] The nine planes of symmetry of a cube have normals a=(1,0,0), b=(0,1,0), c=(0,0,1),a = (1,0,0), \ b = (0,1,0), \ c = (0,0,1),a=(1,0,0), b=(0,1,0), c=(0,0,1), d=(1,1,0), e=(1,0,1), f=(0,1,1),d = (1,1,0), \ e = (1,0,1), \ f = (0,1,1),d=(1,1,0), e=(1,0,1), f=(0,1,1), g=(1,−1,0), h=(1,0,−1), i=(0,1,−1)g = (1,-1,0), \ h = (1,0,-1), \ i = (0,1,-1)g=(1,−1,0), h=(1,0,−1), i=(0,1,−1) . Which six of them represent M(K4)M(K_4)M(K4) , and how are the other three plac…
d,e,f,g,h,id, e, f, g, h, id,e,f,g,h,i give M(K4)M(K_4)M(K4) ; then a=eh‾∩dg‾a = \overline{eh} \cap \overline{dg}a=eh∩dg , b=fi‾∩dg‾\ b = \overline{fi} \cap \overline{dg} b=fi∩dg , c=eh‾∩fi‾\ c = \overline{eh} \cap \overline{fi} c=eh∩fi . Left: M(K4)M(K_4)M(K4) ; right: the whole matroid. The 3-point lines of M(K4)M(K_4)M(K4) : d=e+id = e + id=e+i , d=f+h\ d = f + h d=f+h , e=f+g\ e = f + g e=f+g , h=g+i\ h = g + i h=g+i .Example: aaa lies on both lines since e+h=(2,0,0)=d+ge + h = (2, 0…
[Hyperplane arrangements and matroids] In the matroid of the nine normals of the planes of symmetry of a cube a=(1,0,0), b=(0,1,0), c=(0,0,1),a = (1,0,0), \ b = (0,1,0), \ c = (0,0,1),a=(1,0,0), b=(0,1,0), c=(0,0,1), d=(1,1,0), e=(1,0,1), f=(0,1,1),d = (1,1,0), \ e = (1,0,1), \ f = (0,1,1),d=(1,1,0), e=(1,0,1), f=(0,1,1), g=(1,−1,0), h=(1,0,−1), i=(0,1,−1)g = (1,-1,0), \ h = (1,0,-1), \ i = (0,1,-1)g=(1,−1,0), h=(1,0,−1), i=(0,1,−1) , which lines have four points?
{a,b,d,g}, {a,c,e,h}, {b,c,f,i}\boldsymbol{\{a, b, d, g\}, \ \{a, c, e, h\}, \ \{b, c, f, i\}}{a,b,d,g}, {a,c,e,h}, {b,c,f,i} They are the normals with third, second and first coordinate 0: each set spans a coordinate plane, so it has rank 2.
[Hyperplane arrangements and matroids] For the set SSS of the nine normals of the planes of symmetry of a cube, the 18 vectors ±S\pm S±S form the root system B3.
S={(1,0,0),(0,1,0),(0,0,1),(1,±1,0),(1,0,±1),(0,1,±1)}S = \{(1,0,0), (0,1,0), (0,0,1), (1,\pm 1,0), (1,0,\pm 1), (0,1,\pm 1)\}S={(1,0,0),(0,1,0),(0,0,1),(1,±1,0),(1,0,±1),(0,1,±1)} . Root systems are vector configurations with strong symmetry, used in algebraic classification problems.
[Hyperplane arrangements and matroids] How is the spherical arrangement of a central arrangement A\mathcal{A}A in Rd\mathbb{R}^dRd obtained?
Move all hyperplanes to contain the origin, intersect each with the unit sphere Sd−1S^{d-1}Sd−1 , and keep only these intersections (spheres of dimension d−2d - 2d−2 ). Sd−1={v∈Rd:∥v∥=1}S^{d-1} = \{v \in \mathbb{R}^d : \|v\| = 1\}Sd−1={v∈Rd:∥v∥=1} . In R3\mathbb{R}^3R3 the result is a set of great circles on the ordinary sphere. It defines the same matroid. Example: the planes x=0x = 0x=0 , y=0y = 0y=0 , z=0z = 0z=0 , x−y=0x - y = 0x−y=0 give four great circles.
[Hyperplane arrangements and matroids] How is the projective arrangement obtained from a spherical arrangement, and why does it keep all matroid information?
Cut the sphere into two hemispheres by a hyperplane not in A\mathcal{A}A (the hyperplane at infinity), keep one hemisphere, and identify antipodal points on its boundary. The pattern of intersections on the two hemispheres is the same, so one hemisphere determines the matroid. This is analogous to building the projective space PG(n,q)PG(n, q)PG(n,q) from AG(n+1,q)AG(n + 1, q)AG(n+1,q) . The hyperplane at infinity is the dotted bounding circle.
[Hyperplane arrangements and matroids] What is the affine arrangement obtained from a projective arrangement in a hemisphere of Sd−1S^{d-1}Sd−1 ?
The non-central arrangement in Rd−1\mathbb{R}^{d-1}Rd−1 obtained by flattening the hemisphere. Example: from the planes a:x=0a: x = 0a:x=0 , b:y=0b: y = 0b:y=0 , c:z=0c: z = 0c:z=0 , d:x−y=0d: x - y = 0d:x−y=0 in R3\mathbb{R}^3R3 we get four lines in R2\mathbb{R}^2R2 ; a,b,da, b, da,b,d meet in one point.
[Hyperplane arrangements and matroids] A central arrangement in Rd\mathbb{R}^dRd gives a spherical, a projective and an affine arrangement. Where does each lie, and what do the four have in common?
Central in Rd\mathbb{R}^dRd →\to→ spherical in Sd−1S^{d-1}Sd−1 →\to→ projective in PG(d−1,R)PG(d-1, \mathbb{R})PG(d−1,R) →\to→ affine in Rd−1\mathbb{R}^{d-1}Rd−1 ; all four define the same matroid. (i) central, (ii) spherical, (iii) projective, (iv) affine, for the planes a:x=0a: x = 0a:x=0 , b:y=0b: y = 0b:y=0 , c:z=0c: z = 0c:z=0 , d:x−y=0d: x - y = 0d:x−y=0 .
[Hyperplane arrangements and matroids] Which matroid does this affine arrangement of four lines in R2\mathbb{R}^2R2 define?
Rank 3, with {a,b,d}\{a, b, d\}{a,b,d} a 3-point line and ccc an isthmus. Three lines through one point form a dependent set of rank 2; ccc does not pass through that point, so ccc together with any two of a,b,da, b, da,b,d is independent.
[Hyperplane arrangements and matroids] When does a collection A\mathcal{A}A of hyperplanes in Rd\mathbb{R}^dRd have parallel intersections?
When some subset of A\mathcal{A}A intersects in a subspace WWW with dim⁡W≥1\dim W \ge 1dimW≥1 that is parallel to some H∈AH \in \mathcal{A}H∈A , i.e. W∩H=∅W \cap H = \emptysetW∩H=∅ . Example: in R2\mathbb{R}^2R2 , the lines y=0y = 0y=0 and y=1y = 1y=1 (take WWW = the line y=0y = 0y=0 ).Example: in R3\mathbb{R}^3R3 , the planes x=0x = 0x=0 , y=0y = 0y=0 meet in the zzz -axis, which is parallel to the plane x+y=1x + y = 1x+y=1 .
[Hyperplane arrangements and matroids] Proposition 7.24 (1) If A\mathcal{A}A is a central arrangement in Rd\mathbb{R}^dRd , what holds for its affine arrangement A′\mathcal{A}'A′ in Rd−1\mathbb{R}^{d-1}Rd−1 ? (2) Which non-central arrangements A′\mathcal{A}'A′ in Rd−1\mathbb{R}^{d-1}Rd−1 arise as the affine arrangement of a central arrangement in Rd\mathbb{R}^dRd ?
(1) A′\mathcal{A}'A′ has no parallel intersections. (2) Exactly those with no parallel intersections. So a non-central arrangement without parallel intersections defines a matroid: the matroid of the central arrangement it lifts to.
[Hyperplane arrangements and matroids] When does a family of lines in the plane define a matroid (via lifting to a central arrangement in R3\mathbb{R}^3R3 )?
When every two of the lines intersect (no two lines are parallel). In R2\mathbb{R}^2R2 the only parallel intersections are a line parallel to another line.Example: three lines through one point give U2,3U_{2,3}U2,3 ; three lines forming a triangle give U3,3U_{3,3}U3,3 .
[Hyperplane arrangements and matroids] What is the form of the equation of a projective hyperplane, and of an affine hyperplane?
Projective: a1x1+⋯+adxd=0a_1x_1 + \dots + a_dx_d = 0a1x1+⋯+adxd=0 ; affine: a1x1+⋯+adxd=ba_1x_1 + \dots + a_dx_d = ba1x1+⋯+adxd=b . This matches the hyperplanes of PG(n,q)PG(n, q)PG(n,q) and AG(n,q)AG(n, q)AG(n,q) .Example: x+y−z=0x + y - z = 0x+y−z=0 is projective; x+y=3x + y = 3x+y=3 is affine.
[Cutting cheese: counting regions] What is the largest number of regions that nnn lines divide the plane into?
n2+n+22\boldsymbol{\dfrac{n^2 + n + 2}{2}}2n2+n+2 Example: 3 lines give at most 9+3+22=7\frac{9 + 3 + 2}{2} = 729+3+2=7 regions; 4 lines give at most 11.
[Cutting cheese: counting regions] Into how many pieces can nnn plane cuts divide a cheese (Woodbridge, American Mathematical Monthly, 1943)?
At most (n+1)(n2−n+6)6\boldsymbol{\dfrac{(n + 1)(n^2 - n + 6)}{6}}6(n+1)(n2−n+6) pieces. Example: n=3n = 3n=3 : 4⋅126=8\frac{4 \cdot 12}{6} = 864⋅12=8 ; n=4\ n = 4 n=4 : 5⋅186=15\frac{5 \cdot 18}{6} = 1565⋅18=15 .
[Cutting cheese: counting regions] Schläfli's formula. What is the largest number of regions that nnn hyperplanes divide Rd\mathbb{R}^dRd into?
∑k=0d(nk)\boldsymbol{\displaystyle\sum_{k=0}^{d} \binom{n}{k}}k=0∑d(kn) Published posthumously in 1901 (Ludwig Schläfli); sometimes attributed to R. C. Buck (1943).Example: n=4n = 4n=4 planes in R3\mathbb{R}^3R3 : 1+4+6+4=151 + 4 + 6 + 4 = 151+4+6+4=15 .
[Cutting cheese: counting regions] When are nnn lines in the plane in general position, and when are nnn hyperplanes in Rd\mathbb{R}^dRd ?
Lines: no two parallel and no three through one point. Hyperplanes: no parallel intersections, and any d+1d + 1d+1 of them have empty intersection. Example: five lines in general position.
[Cutting cheese: counting regions] These five lines are in general position (no two parallel, no three through one point). Which matroid do they define?
The uniform matroid U3,5U_{3,5}U3,5 . Lift to five distinct planes through the origin in R3\mathbb{R}^3R3 . No three lines meet in a point, so any three normals are linearly independent; any four vectors in R3\mathbb{R}^3R3 are dependent, so r=3r = 3r=3 .
[Cutting cheese: counting regions] A\mathcal{A}A is an affine arrangement and Hx∈AH_x \in \mathcal{A}Hx∈A corresponds to the element xxx of M(A)M(\mathcal{A})M(A) . Which arrangement A′\mathcal{A}'A′ has M(A′)=M(A)−xM(\mathcal{A}') = M(\mathcal{A}) - xM(A′)=M(A)−x ?
A′=A−Hx\boldsymbol{\mathcal{A}' = \mathcal{A} - H_x}A′=A−Hx : erase the hyperplane HxH_xHx . Erasing HxH_xHx lowers the rank only when xxx is an isthmus of M(A)M(\mathcal{A})M(A) .Example: lines a,b,da, b, da,b,d through one point and a line ccc not through it give rank 3 with ccc an isthmus; erasing ccc leaves three lines through one point, rank 2.
[Cutting cheese: counting regions] A\mathcal{A}A is an affine arrangement in Rd\mathbb{R}^dRd and Hx∈AH_x \in \mathcal{A}Hx∈A corresponds to the element xxx of M(A)M(\mathcal{A})M(A) . Which arrangement A′′\mathcal{A}''A′′ has M(A′′)=M(A)/xM(\mathcal{A}'') = M(\mathcal{A})/xM(A′′)=M(A)/x ?
A′′={H∩Hx:H∈A−Hx}\boldsymbol{\mathcal{A}'' = \{H \cap H_x : H \in \mathcal{A} - H_x\}}A′′={H∩Hx:H∈A−Hx} , an arrangement inside the (d−1)(d-1)(d−1) -dimensional space HxH_xHx . Each H∩HxH \cap H_xH∩Hx is a (d−2)(d-2)(d−2) -dimensional flat, so a hyperplane of HxH_xHx . The rank drops by one, as r(M/x)=r(M)−1r(M/x) = r(M) - 1r(M/x)=r(M)−1 .Example: contracting a line aaa in the plane leaves the points where the other lines cross aaa .
[Cutting cheese: counting regions] Proposition 7.26 Let A\mathcal{A}A be an affine arrangement of hyperplanes in Rd\mathbb{R}^dRd , Hx∈AH_x \in \mathcal{A}Hx∈A , A′=A−Hx\mathcal{A}' = \mathcal{A} - H_xA′=A−Hx and A′′={H∩Hx:H∈A−Hx}\mathcal{A}'' = \{H \cap H_x : H \in \mathcal{A} - H_x\}A′′={H∩Hx:H∈A−Hx} . Then M(A′)= ?M(\mathcal{A}') = \; ?M(A′)=? and M(A′′)= ?M(\mathcal{A}'') = \; ?M(A′′)=?
M(A′)=M(A)−x\boldsymbol{M(\mathcal{A}') = M(\mathcal{A}) - x}M(A′)=M(A)−x and M(A′′)=M(A)/x\boldsymbol{M(\mathcal{A}'') = M(\mathcal{A})/x}M(A′′)=M(A)/x Deletion: erase HxH_xHx . Contraction: restrict the arrangement to HxH_xHx .