What upper bounds are known on the number of non-isomorphic cycle matroids?

Question

For $n\in\mathbb{N}^{+}$, let $c_{n}$ denote the number of simple non-isomorphic cycle matroids of graphs on $n$ vertices. That is, let

$$A(n)=\{M(G)\;;\;G\text{ is a graph on }n\text{ vertices}\},$$

and let $B(n)$ be a largest subset of $A(n)$ such that no two elements of $B(n)$ are isomorphic (as matroids). Then

$$c_{n}\equiv|B(n)|.$$

(Here $M(G)$ denotes the cycle matroid of graph $G$. )

A simple upper bound for $c_{n}$ would be something like $2^{2^{\binom{n}{2}}}$, since the ground set of the cycle matroid of a graph on $n$ vertices is of size at most $\binom{n}{2}$.

Are there any better upper bounds known for $c_{n}$?

---

Edit: It looks like I am asking for the number of non-$2$-isomorphic graphs on $n$ vertices. Whitney's 2-isomorphism theorem (version of Oxley's Matroid Theory) states: "Let $G$ and $H$ be graphs having no isolated vertices. Then $M(G)$ and $M(H)$ are isomorphic if and only if $G$ and $H$ are $2$-isomorphic."

Intuitively, this number looks like it should be significantly smaller than the number of non-isomorphic graphs on $n$ vertices, since non-isomorphic graphs can be $2$-isomorphic.

Do we know of upper bounds on the number of non-$2$-isomorphic graphs on $n$ vertices? (Should I ask this as a separate question?)

Answer 1

It seems now that the question really boins down to the number of non-isomorphic graphs on $n$ vertices. Denote this number by $f(n)$. Clearly, $$ 2^{n\choose 2}\geq f(n)\geq \frac{2^{n\choose 2}}{n!}=\frac{2^{n\choose 2}}{n^{O(n)}}, $$ these two numbers being sufficiently close on the logarithic scale. (Moreover, one may sharpen the upper bound by applying Burnside's formula and investigating the number of fixed points of any permutation of vertices).

As Tony Huynh mentioned, $c_n\leq f(n)$. Let us now construct a large family of graphs with a few isomorphisms between their cycle matroids.

Let $n$ be odd. Take any graph $H$ on $n-1$ vertices. Add the $n$th vertex $v$ connected to all of them to obtain a graph $G$; non-isomorphic $H$ clearly provide non-isomorphic $G$.

In the cycle matroid $M(G)$ there exists a set $S$ of $n-1$ edges (incident to $v$) such that

$(*)$ every edge not from $S$ forms a circuit (=minimal non-independent set) with two edges from $S$.

Consider any other graph $G'$ (obtained in the described manner) with $M(G')\cong M(G)$; if $S$ corresponds in $G'$ to $n-1$ edges sharing a vertex $v'$, then $G'\cong G$ (every edge not from $S$ connects the other vertices of the two edges from $S$ forming a circuit with it). Thus, the number of such graphs $G'$ is at most the number of sets $S'$ in $M(G)$ satisfying $(*)$. We are now to bound this number from above.

Assume that $S'$ contains edges $e_1,\dots,e_k\in S$, and the other edges are not from $S$. Any $e\in S\setminus S'$ should be complemented in $S'$ to a 3-circuit --- by one of the $e_i$ and some other edge. One of the $e_i$ may be chosen in at most $k$ ways, the other one is then found uniquely, and these `other' edges are distinct for distinct $e$. Thus the number of sets $S'$ satisfying $(*)$ is at most $k^{n-k}=n^{O(n)}$, hence we get at least $f(n-1)/n^{O(n)}$ pairwise non-isomorphic cycle matroids.

To summarize, $$ 2^{n\choose 2}\geq f(n)\geq c_n\geq \frac{f(n-1)}{n^{O(n)}}\geq \frac{2^{n\choose 2}}{n^{O(n)}}. $$

Answer 2

There are $2^{\binom{n}{2}}$ labelled graphs on $n$ vertices. Since isomorphic graphs have isomorphic graphic matroids, $c_n$ is at most the number of non-isomorphic graphs on $n$ vertices (see OEIS A000088). In particular, $c_n$ is at most $2^{\binom{n}{2}}$.

I would be remiss not to mention that Peter Nelson recently proved that the number of representable matroids is also small. Note that graphic matroids are representable over every field.

Theorem. For all $n \geq 10$, the number of representable matroids on ground set $[n]$ is at most $2^{2n^3}$.

See this post on the Matroid Union Blog for a proof. This paper of Nelson is written with the bounds as tight as possible, but the proof on the Matroid Union Blog post is slightly easier to follow.