Matroid Theory Assignments

This page will be updated gradually.

Index to:

• readings and problems;
• the list of extra problems.

Readings: Read these lightly first, then carefully.
Do the recommended problems and your choice of other problems.
Hand in the specified problems.
The Extra Problems are below the assignments.

Extra Problems

• Extra problems on duality: PDF file.

• 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?

• 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)² 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 q² + q¹ + q⁰ 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, 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 q^k(n-k). (Prove.)

• 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. G has a vertex whose neighborhood is a clique (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.

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

• Extra problems on 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.)
  • 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 L₀(M, B). We call the corresponding lift L(M, B).
  2. What is a linear class of circuits in a graphic matroid? Describe in terms of the graph Γ. I call the pair Ω = (Γ, B) a biased graph.
  3. Describe some aspect of the lift matroid of a biased graph in terms of the graph, especially, the circuits, the independent sets, the flats. (With proofs, of course.)
  4. Another matroid, the frame matroid G(Γ, B), can be defined to have as independent sets the contrabalanced spanning pseudoforests. Describe some other aspect of the frame matroid of a biased graph in terms of the graph, especially, the circuits, the rank function, the flats. (With proofs, of course.)
  5. Prove that the frame matroid G(Σ) of a signed graph Σ = (Γ, σ) is always regular. (Remember: the balanced circles are those with positive sign product.)
  6. Prove that R₁₀ = G(−K₅), the frame matroid of K₅ with all edges signed negative. Deduce from this that R₁₀ is regular.
  7. Let W_r be the r-spoke wheel graph. Show that the whirl W^r = G(W_r, ∅) = L(W_r, ∅), the frame and(!) lift matroid of the contrabalanced wheel graph. (This is the bicircular matroid of the wheel. ∅ denotes the empty set, in case your browser has trouble with it.)
  8. Show that the bicircular matroid of any graph Γ equals G(Γ, ∅).

• 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 M_i to be
     M | (X_i ∪ C) / (C \ X_i \ p_i)
     with p_i replaced by a point p not in E(M), where C is a circuit that is not contained in either X₁ or X₂ and p_i is a point in C \ X_i.
     1. Show that this definition of M_i 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. I think what might better be 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=M₀, M₁, ..., M_k (with some k ≥ 0) such that each M_i = M_i-1 \ e_i or M_i-1 / e_i , all M_i are 3-connected, and M_k 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.

• Problems on characteristic and Tutte polynomials.
  • The characteristic polynomial p_M(λ) := Sum_{S ⊆ E} (−1)^|S| λ^r(M)−r(S).
  • The corank-nullity (or rank generating) polynomial R_M(u, v) := Sum_{S ⊆ E} u^|S|-r(S) v^r(M)−r(S).
  • The Tutte polynomial can be defined (though this is not the best definition) as T_M(x, y) := R_M(x−1, v−1).
  1. Prove that each of these polynomials, as a function of matroids, satisfies f(M) = f(M\e) + α f(M/e) for a suitable constant α (possibly different for different functions) 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 each polynomial on discrete matroids (where every element is a loop or coloop).
  3. How are these polynomials related to each other? (Easy, not a trick problem.)

• Problems on hyperplane arrangements.
  H denotes a hyperplane arrangement, affine or homogeneous, in Rⁿ. p_H(λ) is its characteristic polynomial.
  1. Show that in the matroid of a homogeneous hyperplane arrangement H, the rank function is r(S) = codim(intersection of S), for any S subset of H.
  2. The arrangement induced by H in h is
     H^h = { h' intersect h : h' in H and h' ≠ h}.
     Show that if h is in H, then M(H^h) = M(H)/h.
  3. A region is a connected component of Rⁿ − (union of H), and ρ(H) is the number of regions. Assume H is homogeneous.
     1. Show that ρ(H) = ρ(H−h) + ρ(H^h).
     2. Deduce that ρ(H) = |p_H(−1)|.