4
$\begingroup$

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.

Since this can be be phrased only in terms of circuits and matroid properties (when the graph is connected, we can recover $n$ as the rank of the matroid plus one), I was wondering is this result could be extended to any matroid. More precisey, is it true that, for any matroid of size $m$, rank $r$ and odd genus $g$, the number of circuits of size $g$ is at most $\frac{(r+1)(m-r)}{g}$?

If no, are there some weaker similar bounds on the number of circuits of size $g$?

If yes, what can we say about the equality case? In the case of graphs, it is reached for the Moore graphs. Are there new non-graphical matroids reaching the equality?

New contributor
Antoine Labelle is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 1
    $\begingroup$ If you leave the world of graphical matroids, no such small bound can hold. The number of shortest circuits in a uniform matroid $U_{m,r}$ is $\binom{m}{r+1}$. $\endgroup$ – Gjergji Zaimi 2 days ago
  • $\begingroup$ Oh, you're right... I was hoping that this bound could have given some matroid theoritic version of Moore graphs, but this probably can't work $\endgroup$ – Antoine Labelle 2 days ago

Your Answer

Antoine Labelle is a new contributor. Be nice, and check out our Code of Conduct.

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

Browse other questions tagged or ask your own question.