Determining a Binary Matroid from its Small Circuits

  • James Oxley
  • Charles Semple
  • Geoff Whittle
Keywords: Binary matroids, Circuit-hyperplane relaxations

Abstract

It is well known that a rank-$r$ matroid $M$ is uniquely determined by its circuits of size at most $r$. This paper proves that if $M$ is binary and $r\ge 3$, then $M$ is uniquely determined by its circuits of size at most $r-1$ unless $M$ is a binary spike or a special restriction thereof. In the exceptional cases, $M$ is determined up to isomorphism.
Published
2016-02-05
Article Number
P1.26