5
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ Could you explain the comment about cycles? What do you mean by "the base for all cycles"? Thank you. @IlyaBogdanov $\endgroup$ – G Philip Oct 12 '17 at 11:54
  • $\begingroup$ I added the condition that the matroids are simple, otherwise, $c_n$ is infinite. $\endgroup$ – Tony Huynh Oct 12 '17 at 12:40
  • $\begingroup$ The (binary) cycle space of a graph is the $\mathbb{F}_2$ kernel of the vertex-edge incidence matrix of a graph. See here for more: en.wikipedia.org/wiki/Cycle_space $\endgroup$ – Aaron Dall Oct 12 '17 at 13:27
4
$\begingroup$

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)}}. $$

$\endgroup$
  • $\begingroup$ Thank you for this analysis. Upon reading a bit further, it seems that I am looking for the number of non-2-isomorphic graphs on $n$ vertices. This is a consequence of Whitney's 2-isomorphism theorem for graphs. $\endgroup$ – G Philip Oct 13 '17 at 3:58
  • 1
    $\begingroup$ I think that for asymptotic purposes all graphs are 3-connected so the count for non-isomorphic graphs will be the same as non-2-isomorphic graphs. $\endgroup$ – Gordon Royle Oct 13 '17 at 12:39
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.