Matroid Theory
Extra Material

Chain Groups

To the main course page | assignments | corrections page

Extra Problems

Index
  1. Flats
  2. Minors
  3. Projective geometry
  4. Modularity
  5. Coextensions and lifts
  6. Connectivity
  7. Characteristic and Tutte polynomials
  8. Hyperplane arrangements
  9. Graphs and signed graphs
  10. Gain and biased graphs
Notes
Some notes are under the topic headings. Here are general notes:

Topical list

  1. Extra problem on flats.
    • A very valuable consequence of Lemma 1.4.6 is the following corollary:
      Corollary 1.4.6.1. If X ⊆ E(M) and C is a circuit with an element y such that C\y ⊆ X, then y ∈ cl(X). In particular, if X is closed, and C\y ⊆ X, then y ∈ X.

    1. Prove that the flats are precisely the sets that are intersections of coatoms ("hyperplanes"). We say a geometric lattice is coatomic.
    2. Show that the lattice of flats of M(Kn) is isomorphic to the partition lattice Πn. Definition: Πn is the set of partitions of [n], partially ordered by τ ≤ π if every block of τ is contained in a block of π.

  2. Extra problems on minors (Chapter 3).
    1. (Sect. 3.2) Suppose M is represented by vectors over a field F, and e is an element of M. Theorem. M/e is represented by the vectors obtained by projecting the given vectors onto any complementary subspace of the subspace <e> spanned by e. Prove the theorem by means of:
      1. rank;
      2. flats;
      3. independent sets.
    2. (Sect. 3.2) Show by example that, if you carry out the same operation but projecting along a line L that isn't spanned by a representing vector, then you might get a matroid that isn't a contraction M/e by an element of M.
    3. (Sect. 3.2) Prove the matrix-contraction theorem 3.2.6 by means of:
      1. duality;
      2. rank;
      3. flats.
      Any opinion on which is simplest?
    4. Let M be a spike with tip t. Prove that M/t is both graphic and cographic.

  3. Extra problems on projective geometry (Section 6.1). (The most important is the second one.)
    1. Practice with projective geometries. (Very important.) The problem is for q = 5. (q = 4 is also very interesting but harder.)
      1. Write down all the equivalence classes that are the points of PG(1,5). This means: write down names of the equivalence classes (these are in brackets []) and write down all the elements of each equivalence class (these are vectors in GF(5)2 and are written with parentheses ()).
      2. Look for a pattern that lets you write down names of all the equivalence classes easily.
      3. Write down names of all the equivalence classes that are the points of PG(2,5). Again, look for a pattern that makes it easy. Your pattern should make it easy to see that there are q2 + q1 + q0 points.
      4. Find equations of the "ordinary" (or "affine") lines in PG(2,5). (This means the lines that are not the ideal line.) Do you see a pattern in the equations? (You do not need to do all the lines, but do at least 10 of them.)
      5. Each ordinary line contains a single ideal point. Find the equation of that ideal point, for several of the ordinary lines you studied in (c).

    2. Make sure you can prove that a coordinatizable projective geometry satisfies the modular law. If ambitious, also prove the modular law for projective planes in general (thus it will be proved for all projective geometries, by the coordinatization theorem).

    3. A subset S of a matroid M is line-closed if, whenever x,y in S, then cl({x,y}) is contained in S.
      1. Prove that any flat in a matroid is line closed.
      2. Prove that, in a coordinatizable projective geometry, any line-closed set is a flat. (Recall that we define the matroid of such a PG as the simplification of a vector matroid.)
      3. Prove by counterexample(s) that (b) is not true of matroids in general.
      The point of this problem is that it tells you a simple way to know which point sets in an abstract projective geometry are flats.

    4. In PG(n-1,q), the number of complements of a rank-k flat is equal to qk(n-k). (Prove.)

  4. Extra problem on modularity.
    1. A simple graph G is called chordal (or triangulated) if every circle of length 4 or more has a chord. In other words, there are no induced circles except triangles. A matroid M is supersolvable if it has a maximal chain of modular flats. Interesting fact: G is chordal if and only if M(G) is supersolvable. This is most easily proved by the following theorem.
      Theorem (mostly due to Dirac, partly Stanley). TFAE:
      1. G is chordal.
      2. V(G) can be ordered v1,v2,...,vn so that in each induced subgraph G:{v1,v2,...,vi} the neighborhood N(vi) is a clique (then vi is a simplicial vertex).
      3. M(G) is supersolvable.
      The theorem raises a homework question and research problems.
      1. Proving this is a good problem though it may be too long for homework. Think about it enough to learn it.
      2. How to generalize the theorem is uncertain. What is a chordal matroid? There are definitions but they don't seem to fit this theorem. What concept generalizes a simplicial vertex? The latter seems to require vertices, and it has been generalized to matroids of signed and biased graphs (Zaslavsky and Koban), but chordality has not. These are research questions.

  5. Extra problem on coextensions and lifts.
    1. Consider the free coextension L∞(M). Does its lattice of flats Lat(L∞(M)) = I(M) ∪ { F ∪ e∞ : F in Lat(M) } ?
      (Here e∞ is the extra point.) If not, what is the correct formula?

  6. Extra problems on connectivity.
    1. Suppose M is n-connected. If n ≤ r(M), then every cocircuit has rank ≥ n. If n > r(M), then every cocircuit spans M and every copoint is independent.
    2. Use #1 to classify the matroids with λ(M) = infinity.
    3. Concerning Theorem 8.3.1: In class I defined Mi to be
      M | (Xi ∪ C) / (C \ Xi \ pi)
      with pi replaced by a point p not in E(M), where C is a circuit that is not contained in either X1 or X2 and pi is a point in C \ Xi.
      1. Show that this definition of Mi is equivalent to Oxley's in Section 8.3.
      2. It follows from (a) that my definition is independent of the choice of C. Show this directly from my definition (and you may use Lemmas 8.3.2-3), without using (a).
    4. What is often called "Tutte's Wheels and Whirls Theorem" is Theorem 8.4.5': Let M be a 3-connected matroid of rank at least 3. Then there exists a sequence M=M0, M1, ..., Mk (with some k ≥ 0) such that each Mi = Mi-1 \ ei or Mi-1 / ei , all Mi are 3-connected, and Mk is a wheel or whirl matroid of rank at least 3. At any rate, find out whether this is the correct statement and show that the correct statement is easily equivalent to Theorem 8.4.5.

  7. Problems on characteristic and Tutte polynomials.
    1. The characteristic polynomial pM(λ) := ∑S ⊆ E (−1)|S| λr(M)−r(S).
    2. The corank-nullity (or rank generating) polynomial RM(u, v) := ∑S ⊆ E u|S|-r(S) vr(M)−r(S).
    3. The Tutte polynomial can be defined (though this is not the best definition) as TM(x, y) := RM(x−1, v−1).

    #1-3: For each of the above polynomials f:

    1. Prove that f, as a function of matroids, satisfies f(M) = f(M\e) + α f(M/e) for a suitable constant α (possibly different for different f) and any e in E that is neither a loop nor a coloop. For f with α ≠ 1, find how to modify f so the modified function satisfies the law with α = 1.
    2. Evaluate f on discrete matroids (where every element is a loop or coloop).

    1. How are these polynomials related to each other? (Easy, not a trick problem.)

  8. Problems on hyperplane arrangements.

    1. Show that in the matroid of a homogeneous hyperplane arrangement H, the rank function is r(S) = codim(∩ S), for any S ⊆ H.
    2. For a homogeneous hyperplane arrangement H, the arrangement induced by H in h is Hh = { h' ∩ h : h' in H and h' ≠ h}.
      Show that if h is in H, then M(Hh) = M(H)/h.
    3. A region is a connected component of Rn − (∪ H), and ρ(H) is the number of regions. Assume H is homogeneous.
      1. Show that ρ(H) = ρ(H \ h) + ρ(Hh).
      2. Deduce that ρ(H) = |pH(−1)|.
    4. Let β(H) be the number of bounded regions of H. Show that β(H) = |pH(1)|.
    5. Draw a central arrangement H of a few lines in A2(R).
      1. Find and label all the faces of this arrangement (all dimensions).
      2. Find the characteristic polynomial of your arrangement H. Evaluate at 1 and −1 and compare to the actual numbers of regions.
      3. Now extend H to the projective plane P2(R) and to its projectivization HP, and find and label all the additional faces (at infinity).
      4. Find and label all the faces of this projective arrangement (all dimensions). [Correction: This is the same as the preceding part. Oops!]
      5. Find the characteristic polynomial of the projective arrangement HP. Evaluate at −1 and compare to the actual number of regions.
    6. Draw a noncentral arrangement H of a few lines in A2(R) and repeat the previous problem for this arrangement.

  9. Problems on graphs and signed graphs.

    1. For the graph G = K4−e (i.e., delete one edge):
      1. Calculate the chromatic polynomial χG(λ).
      2. Find the cycle matroid M(G); make an affine diagram of it.
      3. Find the characteristic polynomial pM(G)(λ).
      4. What are the Whitney numbers of the first kind, wi(M(G))?
      5. Find χ(G).
    2. The same for G = K4. In part b, compare the affine diagram with those of the Fano and non-Fano matroids.
    3. Find the hyperplane arrangements H[K4−e] and H[K4], their intersection lattices, and their characteristic polynomials by using the lattices. Compare to the chromatic polynomials.
    4. Draw a picture of the cross-section of H[K3] in the plane ∑i xi = 1.
    5. For the signed graph Σ = +K3:
      1. Find its hyperplane arrangement H[Σ] and its intersection lattice.
      2. Find the characteristic polynomial of H[Σ] from the intersection lattice; compare to the chromatic polynomial of Σ.
      3. Find the numbers of regions and bounded regions.
    6. This is for the signed graph Σ = −K3.
      1. Find its hyperplane arrangement H[Σ] and its intersection lattice.
      2. Draw a picture of the cross-section of H[Σ] in the plane ∑i xi = 1.
      3. Calculate the chromatic polynomial χΣ(λ) and the zero-free chromatic polynomial χ*Σ(λ).
      4. Find the characteristic polynomial pH[Σ](λ) from the intersection lattice; compare to the chromatic polynomial of Σ.
      5. Find the numbers of regions and bounded regions.
      6. Find the chromatic number χ(Σ).
    7. This is for the signed graph Σ = ±K2○.
      1. Find its hyperplane arrangement H[Σ] and its intersection lattice.
      2. Draw a picture of H[Σ].
      3. Calculate the chromatic polynomial χΣ(λ) and the zero-free chromatic polynomial χ*Σ(λ).
      4. Find the characteristic polynomial pH[Σ](λ) from the intersection lattice; compare to the chromatic polynomial of Σ.
      5. Find the numbers of regions and bounded regions.
      6. Find the chromatic number χ(Σ).
    8. This is for Σ = ±K3○.
      1. Find its hyperplane arrangement H[Σ] and its intersection lattice.
      2. Draw a picture of the cross-section of H[Σ] in the plane ∑i xi = 1.
      3. Calculate the chromatic polynomial χΣ(λ) and the zero-free chromatic polynomial χ*Σ(λ).
      4. Find the characteristic polynomial pH[Σ](λ) from the intersection lattice; compare to the chromatic polynomial of Σ.
      5. Find the numbers of regions and bounded regions.
      6. Find the chromatic number χ(Σ).
    9. Draw affine diagrams of the frame matroids F(Σ) for the following signed graphs:
      1. ±K2○.
      2. ±K3.
      3. −K4.
      4. ±K4.
    10. Calculate the two chromatic polynomials, χΣ(λ) and χ*Σ(λ), for the following signed graphs:
      1. −Kn.
      2. ±Kn○.
      3. ±Kn.
    11. For an arbitrary signed graph Σ, find the intersection ∩ H[Σ] in terms of properties of Σ. What is its dimension?
    12. For which signed graphs Σ is the frame matroid F(Σ) binary? Not binary? Partial results are acceptable in this kind of question, but the stronger your result, the better.
    13. For which Σ is F(Σ) ternary? Not ternary?
    14. For which Σ is F(Σ) regular? Not regular?
    15. For which signed graphs Σ is the lift matroid L(Σ) binary? Not binary? The same for the extended lift matroid L∞(Σ).
    16. For which Σ is L(Σ) ternary? Not ternary? The same for L∞(Σ).
    17. Prove that the matroid R10 (in Oxley) = F(−K5). Can you deduce from this that R10 is regular? (It is regular.)
    18. Prove that χΣ(λ) = χΣ*(λ) if and only if Σ is balanced.
    19. For which signed graphs Σ is χΣ(λ) = χΣ*(λ−1)?

  10. Problems on gain and biased graphs.
    • An (elementary) lift of M is a coextension with the extra point deleted.
    • A linear (sub)class of circuits in a matroid M is a subclass B of C such that, if C, C' ∈ B, nul(C ∪ C') = 2, and D is another circuit contained in C ∪ C', then D ∈ B. (N.B. Don't confuse this B with the class of bases. It's a subclass of the class C of circuits.)
    • Here Φ means a gain graph with gain group G. Ω means a biased graph.
    • A subset of E is called balanced if every circuit in it belongs to B. It is contrabalanced if it contains no circuit from B.
    • A pseudoforest is a graph in which every component has cyclomatic number 0 or 1.

    1. Show that a linear class of circuits determines an elementary coextension of M. We call this the extended lift of M, L∞(M, B). Deleting the extension point, we have the lift matroid L(M, B). (See Oxley §7.2 for coextension of a matroid.)
    2. What is a linear class of circuits in a graphic matroid? Describe in terms of the graph Γ (with proof). I call the pair Ω = (Γ, B) a biased graph.
    3. Describe some aspects of the frame matroid F(Γ, B) of a biased graph in terms of the graph, especially, the circuits, the rank function, the flats, the independent sets.
    4. Describe some aspects of the lift matroid of a biased graph in terms of the graph, especially, the circuits, the independent sets, the flats.
    5. The bicircular matroid of a graph Γ is defined as F(Γ, ∅). Describe some aspects of F(Γ, ∅) in terms of the graph, especially the flats, also the circuits, the rank function, the independent sets.
    6. Let Wr be the r-spoke wheel graph. Show that the whirl Wr = F(Wr, ∅) = L(Wr, ∅), the frame matroid of the contrabalanced wheel graph. (This is the bicircular matroid of the wheel.)
    7. Calculate the two chromatic polynomials, χΦ(λ) and χ*Φ(λ), for the following gain graphs with gains in a group G of finite order m with identity element 1:
      1. G·Kn○.
      2. G·Kn.
      3. (G \ 1)·Kn.
      4. G·C4○, where C4 is the cycle of length 4.
      5. G·C4.
    8. Prove that the chromatic polynomial and also the zero-free chromatic polynomial of a gain graph Φ are invariant under switching.
    9. Prove that switching is a group action on gain graphs. That means if Φ is a gain graph and ζ and η are two switching functions, then (Φζ)η = Φζη.
    10. Prove that χΩ(λ) = χΩ*(λ) if and only if Ω is balanced, for a biased graph Ω, or for a gain graph (but that is less general).
    11. Find two gain graphs Φ and Ψ with the same gain group, on the same underlying graph Γ, which are not switching equivalent but have the same balanced circles.
    12. For which group expansion graphs Φ = G·Kn is the frame matroid F(Φ) binary? Not binary?
    13. For which Φ = G·Kn is F(Φ) ternary? Not ternary?
    14. For which group expansions Φ = G·Cn is F(Φ) binary? Not binary?
    15. For which Φ = G·Cn is F(Φ) ternary? Not ternary?
    16. How are #12 and #14 related to each other? How are #13 and #15 related to each other?
    17. For which group expansion graphs Φ = G·Kn is the lift matroid L(Φ) binary? Not binary?
    18. For which Φ = G·Kn is L(Φ) ternary? Not ternary?
    19. For which group expansions Φ = G·Cn is L(Φ) binary? Not binary?
    20. For which Φ = G·Cn is L(Φ) ternary? Not ternary?
    21. How are #17 and #19 related to each other? How are #18 and #20 related to each other?
    22. Prove that a biased expansion of Kn with n ≥ 4 is a group expansion. Hint: The important case is n = 4.
    23. If you know what a groupoid (category theory) is, prove that a groupoid with n objects is equivalent to a biased expansion of Kn, hence is a group expansion if n ≥ 4 by the preceding problem.
    24. Given two graphs (or gain graphs, etc.) on disjoint vertex sets, Γ1 and Γ2, write Γ1 ∪v Γ2 for the result of identifying one vertex in each graph to a single vertex. (It doesn't matter which.)
      1. Compare the lift matroids of Φ1 ∪ Φ2 (disjoint union) and Φ1 ∪v Φ2. How does the matroid of Φ1 ∪v Φ2 depend on the choice of identified vertices?
      2. Compare the frame matroids of Φ1 ∪ Φ2 (disjoint union) and Φ1 ∪v Φ2. How does the matroid of Φ1 ∪v Φ2 depend on the choice of identified vertices?
    25. Find a biased graph Ω that cannot be represented as a gain graph.
    26. Let Ω be any biased graph whose underlying graph is 2Cn (a circle in which each edge is doubled), in which there are no balanced digons (digon = circle of length 2, i.e., doubled edge).
      1. Prove that spikes (defined by Oxley) are the extended lift matroids of these biased graphs. Based on this fact, what can you say about the structure of spikes?
      2. A swirl is the frame matroid of this kind of biased graph. Based on this fact, what can you say about the structure of swirls?
    27. Prove the subset expansion formulas for the chromatic and zero-free chromatic polynomials of a gain graph, i.e., χ[*]Φ(λ) = ∑S (−1)|S| λb(S), where S ranges over all subsets of E for the chromatic polynomial (no *) and all balanced subsets for the zero-free polynomial (with *). Hint: Induction on |E| and deletion/contraction lemmas.
          Or, use Möbius inversion on the improper coloring method to prove the Möbius expansion formulas, χ[*]Φ(λ) = ∑F μ(∅,F) λb(F), where F ranges over all frame-matroid flats or all balanced flats, respectively.
          Note that the subset and Möbius formulas are equivalent by a theorem in the Möbius chapter, although the two proof methods are completely different.
    28. Open problem. We have coloring interpretations of χΦ(λ) for λ = k|G|+1 and χ*Φ(λ) for λ = k|G|, which give us one polynomial for each residue class 0 and 1 (mod |G|) of integers λ > 0, but no such interpretation for any other residue class. Is there a coloring interpretation, or any counting interpretation, for other values of λ modulo |G|? This is an open question for all |G| > 2.

To the main course page | assignments | corrections page