# Friday January 6th

## 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

Written on January 6, 2023