The asymptotic enumeration conjecture for representable matroids

From papers

Let MM be a matroid with ground set [n][n]. A nonbasis of a rank-rr matroid is an rr-element subset of [n][n] that is not a basis. For each integer nn, let δ(n){0,1}\delta(n)\in\{0,1\} be the remainder of nn on division by 22, and define

d(n)=(n21)(n21)=14(n2δ(n))n+1.d(n)=\left(\left\lfloor\frac n2\right\rfloor-1\right)\left(\left\lceil\frac n2\right\rceil-1\right)=\frac14(n^2-\delta(n))-n+1.

The asymptotic enumeration conjecture. Asymptotically almost all representable matroids on [n][n] have rank in {n/2,n/2}\{\lfloor n/2\rfloor,\lceil n/2\rceil\} and exactly d(n)1d(n)-1 nonbases. Asymptotically almost all matroids on [n][n] with rank in this set and exactly d(n)1d(n)-1 nonbases are representable. Furthermore, the number of representable matroids on [n][n] is

(1+δ(n)+o(1))((nn/2)d(n)1).(1+\delta(n)+o(1))\binom{\binom{n}{\lfloor n/2\rfloor}}{d(n)-1}.

The theorem preceding this conjecture gives an upper bound of 2n3/42^{n^3/4} for the number of representable matroids, while the conjecture predicts the precise leading asymptotic through the extremal ranks and nonbasis count. The claim remains open in the supplied source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Peter Nelson, “Almost all matroids are non-representable”, arXiv:1605.04288 (2017).

Solutions 0

No solutions have been posted yet.