Open problems in matroid theory

Question

I read Oxley's book on matroid theory and found the theory fascinating. At the end, Oxley stated some open problems and conjectures in matroid theory.

1. Are there any modern lists about such problems?

2. Are there more open conjectures in matroid theory?

Answer 1

Stanley has a famous conjecture from his paper Cohen-Macaulay complexes that the $h$-vector of (the independence complex of) a matroid is a pure $O$-sequence (i.e., the $f$-vector of a pure multicomplex). Many special cases of this conjecture are known, but it remains open in general.

Answer 2

Let $G$ be a finite permutation group acting on a finite set $\Omega$. We say that a finite sequence of points $(x_1, x_2, \dots, x_n)$ with $x_i \in \Omega$ is a base for $G$ if the only element of $G$ which fixes all points in the sequence is the identity $1 \in G$. We say that a base is irredundant if no $x_i$ is fixed by the stabiliser of $\{ x_1, x_2, \dots, x_{i-1} \}$. For example, irredundant bases arise when using the Orbit-Stabiliser theorem to find the order of the automorphism of a graph (first pick a vertex $x_1$, then pick a vertex $x_2$ which is not in the orbit of $x_1$, etc.).

Bases in this sense act much like bases for vector spaces, as any element $g \in G$ is uniquely determined by the sequence $(x_1^g, x_2^g, \dots,x_n^g)$. Unfortunately, it is not true in general that all irredundant bases of a permutation group have the same size.

But there is a special class of permutation groups for which this is true! These are known as IBIS groups. In fact, this condition is equivalent to having the irredundant bases form a basis of a matroid. The name IBIS is an initialism for "Irredundant Bases of Invariant Size".

There are many examples; the symmetric group $S_n$ with its natural action is perhaps the easiest. The cyclic group $C_n$ acting on the $n$-cycle gives rise to the matroid $U_{n,1}$. More interestingly, both $M_{12}$ and $M_{24}$ are IBIS groups. The matroid obtained from (the irredundant bases of) the former is $U_{12,5}$, whereas the matroid obtained from of the latter is quite mysterious.

The following problems, finally, are really wide open, especially (2):

1. Which matroids arise as the matroids of (the irredundant bases of) IBIS groups?
2. Which permutation groups are IBIS groups?

Really the only far-reaching result along the lines of answering either of these questions is a result completely characterising the groups which give rise to a uniform matroid $U_{n,k}$.

These problems, as well as IBIS groups, are due to Peter Cameron, and I learned of it as part of his course on Combinatorics at St Andrews; his lecture notes for this course, which includes far more details, can be found on his blog. For even more in-depth material, see these notes.