2
$\begingroup$

How many simple binary matroids are there, up to isomorphism, of rank $r$ on an $n$-element ground set, where $r \le n < 2^r$? Write this number as $a_r(n)$. Is there somewhere where I can get this enumeration for small $r$ and small $n$? At the risk of asking two questions in one post, I am also interested in asymptomic results for $a_r(n)$ for $r$ large.

I am aware of Marcel Wild's asymptotics for the number $b(n)$ (A076766) of binary matroids, up to isomorphism, on an $n$-element ground set: $$b(n) \sim \frac{1}{n!}(\text{number of $\mathbb{F}_2$-linear subspaces of } {\mathbb{F}_2}^n).$$ Hence $b(n) = \Theta(2^{n^2/4})$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

You can compute these numbers for small $n$ and $r$ using Pólya's Enumeration Theorem (which is just a specific application of the orbit-stabiliser theorem).

A simple binary matroid of rank at most $r$ is simply a subset of the projective space $\mathrm{PG}(r-1,2)$ and isomorphism of binary matroids is precisely equivalence under the action of the group $G = \mathrm{PGL}(r,2)$.

Given the group you can calculate its cycle index polynomial which is a multivariate polynomial in variables $X_1$, $X_2$, $X_3$, $\ldots$ $$ Z(G;X_1, X_2, \ldots) := \frac{1}{|G|} \sum_{g \in G} \prod X_k^{n_k(g)}. $$ where $n_k(g)$ is the number of cycles of length $k$ in the group element $g$.

Although this is defined as a sum over individual group elements, the expression is constant on conjugacy classes so all you need is something able to compute conjugacy classes.

Once you have this expression, you substitute $1+x^k$ for each variable $X_k$ and you end up with the generating function for the number of simple binary matroids of rank at most $r$.

If we do this for rank $r=4$ then we end up with $$ x^{15}+x^{14}+x^{13}+2x^{12}+{\color{red}3x^{11}}+4x^{10}+5x^9 \\ +6 x^8+6x^7+5x^6+4x^5+3x^4+2x^3+x^2+x+1 $$ meaning that there are, for example, $3$ simple binary matroids of rank at most $4$ and size $11$.

How do you get the cycle index polynomial?

You can do it in GAP "by hand" using ConjugacyClasses, but if you are fortunate enough to have a subscription to Magma, you can use the entirely undocumented function CycleIndexPolynomial.

> g := PGammaL(4,2);
> cp := CycleIndexPolynomial(g);
> cp;
1/20160*x[1]^15 + 1/192*x[1]^7*x[2]^4 + 1/96*x[1]^3*x[2]^6 + 
1/16*x[1]^3*x[2]^2*x[4]^2 + 1/18*x[1]^3*x[3]^4 + 
1/6*x[1]*x[2]*x[3]^2*x[6] + 1/8*x[1]*x[2]*x[4]^3 + 
2/7*x[1]*x[7]^2 + 1/180*x[3]^5 + 1/12*x[3]*x[6]^2 + 
1/15*x[5]^3 + 2/15*x[15]

Here, Magma is using x[5] for the variable $X_5$ and so on, and so you then have to substitute $1+x^5$ for $X_5$ and so on.

Here are the numbers of simple binary matroids of rank up to $6$ --- the size goes from 0 to 63 and it is reassuringly symmetric about the middle.

$$ \begin{array}{|rr|rr|rr|rr|} 0&1&16&29236&32&46875728&48&11780\\ 1&1&17&70729&33&44065939&49&4708\\ 2&1&18&164818&34&38939167&50&1907\\ 3&2&19&366180&35&32339616&51&791\\ 4&3&20&770299&36&25238329&52&340\\ 5&5&21&1528238&37&18504126&53&155\\ 6&10&22&2852575&38&12742321&54&72\\ 7&19&23&5002828&39&8239590&55&35\\ 8&35&24&8239590&40&5002828&56&19\\ 9&72&25&12742321&41&2852575&57&10\\ 10&155&26&18504126&42&1528238&58&5\\ 11&340&27&25238329&43&770299&59&3\\ 12&791&28&32339616&44&366180&60&2\\ 13&1907&29&38939167&45&164818&61&1\\ 14&4708&30&44065939&46&70729&62&1\\ 15&11780&31&46875728&47&29236&63&1\\ \end{array} $$

Improve this answer
$\endgroup$
6
  • $\begingroup$ thank you, Professor Royle for your answer. Thanks for sharing the details. $\endgroup$
    – Colin Tan
    Commented Sep 20 at 4:54
  • $\begingroup$ Is there a difference between the group action of $PGL(r, 2)$ on $PG(r-1,2)$ versus the group action of $GL(r,2)$ on ${\mathbb{F}_2}^r \setminus \{0\}$, the nonzero points of $r$-dimensional affine space over ${\mathbb{F}_2}$? Because the base field has only 2 elements, the equivalence classes in $PGL(r, 2) = GL(r,2)/{\mathbb{F}_2}*$ and $PG(r - 1, 2) = {\mathbb{F}_2}^r \setminus \{0\}/\sim$ consist only of one element each. $\endgroup$
    – Colin Tan
    Commented Oct 11 at 7:00
  • $\begingroup$ @Colin Tan There is no difference in this case. $\endgroup$
    – Gordon Royle
    Commented Oct 11 at 9:37
  • $\begingroup$ why in your code did you use "PGammaL" instead of "PGL"? Here $PGL$ stands for *projective linear group", right? $\endgroup$
    – Colin Tan
    Commented Oct 14 at 3:30
  • $\begingroup$ If q is prime, then PGammaL(n,q) and PGL(n,q) are the same thing and so it is irrelevant which you use. If q is not prime then, depending on the application, you might want either PGL or PGammaL. The code you see above is some old code of mine that used PGammaL because at the time I was working with q=4. To write my answer I just took my old code and replaced "4" with "2" because you were interested in binary matroids. There was no need for me to change PGammaL to PGL because they are the same when q=2. $\endgroup$
    – Gordon Royle
    Commented Oct 14 at 7:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .