Week 3: Chapter 6(b): Representability

Starting from Rota’s Conjecture

We start from pg 196, Theorem 6.5.9

• Rota’s conjecture: For all prime powers q, the set of excluded minors for GF(q)-representability is finite.
• We use spikes (following Geelen and Whittle) to ask what happens when the converse of Rota’s conjecture holds.
• Lemma 6.5.13: Let r be an integer exceeding three and F be a field. Let M be a rank-r spike with legs {t, x_1, y_1}, {t, x_2, y_2}, {t, x_2, y_r} and let N = M \ t. Then M is F-representable iff N is F-representable.
• Note that this does not hold if r = 3. For example, if t is an element of the spike, F_7, then we may view t as the tip of the spike. Deleting it gives a matroid isomorphic to M(K_4). Thus, F_7 \ t is representable over every field whereas F_7 is representable only over fields of characteristic two.
• If r \geq 4 and N is an F-representable rank-r tipless spike with legs {x_1, y_1}, {x_2, y_2}, …, {x_r, y_r} s.t. {x_1, x_2, …, x_r} is independent, then every F-representation of N is projectively equivalent to a matrix of the form [I_r|A_r] whose columns are labelled, in order x_1, x_2, …, x_r, y_1, y_2, …y_r.
• Let F be a field. If F is infinite, the set of excluded minors for F-representability contains infinitely many tipless spikes.
• N-arc: a set S of points of PG(r - 1, q) s.t. PG(r - 1, q) | S \cong U_{r,n}. (See Hirschfeld 1997 and Segre 1955).
• MDS: maximum distance separable.
• Prop 6.5.23: Let M be a matroid and F be a field. A necessary and sufficient condition for M to be F-representable is that, for all hyperplanes H of M, there is a function f_H : E(M) \rightarrow F s.t.:
  • H = {x \in E(M) : f_H(x) = 0}
  • If H_1, H_2 and H_3 are distinct hyperplanes of M for which the rank of H_1 \cap H_2 \cap H_3 is r(M) - 2, then there are non-zero elements c_1, c_2, c_3 of F s.t. c_1f_{H1} + c_2f{H2} + c_3f{H3} = 0.
• For a matroid M:
  • M is regular
  • M is representable over every field
  • M is binary and, for some field F of characteristic other than two, M is F-representable.
• A matroid is regular iff it has no minor isomorphic to any of the matroids U_{2,4}, F_7 and F^{*}_{7}.
• A matroid is co-graphic iff it has no minor isomorphic to any of the matroids U_{2,4}, F_7, F^{*}_{7}, M(K_5), M(K_{3,3})
• Algebraic Matroids! How does algebraic dependence relate to a specific class of matroids? (Van der Waerden (1937), Mac Lane (1938); is he the Category Theory dude?)
• Let {t_1, t_2,…t_n} be a subset of K, and extension field of F. Then F(t_1, t_2, …,t_n) denotes the subfield of K generated by {t_1, t_2, …, t_n}, that is, F(t_1, t_2, …,t_n) consists of all elements of the form h(t_1, t_2, …, t_n) / k(t_1, t_2, …, t_n) where h and k are in the F[x_1, x_2, …, x_n]. An element of K is algebraically dependent on {t_1, t_2, …, t_n} over F if s is algebraic over F(t_1, t_2, …, t_n). The latter occurs iff s is a root of an equation of the form a_0(t_1, t_2,…., t_n)x^{m} + a_1(t_1, t_2, …,t_n)x^{m-1} + … + a_m(t_1, t_2, …, t_n) = 0, where each a_i(t_1, t_2, …t_n) is a polynomial in t_1, t_2, …, t_n with coefficients in F, and at least one of these polynomials is non-zero.
• A finite subset T of K is algebraically dependent over F if, for some t in T, the element t is algebraically dependent on T - t. If T is not algebraically dependent over F, it is called algebraically independent over F.
• Let M be an arbitrary matroid and let (E, I) such that there is a map \varphi from E(M) into E s.t. for all subsets T of E(M), the set T is independent in M iff |\varphi(T)| = |T| and \varphi(T) is independent of (E, I). Then the matroid M is said to be algebraic over F or algebraically representable over F, and the map \varphi is called an algebraic representation of M over F.
• Goes over independent transcendentals over F, as they relate to polynomial rings and the quotient fields F(t_1, t_2, …t_n) and F(x_1, x_2,…x_n).
• The characteristic set K(M) of M is the set {k:M is representable over some field of characteristic k}.
• Gröbner basis hype! (6.8.10)
• We rely on the theory of Gröbner bases to prove that there is a finite algorithm for determining whether 1 \in I (we use this to show that M is representable iff 1 \notin I by supposing 1 \in I).
• Let K be a field and L be its algebraic closure. Let I be an ideal in K[x_1, x_2, …, x_n]. Then there are elements a_1, a_2, …, a_n of L s.t. f(a_1, a_2, …, a_n) = 0 for all f in I iff I \neq K[x_1, x_2, …, x_n].
• Let X and Y be flats in a matroid M. Then (X, Y) is a modular pair of flats if r(X) + r(Y) = r(X \cup Y) + r(X \cap Y).
• Modularity is a property of flats, so it is basically a lattice property. A matroid M is modular if, for every connected component N of M, the simple matroid associated with N is either a free matroid or a finite projective geometry (see Birkhoff 1967 for proof).
• A flat Y in a matroid M is a complement of a flat X if X \cap Y = cl(\emptyset) and cl(X \cup Y) = E(M).
• For a flat X in a matroid M:
  • M is modular
  • r(X) + r(Y) = r(X \cup Y) for all flats Y that meet M in cl(\emptyset)
  • r(X) + r(Y) = r(M) for all complements Y of X.
• Modular short-circuit axiom and strong circuit elimination (covered by Federico)
• Dowling Geometries: important in matroid theory because they are linked to projective geometries and free matroids (Kahn and Kung (1982).
• Cycles vs unbalanced cycles: a cycle is unbalanced if it has a single edge, or if it has at least two edges but is not balanced.
• Bias or frame matroid; the class of bias matroids is minor-closed.
• They talk about signed graphs, which we covered in Spectral (well, rather unsigned graphs)
• Grain graphs, voltage-graphic matroids.
• The variety of matchstick geometries of order n is the set of all restrictions of the matroids M_r(n) where r and n are positive integers and M_1(n) = U_{1,1} wile, for all k \geq 1, the matroid M_{2k}(n) is the direct sum of k copies of U_{2, n+1}; and M_{2k+1}(n) is the direct sum of M_{2k}(n) and U_{1,1}.

Notes

• The chapter has a couple examples of non-algebraic matroids (as in, diagrams), which was helpful to see. Some of this felt a bit Algebra III to IV-ish. Ah. Definitely, by the time we got to using Gröbner bases to prove our theorem of representability, I felt like I was in Taylor’s class!
• I would definitely like to go over this section (ie. Algebraic matroids, specifically on Dowling geometries), as there is a lot packed in. I might just also pick a paper or two that talks a bit more about Dowling geometries and read a bit of that on my own. (example link due to Zaslavsky. The Hirschfeld paper was referred to “as the survey paper” in this chapter.
• Lemon (1988) noted that one can use one of Lindström’s (1987) classes of non-algebraic matroids or another class of matroids considered by Gordon (1984) to show that for every field F, the set of excluded minors for algebraic representability is infinite.
• I also added the two papers I didn’t get to yesterday to today’s readings, as I should be able to get to them today. Today was a solid day. I ended up watching a British mystery murder with my parents and then my dad picked this hilarious movie that literally grossed US $4000 at the box office and was pretty terrible, but in a hilarious way. I haven’t seen those types of movies in a long time. I’m really going to miss hanging out with them daily; they’re really the best! We also walked again early in the morning; it’s really quite chill seeing your neighbours doing walks early in the morning and the people here say good morning and everything. My mom has already asked me to start making a list of all the things I want to eat when I head back.

Readings

• On Dowling Geometries, it looks like the papers to read are:
  • Dowling, T.A., “A class of Geometric lattices based on finite groups” (1973)
  • Zaslavsky T., “Associativity in multary quasigroups: The way of biased expansions (2012)
• Hirschfeld J.W.P, (1997), “Complete Arcs”: link
• Martí-Farré, J., Padró, C., “On Secret Sharing Schemes, Matroids and Polymatroids” (2007). link
• Hochstättler W. And Kromberg S., “A Pseduoconfiguration of Points without Adjoint” (1995): link