Open problems in matroid theory

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.

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.