Ch.1: A tour of matroids

Chapter 1 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 1.1. Motivation 1.2. Introduction to matroids 1.3. Geometries 1.4. Graphs and matroids 1.5. Bipartite graphs, transversal matroids

84 flashcards · Mathematics · by lakesare

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

1. [Motivation] What do these four objects (a graph, a point–line geometry, a bipartite graph, vectors in 3-space) have in common?

   They all represent the same matroid, i.e. the same dependence structure on {a,b,c,d,e}\{a, b, c, d, e\}{a,b,c,d,e} . They are also the same matroid as the column dependences of [000110110011010]\begin{bmatrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \end{bmatrix}⎣⎡​001​011​010​101​100​⎦⎤​ (columns a,…,ea, \dots, ea,…,e ).Matroid theory uses linear and abstract algebra, graph theory, combinatorics and finite geometry.

2. [Motivation] Who invented matroid theory, and what did he want to understand?

   Hassler Whitney, in the 1930s: how much of linear algebra does not depend on coordinates (on the field of coefficients). He noticed that the linearly independent subsets of a vector space satisfy the independent set axioms, and first stated the definition of a matroid.

3. [Motivation] Whose approach to matroids does the book follow, and what was his name for a matroid?

   Gian-Carlo Rota's geometric approach; he said "combinatorial pregeometry" instead of "matroid". Rota disliked the word "matroid"; his term did not catch on.

4. [Introduction to matroids] The columns of A=[10110112]A = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 2 \end{bmatrix}A=[10​01​11​12​] are a=(1,0)a = (1, 0)a=(1,0) , b=(0,1)b = (0, 1)b=(0,1) , c=(1,1)c = (1, 1)c=(1,1) , d=(1,2)d = (1, 2)d=(1,2) . Which subsets of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} are linearly dependent?

   Exactly the subsets with 3 or 4 elements: abc,abd,acd,bcd,abcdabc, abd, acd, bcd, abcdabc,abd,acd,bcd,abcd . Every two of the vectors are linearly independent, and more than 2 vectors in R2\mathbb{R}^2R2 are always dependent.

5. [Introduction to matroids] What are the steps of the rank 2 matroid drawing procedure for a matrix with 2 rows?

   Step 1 Draw the column vectors in the plane. Step 2 Draw a free line (parallel to none of the vectors), and scale each vector (by a negative number if needed) until it ends on that line. Step 3 Keep the line with the points on it and discard the vectors. Example: for a=(1,0)a = (1, 0)a=(1,0) , b=(0,1)b = (0, 1)b=(0,1) , c=(1,1)c = (1, 1)c=(1,1) , d=(1,2)d = (1, 2)d=(1,2) the result is four points on one line.

6. [Introduction to matroids] In the matroid drawing procedure, why does the picture stay the same when a column vector vvv is replaced by λv\lambda vλv for some λ≠0\lambda \neq 0λ=0 ?

   Multiplying a vector by a nonzero scalar does not change which subsets are linearly dependent, and vvv and λv\lambda vλv meet the free line in the same point. Example: replacing (1,1)(1, 1)(1,1) by (2,2)(2, 2)(2,2) , or (1,2)(1, 2)(1,2) by (−1,−2)(-1, -2)(−1,−2) , gives the same picture.

7. [Introduction to matroids] What are the steps of the rank 3 matroid drawing procedure for a matrix with 3 rows?

   Project the column vectors onto a free plane PPP (a plane parallel to none of the vectors). Draw the vectors in R3\mathbb{R}^3R3 and scale each vector (or its negative) until it ends on PPP . The points on PPP are the picture. Example: the plane x+y+z=1x + y + z = 1x+y+z=1 is free for (0,0,1),(0,1,1),(0,1,0),(1,0,1),(1,0,0)(0,0,1), (0,1,1), (0,1,0), (1,0,1), (1,0,0)(0,0,1),(0,1,1),(0,1,0),(1,0,1),(1,0,0) .

8. [Introduction to matroids] Draw the matroid on the columns a,b,c,d,ea, b, c, d, ea,b,c,d,e of B=[000110110011010]B = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \end{bmatrix}B=⎣⎡​001​011​010​101​100​⎦⎤​

   Two three-point lines abcabcabc and adeadeade that meet in the point aaa . b=a+cb = a + cb=a+c and d=a+ed = a + ed=a+e ; no other three columns are dependent.

9. [Introduction to matroids] In a picture of a matroid, which lines are not drawn?

   Lines that contain only two points. They still exist in the matroid. Example: the matroid with three-point lines abcabcabc and adeadeade also has the two-point lines bd,be,cd,cebd, be, cd, cebd,be,cd,ce (drawn here).

10. [Introduction to matroids] How does the rank of a matrix relate to the dimension of the matroid picture of its columns?

    rank=dimension of the picture+1\boldsymbol{\text{rank} = \text{dimension of the picture} + 1}rank=dimension of the picture+1 Example: a rank 2 matrix gives points on a line (dimension 1); a rank 3 matrix gives points in a plane (dimension 2).

11. [Introduction to matroids] Definition 1.3. EEE is a finite set and I\mathcal{I}I a family of subsets of EEE . Which three axioms make I\mathcal{I}I the independent sets of a matroid?

    (I1) Non-triviality I≠∅\mathcal{I} \neq \emptysetI=∅ . Example: for any matroid, ∅∈I\emptyset \in \mathcal{I}∅∈I by (I1) and (I2). (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: if abeabeabe is independent, so are ababab , eee and ∅\emptyset∅ . (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∪{x}∈I . Example: with a=(…

12. [Introduction to matroids] The finite set EEE on which a matroid is defined is called the ground set of the matroid.

    Example: the columns of a matrix, or the edges of a graph.

13. [Introduction to matroids] What is the rank r(M)r(M)r(M) of a matroid MMM ?

    The size of the largest independent set. Example: the columns (1,0),(0,1),(1,1),(1,2)(1, 0), (0, 1), (1, 1), (1, 2)(1,0),(0,1),(1,1),(1,2) give a matroid of rank 2.

14. [Introduction to matroids] For the matroid on the columns of a matrix, how does r(M)r(M)r(M) compare with the rank of the matrix?

    They are equal. Example: [10110112]\begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 2 \end{bmatrix}[10​01​11​12​] has matrix rank 2, and its largest linearly independent sets of columns have 2 elements.

15. [Introduction to matroids] Theorem 6.1 Let EEE be the columns of a matrix AAA with entries in a field F\mathbb{F}F , and I\mathcal{I}I the collection of all linearly independent subsets of EEE . Then … ?

    M=(E,I)M = (E, \mathcal{I})M=(E,I) is a matroid: I\mathcal{I}I satisfies (I1), (I2) and (I3). (I1) and (I2) are easy: ∅\emptyset∅ is linearly independent, and so is every subset of a linearly independent set. (I3) is a fact from linear algebra.

16. [Introduction to matroids] What is a representable matroid?

    A matroid whose ground set is a set of vectors (independent = linearly independent). Not every matroid is representable.

17. [Introduction to matroids] When one proves that some family I\mathcal{I}I of sets (linearly independent sets, acyclic edge sets, ...) is a matroid, which axiom is usually the real work?

    (I3), augmentation. (I1) non-triviality and (I2) closure under subsets are usually immediate.

18. [Introduction to matroids] E={a,b,c,d}E = \{a, b, c, d\}E={a,b,c,d} and I={∅,a,b,c,d,ab,cd}\mathcal{I} = \{\emptyset, a, b, c, d, ab, cd\}I={∅,a,b,c,d,ab,cd} ( ababab means {a,b}\{a, b\}{a,b} ). Is I\mathcal{I}I the family of independent sets of a matroid?

    No: (I3) fails. ccc and ababab are independent, so (I3) needs acacac or bcbcbc to be independent, and neither is. (I1) and (I2) hold.

19. [Introduction to matroids] E={a,b,c,d}E = \{a, b, c, d\}E={a,b,c,d} and I={∅,a,b,c,d,ab,cd}\mathcal{I} = \{\emptyset, a, b, c, d, ab, cd\}I={∅,a,b,c,d,ab,cd} violates augmentation (I3).Which two pairs can be added to I\mathcal{I}I to get a matroid?

    adadad and bcbcbc . Then the independent pairs are ab,bc,cd,daab, bc, cd, daab,bc,cd,da . Each element forms an independent pair with exactly two of the other three, so for a singleton {x}\{x\}{x} and an independent pair J∌xJ \not\ni xJ∋x , some element of JJJ forms an independent pair with xxx .Example: ccc and ababab : bcbcbc is now independent.

20. [Introduction to matroids] What is the uniform matroid Uk,nU_{k,n}Uk,n​ ( k≤nk \le nk≤n )?

    Ground set with nnn elements; the independent sets are all subsets with at most kkk elements. Example: U2,4U_{2,4}U2,4​ , four points on a line; it is the matroid of the columns (1,0),(0,1),(1,1),(1,2)(1,0), (0,1), (1,1), (1,2)(1,0),(0,1),(1,1),(1,2) .

21. [Introduction to matroids] What is the Boolean algebra BnB_nBn​ as a matroid?

    Un,nU_{n,n}Un,n​ : every subset of the nnn -element ground set is independent. Example: in B2B_2B2​ on {a,b}\{a, b\}{a,b} the independent sets are ∅,a,b,ab\emptyset, a, b, ab∅,a,b,ab .

22. [Introduction to matroids] What two rules let you draw the matroid of a matrix's columns directly, without drawing vectors?

    Each column is a point; three linearly dependent columns give three collinear points. Example: both pictures show the columns (1,0),(1,1),(1,2),(0,1)(1,0), (1,1), (1,2), (0,1)(1,0),(1,1),(1,2),(0,1) labeled a,c,d,ba, c, d, ba,c,d,b ; any of the 4!=244! = 244!=24 labelings of the four-point line works.

23. [Introduction to matroids] In the matroid picture of the columns of a rank 3 matrix, why are three points collinear exactly when the three column vectors are linearly dependent?

    Three vectors are linearly dependent ⇔\Leftrightarrow⇔ they lie in a plane through the origin ⇔\Leftrightarrow⇔ that plane meets the free plane in a line through the three points.

24. [Introduction to matroids] What does a zero column of a matrix give in the matroid picture?

    A loop: a dependent set of size 1, drawn inside a cloud. A loop cannot be drawn as a point in any reasonable way.

25. [Introduction to matroids] A dependent set with one element (a dependent singleton) is called a loop.

26. [Introduction to matroids] What do two parallel nonzero columns ( u=λvu = \lambda vu=λv ) give in the matroid picture?

    A multiple point: a dependent set of size 2, drawn as overlapping disks. Example: d=(−1,0,2)d = (-1, 0, 2)d=(−1,0,2) and f=(2,0,−4)=−2df = (2, 0, -4) = -2df=(2,0,−4)=−2d form a double point dfdfdf .

27. [Introduction to matroids] Columns a,…,ga, \dots, ga,…,g of C=[101−10201−10010001122−40]C = \begin{bmatrix} 1 & 0 & 1 & -1 & 0 & 2 & 0 \\ 1 & -1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 & 2 & -4 & 0 \end{bmatrix}C=⎣⎡​110​0−11​101​−102​012​20−4​000​⎦⎤​ Which sets are the minimal dependent sets with at most 3 elements?

    ggg ; df\ df df ; abc,ade,aef\ abc, ade, aef abc,ade,aef . g=0g = 0g=0 , f=−2df = -2df=−2d , c=a+bc = a + bc=a+b , e=a+de = a + de=a+d , f=2a−2ef = 2a - 2ef=2a−2e . Every set of 4 or more columns is dependent (rank 3).

28. [Introduction to matroids] Do these two pictures represent the same matroid?

    Yes: they have the same dependent sets ( ggg ; dfdfdf ; abcabcabc , adeadeade , aefaefaef ). Only which points are collinear matters, not the order of the points on a line or the shape of the drawing.

29. [Geometries] What is a simple matroid (also called a combinatorial geometry)?

    A matroid with no loops and no multiple points: every set of 1 or 2 elements is independent. Example: four points on a line ( U2,4U_{2,4}U2,4​ ) is simple; a matroid with a double point dfdfdf is not.

30. [Geometries] When the book says " eee is a point of a matroid", what does it assume about eee ?

    eee is not a loop: {e}\{e\}{e} is independent.

31. [Geometries] How do you read the independent sets of a simple rank 3 matroid from its point–line picture?

    Empty set ∅\emptyset∅ is independent. Points Every point is independent. Pairs Every pair of points is independent. Triples A triple is independent if and only if the three points are not collinear. Example: on two lines abcabcabc and adeadeade , the triple abdabdabd is independent and abcabcabc is not. Four or more points Never independent.

32. [Geometries] How does reading independent sets from a rank 3 picture change when the matroid is not simple?

    Every element in the cloud is a loop (dependent), and every pair of elements of a multiple point is dependent. Example: with loop eee and double point bcbcbc , the sets eee , bcbcbc and every set containing eee or bcbcbc are dependent.

33. [Geometries] Which sets are independent in this matroid on {a,b,c,d,e}\{a, b, c, d, e\}{a,b,c,d,e} ?

    Every set of at most 3 elements except abcabcabc and adeadeade . Sets of 4 or more elements are dependent, since the rank is 3.

34. [Geometries] Which sets are the minimal dependent sets with at most 3 elements in this matroid on {a,…,g}\{a, \dots, g\}{a,…,g} ?

    eee ; bc\ bc bc ; abd,acd,dfg\ abd, acd, dfg abd,acd,dfg . eee is in the cloud, bcbcbc is a double point, and the two lines are a (bc) da\,(bc)\,da(bc)d and fdgfdgfdg .

35. [Geometries] When are two matroids isomorphic?

    When the ground sets can be relabeled (by a bijection) so that the independent sets of one become exactly the independent sets of the other. Example: these two are isomorphic via d↦ad \mapsto ad↦a , e↦ge \mapsto ge↦g , {b,c}↦{d,f}\{b, c\} \mapsto \{d, f\}{b,c}↦{d,f} , a↦ea \mapsto ea↦e , f↦bf \mapsto bf↦b , g↦cg \mapsto cg↦c (left to right).

36. [Geometries] What is the simplification of a matroid MMM ?

    The matroid obtained from MMM by deleting the loops and replacing each multiple point by a single point. Example: MMM (left) has the loop eee and the double point bcbcbc ; the simplification M′M&#x27;M′ (right) has the points a,b,d,f,ga, b, d, f, ga,b,d,f,g .

37. [Geometries] What is a basis of a matroid?

    A maximal independent set. All bases of a matroid have the same number of elements, r(M)r(M)r(M) .Example: in the rank 3 matroid on {a,…,e}\{a, \dots, e\}{a,…,e} with lines abcabcabc and adeadeade , the bases are the (53)−2=8\binom{5}{3} - 2 = 8(35​)−2=8 triples other than abcabcabc and adeadeade .

38. [Geometries] What is a circuit of a matroid?

    A minimal dependent set: dependent, and every proper subset is independent. Example: a loop is a circuit of size 1; a double point dfdfdf is a circuit of size 2.

39. [Geometries] What are the circuits of this rank 3 matroid?

    abcabcabc , adeadeade and bcdebcdebcde . bcdebcdebcde is dependent (4 elements, rank 3), and its 3-subsets bcd,bce,bde,cdebcd, bce, bde, cdebcd,bce,bde,cde are all independent.

40. [Geometries] This is the Fano plane F7F_7F7​ . Which triples are its lines (dependent triples)?

    The 7 lines abe,adg,acf,bdf,bcg,cde,efgabe, adg, acf, bdf, bcg, cde, efgabe,adg,acf,bdf,bcg,cde,efg . efgefgefg is a line even though the three points are drawn on a circle. All sets of at most 2 points are independent, and all sets of 4 or more are dependent.

41. [Geometries] How many bases does the Fano plane F7F_7F7​ have?

    28=(73)−7\boldsymbol{28 = \binom{7}{3} - 7}28=(37​)−7 F7F_7F7​ has rank 3: every triple except the 7 lines is a basis.

42. [Geometries] Fano plane F7F_7F7​ : 7 points, every pair independent, 7 three-point lines, any two points lie on exactly one line.Why does (I3) hold for independent sets AAA , BBB with ∣A∣=1|A| = 1∣A∣=1 , ∣B∣=2|B| = 2∣B∣=2 ?

    Some x∈Bx \in Bx∈B is not the element yyy of AAA , and every pair {x,y}\{x, y\}{x,y} of points is independent.

43. [Geometries] Fano plane F7F_7F7​ : 7 points, every pair independent, 7 three-point lines, any two points lie on exactly one line.Why does (I3) hold for independent sets A={x,y}A = \{x, y\}A={x,y} and BBB with ∣B∣=3|B| = 3∣B∣=3 ?

    Let zzz be the third point on the line through xxx and yyy . BBB is independent, so B≠{x,y,z}B \neq \{x, y, z\}B={x,y,z} and BBB contains some w≠x,y,zw \neq x, y, zw=x,y,z ; then A∪{w}A \cup \{w\}A∪{w} is independent.

44. [Geometries] In the Fano plane F7F_7F7​ , how many lines pass through each point and how many points lie on each line?

    3 lines through every point, 3 points on every line. This point–line symmetry is characteristic of projective planes.

45. [Geometries] The Fano plane F7F_7F7​ is represented by the columns a,…,ga, \dots, ga,…,g of [100111001011010011011]\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{bmatrix}⎣⎡​100​010​001​111​110​101​011​⎦⎤​ For which fields does this work, and why?

    Only for fields with 2=02 = 02=0 (binary, i.e. modulo 2 arithmetic): e+f+g=(2,2,2)e + f + g = (2, 2, 2)e+f+g=(2,2,2) must be 0 so that the line efgefgefg is dependent. Equivalently, det⁡[110101011]=−2\det \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} = -2det⎣⎡​110​101​011​⎦⎤​=−2 must be 0. The other six lines are dependent over every field, e.g. e=a+be = a + be=a+b .

46. [Geometries] What is the non-Fano matroid F7−F_7^-F7−​ ?

    The Fano plane F7F_7F7​ with the triple efgefgefg declared independent; the line efgefgefg becomes the three two-point lines ef,eg,fgef, eg, fgef,eg,fg . Over R\mathbb{R}R , the columns of the matrix that represents F7F_7F7​ in characteristic 2 give F7−F_7^-F7−​ , since det⁡[e f g]=−2≠0\det[e\,f\,g] = -2 \neq 0det[efg]=−2=0 .

47. [Geometries] In a simple rank 3 matroid, what is a two-point line in terms of independent sets?

    An independent set {x,y}\{x, y\}{x,y} such that {x,y,z}\{x, y, z\}{x,y,z} is independent for every other point zzz . Example: in the non-Fano matroid F7−F_7^-F7−​ , efefef is a two-point line.

48. [Geometries] One procedure that declares a dependent set of a matroid independent and still gives a matroid is called relaxing a hyperplane.

    Example: relaxing the line efgefgefg of the Fano plane F7F_7F7​ gives the non-Fano matroid F7−F_7^-F7−​ .

49. [Geometries] Why can't the Fano plane F7F_7F7​ be drawn in the Euclidean plane with all 7 lines straight?

    F7F_7F7​ has no two-point lines, but every finite set of points in the plane, not all on one line, has a two-point line (Sylvester–Gallai theorem). This is why the line efgefgefg is drawn as a circle.

50. [Geometries] In this rank 4 matroid on {a,…,g}\{a, \dots, g\}{a,…,g} (the only three-point line is abcabcabc ), when is a set of 4 points dependent?

    When the 4 points are coplanar. Example: acdgacdgacdg is dependent; abfgabfgabfg is independent. Every set of 5 or more points is dependent.

51. [Geometries] Which planes of this rank 4 matroid contain at least 4 points?

    abcdgabcdgabcdg , abcefabcefabcef and defgdefgdefg . bbb lies on the line acacac , so bbb is in every plane containing aaa and ccc . The ends afgafgafg and cdecdecde have only 3 points.

52. [Graphs and matroids] In this book, what may a graph contain besides edges joining two different vertices?

    Loops (an edge joining a vertex to itself) and multiple edges (distinct edges joining the same two vertices). Other authors call such a graph a multigraph.

53. [Graphs and matroids] When are two edges incident, and when are two vertices adjacent?

    Edges: they have a common vertex. Vertices: some edge joins them. Example: edges bbb and ccc are incident (at v2v_2v2​ ); bbb and eee are not.

54. [Graphs and matroids] What is a path in a graph?

    A sequence of edges, each incident with the next, with no repeated edge and no repeated vertex. Example: (i) b,cb, cb,c is a path; (ii) b,eb, eb,e is not, since bbb and eee are not incident; (iii) abcabcabc is a cycle.

55. [Graphs and matroids] What is a cycle in a graph?

    A path that starts and ends at the same vertex. The order of its edges is ignored: in the graph below, {b,c,d,e}\{b, c, d, e\}{b,c,d,e} is the cycle bcdebcdebcde .

56. [Graphs and matroids] Is a,b,d,e,f,ca, b, d, e, f, ca,b,d,e,f,c a path or a cycle?

    Neither: the vertex v3v_3v3​ repeats; the edges form two edge-disjoint cycles abcabcabc and defdefdef .

57. [Graphs and matroids] When is a graph connected?

    There is a path between every pair of vertices; otherwise it is disconnected. Example: HHH is disconnected (no path from v2v_2v2​ to v6v_6v6​ ). HHH is still one graph, with two connected components.

58. [Graphs and matroids] When is HHH a subgraph of a graph GGG ?

    Every vertex and every edge of HHH belongs to GGG . Example: paths and cycles of GGG are subgraphs of GGG .

59. [Graphs and matroids] What are a tree, a forest and a spanning tree?

    Tree A connected graph with no cycles. Forest A graph (connected or not) with no cycles. Spanning tree For a connected graph GGG : a tree in GGG that contains all vertices of GGG . Example: subgraphs of the graph with edges a=v1v3a = v_1v_3a=v1​v3​ , b=v1v2b = v_1v_2b=v1​v2​ , c=v2v3c = v_2v_3c=v2​v3​ , d=v1v4d = v_1v_4d=v1​v4​ , e=v3v4e = v_3v_4e=v3​v4​ : (i) a tree, (ii) a disconnected forest, (iii) a spanning tree.

60. [Graphs and matroids] From the matroid viewpoint, is the subgraph "edge eee " different from the subgraph "edge eee plus an extra vertex v1v_1v1​ "?

    No: subgraphs are identified by their sets of edges.

61. [Graphs and matroids] GGG : vertices v1,v2,v3,v4v_1, v_2, v_3, v_4v1​,v2​,v3​,v4​ ; edges a=v1v3a = v_1v_3a=v1​v3​ , b=v1v2b = v_1v_2b=v1​v2​ , c=v2v3c = v_2v_3c=v2​v3​ , d=v1v4d = v_1v_4d=v1​v4​ , e=v3v4e = v_3v_4e=v3​v4​ (a 4-cycle bcdebcdebcde with the diagonal aaa ). How many spanning trees does GGG have?

    8=(53)−2\boldsymbol{8 = \binom{5}{3} - 2}8=(35​)−2 A spanning tree has 4−1=34 - 1 = 34−1=3 edges; every 3 edges except the cycles abcabcabc and adeadeade form one.

62. [Graphs and matroids] GGG : vertices v1,v2,v3,v4v_1, v_2, v_3, v_4v1​,v2​,v3​,v4​ ; edges a=v1v3a = v_1v_3a=v1​v3​ , b=v1v2b = v_1v_2b=v1​v2​ , c=v2v3c = v_2v_3c=v2​v3​ , d=v1v4d = v_1v_4d=v1​v4​ , e=v3v4e = v_3v_4e=v3​v4​ (a 4-cycle bcdebcdebcde with the diagonal aaa ). How many forests (acyclic edge sets) does GGG have, and how many of them are disconnected?

    24 forests, 2 of them disconnected ( bebebe and cdcdcd ). 111 empty +5+ 5+5 single edges +10+ 10+10 pairs +8+ 8+8 spanning trees =24= 24=24 . Of the 10 pairs, only bebebe and cdcdcd have no common vertex, so 222222 of the forests are trees (counting ∅\emptyset∅ ).

63. [Graphs and matroids] In a connected graph, what are the spanning trees and the cycles in terms of acyclic edge sets?

    Spanning trees: maximal acyclic edge sets. Cycles: minimal edge sets that are not acyclic. These become the bases and the circuits of the cycle matroid.

64. [Graphs and matroids] Theorem 1.15 If GGG is a connected graph with nnn vertices, then … ?

    GGG has a spanning tree, and every spanning tree of GGG has n−1n - 1n−1 edges. A spanning tree can be built one edge at a time, each new edge joining the tree to a new vertex.

65. [Graphs and matroids] Which theorem counts the spanning trees of a connected graph, and how?

    Kirchhoff's Matrix-Tree Theorem: the number is a determinant of a matrix built from the graph.

66. [Graphs and matroids] A set of edges of a graph that contains no cycle is called acyclic.

67. [Graphs and matroids] Theorem 4.1 Let EEE be the set of edges of a graph GGG and I\mathcal{I}I the collection of all acyclic subsets of EEE . Then … ?

    M=(E,I)M = (E, \mathcal{I})M=(E,I) is a matroid, the cycle matroid M(G)M(G)M(G) . Its independent sets are the edge sets of forests of GGG .

68. [Graphs and matroids] What are the circuits of the cycle matroid M(G)M(G)M(G) ?

    The cycles of GGG (their edge sets). Example: here the circuits are abcabcabc , adeadeade and bcdebcdebcde ; the matroid is the one with lines abcabcabc and adeadeade .

69. [Graphs and matroids] For a connected graph GGG , what are the bases of M(G)M(G)M(G) ?

    The spanning trees of GGG . Example: for the 4-cycle bcdebcdebcde with diagonal aaa , the bases are the 8 three-edge sets other than abcabcabc and adeadeade .

70. [Graphs and matroids] Theorem 1.17 If GGG is a connected graph with nnn vertices, then the rank of M(G)M(G)M(G) is … ?

    n−1\boldsymbol{n - 1}n−1 , the number of edges in a spanning tree. Example: a connected graph with 4 vertices has a cycle matroid of rank 3.

71. [Graphs and matroids] In the cycle matroid of a graph, what do a loop ggg and a double edge d,fd, fd,f become?

    The loop ggg is a matroid loop; the double edge dfdfdf is a double point (a circuit of size 2).

72. [Graphs and matroids] Can you tell from the cycle matroid M(G)M(G)M(G) which vertex a loop of GGG is incident with?

    No. A loop is a dependent singleton whichever vertex it is incident with.

73. [Graphs and matroids] When is a matroid graphic?

    It is the cycle matroid M(G)M(G)M(G) of some graph GGG . Not every matroid is graphic. Example: U2,4U_{2,4}U2,4​ is not.

74. [Graphs and matroids] Every graphic matroid is the cycle matroid of a connected graph, and a spanning tree of a connected graph with nnn vertices has n−1n - 1n−1 edges.Why is U2,4U_{2,4}U2,4​ (4 elements, independent sets = sets of size at most 2) not graphic?

    A graph GGG with M(G)=U2,4M(G) = U_{2,4}M(G)=U2,4​ would have 3 vertices, 4 edges, no loops and no multiple edges, but such a graph has at most 3 edges. Bases have 2 edges, so n−1=2n - 1 = 2n−1=2 . Singletons and pairs are independent, so there are no loops or multiple edges.

75. [Graphs and matroids] Proposition 4.3 If GGG is a graph, then there is a connected graph G′G&#x27;G′ with … ?

    M(G)=M(G′)\boldsymbol{M(G) = M(G&#x27;)}M(G)=M(G′) Identify a vertex of one component with a vertex of another (vertex identification; the reverse is vertex splitting): acyclic edge sets stay acyclic, and vice versa.

76. [Graphs and matroids] Are graphic matroids representable?

    Yes: there is a matrix with a column for each edge in which a set of columns is linearly independent if and only if the edges are acyclic.

77. [Graphs and matroids] In pictures, how does the book distinguish a graph from a geometric picture of a matroid?

    Graphs: small hollow vertices, labeled edges. Matroids: large filled points, labeled points. In a graph, the matroid is on the edges and dependence comes from cycles; in a geometric picture, the matroid is on the points and dependence is geometric.

78. [Bipartite graphs, transversal matroids] What is a bipartite graph?

    A graph whose vertex set is X∪YX \cup YX∪Y with X,YX, YX,Y disjoint and nonempty, and every edge joins a vertex of XXX to a vertex of YYY .

79. [Bipartite graphs, transversal matroids] What is a matching in a bipartite graph?

    A set of edges, no two of which share a vertex. A matching uses as many vertices I⊆XI \subseteq XI⊆X as J⊆YJ \subseteq YJ⊆Y ; written M=(I,J)M = (I, J)M=(I,J) . Example: aaa –cook, ddd –kitchen cleaner is a matching with I={a,d}I = \{a, d\}I={a,d} .

80. [Bipartite graphs, transversal matroids] Applicants a,…,ea, \dots, ea,…,e and the jobs they want. Which sets of applicants can all be hired (matched to different jobs)?

    ∅\emptyset∅ , every single person, every pair except bcbcbc , every triple except abc,bcd,bceabc, bcd, bceabc,bcd,bce ; no set of 4 or more. bbb and ccc both want only "food taster". Example: adeadeade : aaa cook, ddd food taster, eee kitchen cleaner.

81. [Bipartite graphs, transversal matroids] Theorem 7.2 Let GGG be a bipartite graph with vertex partition X∪YX \cup YX∪Y , and I\mathcal{I}I the collection of sets I⊆XI \subseteq XI⊆X such that III is exactly the set of vertices of XXX used by some matching M=(I,J)M = (I, J)M=(I,J) . Then … ?

    I\mathcal{I}I satisfies (I1), (I2) and (I3): it is the family of independent sets of a matroid, the transversal matroid M(G)M(G)M(G) . Example: in a star with center y∈Yy \in Yy∈Y and leaves a,b∈Xa, b \in Xa,b∈X , the independent sets are ∅,a,b\emptyset, a, b∅,a,b (rank 1, ababab a double point).

82. [Bipartite graphs, transversal matroids] Draw the transversal matroid on {a,b,c,d,e}\{a, b, c, d, e\}{a,b,c,d,e} of this bipartite graph.

    Rank 3: a double point bcbcbc and the points a,d,ea, d, ea,d,e , with no three-point lines. The only minimal dependent sets are bcbcbc and the sets of 4 elements not containing bcbcbc .

83. [Bipartite graphs, transversal matroids] In the transversal matroid of this bipartite graph on {a,b,c,d,e}\{a, b, c, d, e\}{a,b,c,d,e} , which triples are dependent?

    abcabcabc and adeadeade : a,b,ca, b, ca,b,c are joined only to {x,y}\{x, y\}{x,y} , and a,d,ea, d, ea,d,e only to {y,z}\{y, z\}{y,z} . Example: acacac is independent ( aaa – yyy , ccc – xxx ). The matroid is the cycle matroid of the 4-cycle with a diagonal.

84. [Bipartite graphs, transversal matroids] Who discovered the connection between matroids and matchings in bipartite graphs, and when?

    Richard Rado, in the 1940s.