Guest post by James Oxley.
1. Introduction
It is well known that a graph is bipartite if and only if every cycle has an even number of edges and that a connected graph is Eulerian if and only if every vertex has even degree. While we cannot characterize arbitrary matroids in which every circuit has even cardinality, we can characterize binary matroids with this property. For reasons that will be clarified later, such a binary matroid is called affine. The goal of this note is to prove the following two theorems. The first is due to Jim Geelen and Peter Nelson, the second to Nathan Bowler. A circuit $C$ in a matroid is odd if $|C|$ is odd; otherwise $C$ is even.
Theorem 1.1 (Geelen and Nelson). Let $M$ be a loopless, connected, non-affine, binary matroid. If a largest odd circuit of $M$ has $k$ elements, then $M$ has no circuit of size exceeding $2k-2$.
Theorem 1.2 (Bowler). Let $n$ and $k$ be integers exceeding two where $k$ is odd. Then there is an integer $N(k,n)$ such that every $3$-connected, non-affine, binary matroid whose largest odd circuit has $k$ elements either has at most $N(k,n)$ elements or has a minor isomorphic to $M(K_{3,n})$.
Both of these theorems emerged two years ago from discussions following the author’s online seminar talk [7] based on the paper by Chun, Oxley, and Wetzler [2]. The proofs of these theorems were emailed to the author by Jim Geelen and Nathan Bowler. The matroid terminology used here will follow [6].
2. Background
Recall that the rank-$r$ binary projective geometry $PG(r-1,2)$ is the matroid whose elements are the non-zero vectors of $V(r,2)$, the $r$-dimensional vector space over the two-element field, and whose independent sets are the linearly independent subsets of $V(r,2)$. For example, the matroids $PG(0,2)$, $PG(1,2)$, and $PG(2,2)$ are $U_{1,1}$, $U_{2,3}$, and the Fano matroid. Of course, every simple binary matroid of rank $r$ is isomorphic to a restriction of $PG(r-1,2)$. The rank-$r$ binary affine geometry $AG(r-1,2)$ is the matroid that is obtained from $PG(r-1,2)$ by deleting one of its hyperplanes. Thus $AG(0,2)$, $AG(1,2)$, and $AG(2,2)$ are $U_{1,1}$, $U_{2,2}$, and $U_{3,4}$. Clearly, $AG(r-1,2)$ is the matroid that is obtained from $V(r,2)$ by deleting a $V(r-1,2)$. The symmetry of $V(r,2)$ means that it does not matter which hyperplane we choose to delete. If we delete the hyperplane consisting of the vectors whose first coordinate is zero, then we see that the elements of $AG(r-1,2)$ are the vectors of $V(r,2)$ whose first coordinate is one. It follows that every circuit of $AG(r-1,2)$ is even. To see that a simple binary matroid $M$ having no odd circuits is a restriction of a binary affine geometry, we proceed as follows. Let $A$ be a binary matrix representing $M$. Adjoin a new row to $A$ consisting entirely of ones to get the matrix $A^+$. Then one easily checks that $M[A] = M[A^+]$. Clearly $M[A^+]$ is a restriction of a binary affine geometry.
Adding elements in parallel to existing elements of a simple binary affine matroid yields another binary matroid in which every circuit is even. We deduce that a binary matroid is affine if and only if it has no loops and its simplification is isomorphic to a restriction of a binary affine geometry. The next theorem, which incorporates this observation, is obtained by combining results of Brylawski [1], Heron [4], and Welsh [8]. A proof of the equivalence of i and ii was outlined above. A proof of the equivalence of i and iii may be found in [6, Proposition 9.4.1]. This equivalence, originally shown by Welsh, generalizes to binary matroids the dual relationship between bipartite and Eulerian graphs.
Theorem 2.1. The following are equivalent for a non-empty binary matroid $M$.
- Every circuit of $M$ is even.
- $M$ is loopless and its simplification is isomorphic to a restriction of a binary affine geometry.
- $E(M)$ can be partitioned into cocircuits.
3. Proofs and Consequences
This section presents the proofs of the two main theorems. The proof of Theorem 1.1 will use the next two lemmas. A theta-graph is a graph $G$ consisting of two vertices, $u$ and $v$, and three internally disjoint paths joining them. These three $uv$-paths in $G$ are the series classes of the theta-graph.
Lemma 3.1. In a connected binary matroid $M$ with an element $e$ and an odd circuit $C$, either $E(M) = C$, or $M$ has as a restriction the cycle matroid of a theta-graph that contains the element $e$ and has $C$ as the union of two of its series classes. In particular, $M$ has an odd circuit containing $e$.
Proof. We may assume that $E(M) \neq C$. Let $d$ be an element of $E(M) – C$, and let $D$ be a circuit that contains $d$ and meets $C$ such that $D – C$ is minimal. As $M$ is binary, $C \bigtriangleup D$ is a disjoint union of circuits. The minimality of $D- C$ implies that $C \bigtriangleup D$ is a circuit, so $M|(C \cup D)$ is the cycle matroid of a theta-graph in which $C$ is the union of two of the series classes. To ensure that $e \in C \cup D$, we take $e = d$ when $e \notin C$. Because the series classes in $M|(C \cup D)$ do not all have even cardinality, it follows that $e$ is in an odd circuit of $M$.
Lemma 3.2. Let $M$ be a connected, non-affine binary matroid. If $M|X$ is connected and affine having at least two elements, then $M$ has an odd circuit $D$ that meets both $X$ and $E(M) – X$ for which $D-X$ is a circuit of $M/X$. Moreover, if $X$ is a circuit, then $M|(X\cup D)$ is the cycle matroid of a theta-graph in which exactly two of the series classes have the same parity.
Proof. As $M$ is not affine, it has an odd circuit $C$. Thus, by Lemma 3.1, $M$ has an odd circuit containing $e$. Hence we can take an odd circuit $D$ that meets $X$ for which $D – X$ is minimal. Suppose that $D -X$ is not a circuit of $M/X$. Then $M/X$ has a circuit $D_1$ that is properly contained in $D -X$. Thus $M$ has a circuit $D_2$ that meets $D-X$ in $D_1$ and is contained in $D_1 \cup X$. The choice of $D$ implies that $D_2$ is even. Now $D \bigtriangleup D_2$ is a disjoint union of circuits of $M$. As $|D \bigtriangleup D_2|$ is odd, $D \bigtriangleup D_2$ contains an odd circuit. This odd circuit cannot be contained in $X$, nor does it contain $D-X$. Hence it contradicts the choice of $D$. Thus $D -X$ is a circuit of $M/X$. It follows immediately that if $X$ is a circuit, then $M|(X\cup D)$ is the cycle matroid of a theta-graph. As each of $D$ and $X$ is the union of exactly two of the series classes in this theta-graph, and $|D|$ and $|X|$ have different parities, it follows that exactly two of the series classes in $M|(X\cup D)$ have the same parity.
Proof of Theorem 1.1. Let $C$ be a largest circuit of $M$. We may assume that $C$ is even. By Lemma 3.2, $M$ has an odd circuit $D$ that meets $C$ such that $M|(C\cup D)$ is the cycle matroid of a theta-graph. Let the series classes of the theta-graph be $S_1$, $S_2$, and $S_3$ where the first two have the same parity. Then $C = S_1 \cup S_2$.
Suppose that each of $|S_1 \cup S_3|$ and $|S_2 \cup S_3|$ is at most $\tfrac{1}{2}|C|$. Then $|S_1| + |S_2| + 2|S_3| \le |S_1| + |S_2|$. Thus $S_3$ is empty, a contradiction. Hence $|S_1 \cup S_3|$ or $|S_2 \cup S_3|$ exceeds $\tfrac{1}{2}|C|$, and the theorem follows.
A theta-graph with two series classes each having $k – 1$ elements and one having exactly one element shows that the bound in Theorem 1.1 is sharp. Another immediate consequence of Lemma 3.2 is the following.
Corollary 3.3. Every even circuit in a connected, non-affine, binary matroid is the symmetric difference of two odd circuits.
In a connected matroid $M$ with at least two elements, the sizes of a largest circuit and a largest cocircuit are the circumference $c(M)$ and the cocircumference $c^*(M)$, respectively. When $M$ has an odd circuit, we denote the size of a largest odd circuit by $c_o(M)$; when $M^*$ has an odd circuit, we write $c^*_o(M)$ for $c_o(M^*)$.
Corollary 3.4. Let $M$ be a connected binary matroid having an odd circuit and an odd cocircuit. Then
$$|E(M)| \le 2(c_o(M) – 1)(c^*_o(M) – 1).$$
Proof. By a result of Lemos and Oxley [5], $|E(K)| \le \tfrac{1}{2}c(K)c^*(K)$ for all connected matroids $K$. Combining this with Theorem 1.1 gives the result.
In the next proof, $M({\mathcal W}_m)$ denotes the cycle matroid of a rank-$m$ wheel, while a tipless binary spike of rank $m$ is the vector matroid of the binary matrix $[I_m|I_m^c]$ where $I_m^c$ is the $m \times m$ matrix that is obtained from $I_m$ by replacing each entry by the other element in the two-element field.
Proof of Theorem 1.2. Let $m = \max\{n, 2k -1\}$. By a theorem of Ding, Oporowski, Oxley, and Vertigan [3], there is a number $N(m)$ such that every $3$-connected binary matroid having more than $N(m)$ elements has as a minor one of $M({\mathcal W}_m)$, $M(K_{3,m})$, $M^*(K_{3,m})$, or a tipless binary spike of rank $m$. If $M$ is a non-affine such matroid and its largest odd circuit has $k$ elements, then, by Theorem 1.1, its largest circuit has at most $2k-2$ elements. Each of $M({\mathcal W}_m)$, $M^*(K_{3,m})$, and the tipless binary spike of rank $m$ has an $m$-element circuit, so none of these matroids occurs as a minor of $M$. Hence $M$ has a minor isomorphic to $M(K_{3,m})$. Taking $N(k,n)$ to be $N(m)$, we get the theorem.
Corollary 3.5. For every odd integer $k$ exceeding two, there is an integer $N'(k)$ such that every $3$-connected, non-Eulerian, simple graph whose largest odd bond has $k$ edges has at most $N'(k)$ edges.
Bibliography
[1] T.H. Brylawski, A decomposition of combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235-282.
[2] C. Chun, J. Oxley, K. Wetzler, The binary matroids with no odd circuits of size exceeding five, J. Combin. Theory Ser. B 152 (2022), 80-120.
[3] G. Ding, B. Oporowski, J. Oxley, and D. Vertigan, Unavoidable minors of large $3$-connected binary matroids, J. Combin. Theory Ser. B 66 (1996), 334-360.
[4] A.P. Heron, Some topics in matroid theory, D.Phil. thesis, University of Oxford, 1972.
[5] M. Lemos and J. Oxley, A sharp bound on the size of a connected matroid, Trans. Amer. Math. Soc. 353 (2001), 4039-4056.
[6] J. Oxley, Matroid Theory, Second edition, Oxford University Press, New York, 2011.
[7] J. Oxley, The binary matroids with no odd circuits of size exceeding five, Graphs and Matroids Online Seminar, University of Waterloo, April 17, 2020.
[8] D.J.A. Welsh, Euler and bipartite matroids, J. Combin.Theory 6 (1969), 313-316.