NON-SEPARATING COCIRCUITS IN BINARY MATROIDS

MANOEL LEMOS

Abstract. In this note, we show that a 3-connected binary matroid M has at least r(M) − 1 non-separating cocircuits avoiding a fixed element. As a consequence of this result, we get a lower bound for the number of non-separating cocircuits of a simple and a cosimple connected binary matroid that generalizes the bound obtained by McNulty and Wu.

We say that a cocircuit C^{∗} of a matroid M is non-separating when M\C^{∗} is connected. We denote the set of non-separating cocircuits of a matroid M by R^{∗}(M). Note that a cocircuit of a matroid M is non-separating if and only if its complement is a connected hyperplane of M. For a connected graphic matroid, a non-separating cocircuit corresponds to the star of a vertex whose deletion from the associated graph keeps it 2-connected. Non-separating circuits and cocircuits play an important role in studying the structure of graphic matroids (see [7, 8, 17, 18]). There has been much interest in the study of non-separating circuits and cocircuits in graphs and matroids lately (see [1, 3, 4, 5, 6, 8, 10, 11, 16, 17, 18]).

For matroid notation and terminology, we follow Oxley[14]. For definitions related to chains and fans, we use Oxley and Wu[15]. Kelmans[6] and, independently, Seymour (see [13]) proved that every simple and cosimple connected binary matroid has a non-separating cocircuit, that is, Theorem 1. If M is a simple and cosimple connected binary matroid, then

|R^{∗}(M)| ≥ 1.

Bixby and Cunningham[1] showed implicitly that a 3-connected binary matroid has a lot of non-separating cocircuits, namely: Theorem 2. If M is a 3-connected binary matroid such that r(M) ≥ 3, then

|R^{∗}(M)| ≥ r(M) + 1.

Next, McNulty and Wu[12] improved the bound on the number of non-separating cocircuits for simple and cosimple connected binary matroids gave on Theorem 1: Theorem 3. If M is a simple and cosimple connected binary matroid, then

|R^{∗}(M)| ≥ 4.

This bound also is the best possible: McNulty and Wu gave an infinite family of extremal examples. Note that there is a large gap between Bixby and Cunningham’s bound on the number of non-separating cocircuits for 3-connected binary matroids and McNulty and Wu’s bound for simple and cosimple connected binary matroids.

1991 Mathematics Subject Classification. 05B35.

Key words and phrases. binary matroid, cocircuit, connected hyperplane, hyperplane, matroid, non-separating cocircuit.

The author is partially supported by CNPq under grants number 522910/96-3, 476097/01-0 and 664107/97-4 (ProNEx 107/97).

In this note, we obtain a bound that is close to the bound presented in Theorem 2, in some sense, and generalize the bound given by Theorem 3. The main result of this note is the following: Theorem 4. If M is a 3-connected binary matroid and a ∈ E(M), then there is at least r(M) − 1 non-separating cocircuits of M avoiding a.

Theorem 4 is the best possible, since any 3-connected graphic matroid M other than a loop has exactly r(M) − 1 cocircuits avoiding a fixed element.

An important tool used in this note is the following idea of decomposing a connected matroid M. Assume |E(M)| ≥ 3. A tree decomposition of M is a tree T with edges labelled e_{1}, e_{2}, …, e_{k−1} and vertices labelled by matroids M_{1}, M_{2}, …, M_{k} such that

(i) each M_{i} is 3-connected having at least four elements or is a circuit or cocircuit with at least three elements;

(ii) E(M_{1}) ∪ E(M_{2}) ∪ … ∪ E(M_{k}) = E(M) ∪ {e_{1}, e_{2}, …, e_{k−1}}; (iii) if the edge e_{i} joins the vertices M_{j_{1}} and M_{j_{2}}, then E(M_{j_{1}})∩E(M_{j_{2}}) = {e_{i}}; (iv) if no edge joins the vertices M_{j_{1}} and M_{j_{2}}, then E(M_{j_{1}}) ∩ E(M_{j_{i}}) is empty;

(v) M is the matroid that labels the single vertex of the tree T/e_{1}, e_{2}, …, e_{k−1} at the conclusion of the following process: contract the edges e_{1}, e_{2}, …, e_{k−1} of T one by one in order; when e_{i} is contracted, its ends are identified and the vertex formed by this identification is labelled by the 2-sum of the matroids that previously labelled the ends of e_{i}.

Cunningham and Edmonds [2] proved the following result. Theorem 5. Every connected matroid M has a tree decomposition T (M) in which no two adjacent vertices are both labelled by circuits or are both labelled by cocircuits. Furthermore, the tree T (M) is unique to within relabelling of its edges.

We shall call T (M) the canonical tree decomposition of M and let Λ_{2}^{u}(M) be the set of matroids that label vertices of T (M).

For a 3-connected binary matroid M and A ⊆ E(M), we define R_{A}^{∗}(M) to be the set of non-separating cocircuits of M avoiding A. When A = {a}, we use R_{a}^{∗}(M) instead of R_{A}^{∗}(M). Theorem 6. Suppose that M is a simple and cosimple connected binary matroid. If M is not 3-connected, then

R_{a_{1}}^{∗}(M_{1}) ∪ R_{a_{2}}^{∗}(M_{2}) ∪ ⋯ ∪ R_{a_{n}}^{∗}(M_{n}) ⊆ R^{∗}(M),

where M_{1}, M_{2}, …, M_{n} label the terminal vertices of T (M) and, for i ∈ {1, 2, …, n}, a_{i} labels the edge of T (M) incident to M_{i}. Moreover,

|R^{∗}(M)| ≥ ∑_{i=1}^{n}[r(M_{i}) − 1].

As each matroid M_{i} that labels a terminal vertex of T (M) is not a circuit or a cocircuit, since M is simple and cosimple, it follows that r(M_{i}) ≥ 3 and so |R^{∗}(M)| ≥ 2n. Theorem 3 follows from Theorem 6 because n ≥ 2. From Theorems 2 and 6, we conclude that, when the bound on Theorem 3 is attained for some simple and cosimple connected binary matroid M, then T (M) is a path whose terminal vertices are labeled by matroids isomorphic to M(K_{4}).

For a simple and cosimple connected binary matroid M, note that T (M) has only two vertices if and only if M has just one 2-separation. If M_{1} and M_{2} labels the two vertices of T (M), then M = M_{1} ⊕_{2} M_{2} and so r(M) = r(M_{1}) + r(M_{2}) − 1. Thus, from Theorem 6, we get: Corollary 1. Suppose that M is a simple and cosimple connected binary matroid. If M has just one 2-separation, then

|R^{∗}(M)| ≥ r(M) − 1.

This bound is close to the bound given by Theorem 2 and much better than the bound given by Theorem 3. It is not possible to get a substantially better bound depending on the number of 2-separations of M, as we show in an example after the proof of Theorem 6: we construct an infinite family of simple and cosimple connected binary matroids each having just two 2-separations and only four nonseparating cocircuits.

Proof of Theorem 6 assuming Theorem 4. Observe that each matroid M_{i} that labels a terminal vertex of T (M) is 3-connected. So, |R_{a_{i}}^{∗}(M_{i})| ≥ r(M_{i}) − 1, by Theorem 4. The result follows provided we show that

R_{a_{1}}^{∗}(M_{1}) ∪ R_{a_{2}}^{∗}(M_{2}) ∪ ⋯ ∪ R_{a_{n}}^{∗}(M_{n}) ⊆ R^{∗}(M).

Suppose that C^{∗} ∈ R_{a_{i}}^{∗}(M_{i}). Let T be the connected component of T (M) − e_{i} other than the vertex labeled by M_{i}. If N_{i} is the matroid such that T (N_{i}) = T, then M = M_{i} ⊕_{2} N_{i}. As r(M_{i}\C^{∗}) = r(M_{i}) − 1 ≥ 2, for C^{∗} ∈ R_{a_{i}}^{∗}(M_{i}), it follows that |E(M_{i}\C^{∗})| ≥ 3 and so M\C^{∗} = (M_{i}\C^{∗}) ⊕_{2} N_{i}. Thus M\C^{∗} is connected and hence C^{∗} ∈ R^{∗}(M). □

One may think that Theorem 4 is a particular case of a more general result, that holds for graphic matroids: if M is a 3-connected binary matroid and A ⊆ E(M), then the number of non-separating cocircuits of M that avoids A is at least r(M) + 1 − 2|A|. But this assertion is false, even for |A| = 2, as the next example shows. For m ≥ 2, let S_{m} be the binary spike having legs L_{0}, L_{1}, …, L_{m} and tip e. Suppose that L_{0} = {e, f, g}. Consider the 3-connected matroid B_{m} = S_{m}\g. Now, we prove that R_{{e,f}}^{∗}(B_{m}) = ∅. If C^{∗} is a cocircuit of B_{m} such that C^{∗} ∩{e, f} = ∅, then C^{∗} ∩ L_{i} ≠ ∅, for some i ∈ {1, 2, …, m}, say i = 1. By orthogonality, L_{1} − e ⊆ C^{∗}. But (L_{1} − e) ∪ f is a triad of B_{m} and so B_{m}\C^{∗} has f as a coloop. Thus R_{{e,f}}^{∗}(B_{m}) = ∅.

For n ≥ 2, let M_{1}, M_{2}, …, M_{n} be simple and cosimple connected binary matroids whose ground sets are pairwise disjoint. For i ∈ {1, 2, …, n}, choose a_{i} ∈ E(M_{i}). In this paragraph, we construct a matroid H having arbitrary larger rank such that M_{1}, M_{2}, …, M_{n} label the terminal vertices of T (H), a_{1}, a_{2}, …, a_{n} label the pendents edges of T (H) and

R_{a_{1}}^{∗}(M_{1}) ∪ R_{a_{2}}^{∗}(M_{2}) ∪ ⋯ ∪ R_{a_{n}}^{∗}(M_{n}) = R^{∗}(H).

That is, Theorem 6 cannot be improved. Let m, B_{m} and {e, f} be as in the previous paragraph. We may assume that E(B_{m}) ∩ E(M_{i}) = ∅, for every i. When n = 2, relabel the element e of B_{m} by a_{1} and let H′ be the 2-sum of M_{1} and B_{m}. When n ≥ 3, let H′ be the 2-sum of M_{1}, …, M_{n−1}, B_{m} and H′′, where H′′ is a cocircuit such that E(H′′) = {e, a_{1}, a_{2}, …, a_{n−1}}. Next, relabel the element f of B_{m} by a_{n} and let H be the 2-sum of H′ with M_{n}. Note that H has the desired properties. When n = 2 and M_{1} and M_{2} are both isomorphic to M(K_{4}), H has only four non-separable cocircuits and two 2-separations.

To prove Theorem 4, we need the next lemma from Bixby and Cunningham[1].

Lemma 1. Suppose that M is a 3-connected binary matroid such that r^{∗}(M) ≥ 3. If e ∈ E(M) and C^{∗} ∈ R^{∗}(M/e), then

(i) C^{∗} ∈ R^{∗}(M); or (ii) there are C_{1}^{∗}, C_{2}^{∗} ∈ R^{∗}(M) such that C_{1}^{∗} ∩ C_{2}^{∗} = {e}, C_{1}^{∗} ∪ C_{2}^{∗} = C^{∗} ∪ e and

C_{1}^{∗} △ C_{2}^{∗} = C^{∗}.

Theorem 4 is a consequence of the next result. Instead of proving that the cardinality of R_{a}^{∗}(M) is at least r(M) − 1, we show that the dimension of the subspace of the cocycle space spanned by R_{a}^{∗}(M) is at least r(M) − 1. Theorem 7. Suppose that M is a 3-connected binary matroid. If a ∈ E(M), then

dim_{GF (2)}R_{a}^{∗}(M) ≥ r(M) − 1.

Proof. Suppose that Theorem 7 is not true and choose a counter-example M such that |E(M)| is minimum. Observe that r(M) ≥ 3. Now, we divide the proof of this result in a sequence of lemmas.

Lemma 2. If e ∈ E(M) − a, then M\e is not 3-connected.

Proof. Suppose that M\e is 3-connected. By the choice of M, we have that

dim_{GF (2)}R_{a}^{∗}(M\e) ≥ r(M\e) − 1 = r(M) − 1.

If C^{∗} ∈ R_{a}^{∗}(M\e), then H = E(M) − (C^{∗} ∪ e) is a connected hyperplane of M\e. Hence H or H ∪e is a connected hyperplane of M and so R_{a}^{∗}(M)∩{C^{∗}, C^{∗} ∪e} ≠ ∅. Thus dim_{GF (2)}R_{a}^{∗}(M) ≥ dim_{GF (2)}R_{a}^{∗}(M\e); a contradiction. □

Lemma 3. If T is a triangle of M and e ∈ T − a, then there is a triad T^{∗} of M such that e ∈ T^{∗}.

Proof. By Lemma 2, M\f is not 3-connected, for every f ∈ T −a. As |T −a| ≥ 2, it follows, by Tutte’s triangle lemma (7.2 of [19]), that every element of T − a belongs to a triad of M. □

Lemma 4. If e ∈ E(M) − a and M/e is 3-connected, then

dim_{GF (2)}R_{a}^{∗}(M) = r(M) − 2

and R_{a}^{∗}(M) = R_{{a,e}}^{∗}(M).

Proof. By the choice of M, we have that

dim_{GF (2)}R_{a}^{∗}(M/e) ≥ r(M/e) − 1 = r(M) − 2.

By Lemma 1, if C^{∗} ∈ R_{a}^{∗}(M/e), then (i) C^{∗} ∈ R_{a}^{∗}(M); or (ii) there is a partition {X_{1}, X_{2}} of C^{∗} such that, for i ∈ {1, 2}, C_{i}^{∗} = X_{i} ∪ e ∈

R_{a}^{∗}(M).

Let R^{∗} be the family of cocircuits obtained from R_{a}^{∗}(M/e) by replacing each C^{∗} ∈ R_{a}^{∗}(M/e) for which (ii) happens by C_{1}^{∗} and C_{2}^{∗}. If (ii) happens to some C^{∗} ∈ R_{a}^{∗}(M/e), then the space spanned by R_{a}^{∗}(M/e) is properly contained in the space spanned by R^{∗} and so dim_{GF (2)}R_{a}^{∗}(M) > dim_{GF (2)}R_{a}^{∗}(M/e); a contradiction. Hence (i) occurs for every C^{∗} ∈ R_{a}^{∗}(M/e) and so R_{a}^{∗}(M/e) ⊆ R_{a}^{∗}(M). But

dim_{GF (2)}R_{a}^{∗}(M) ≤ r(M) − 2 ≤ dim_{GF (2)}R_{a}^{∗}(M/e).

So equality holds along this inequality and the first part of this lemma follows. Moreover, R_{a}^{∗}(M/e) spans R_{a}^{∗}(M) and hence every cocircuit of R_{a}^{∗}(M) does not include e. The second part of this result also follows. □

Lemma 5. If T_{1}, T_{2}, …, T_{n} is a fan of M such that n ≥ 2, then n = 3, T_{2} is a triangle and T_{1} ∩ T_{2} ∩ T_{3} = {a}.

Proof. There is two possibilities for T_{1}:

(i) If T_{1} is a triangle, then T_{1} − T_{2} = {a}, by Lemma 3.

(ii) If T_{1} is a triad, then a ∈ T_{1}. Suppose that a ∉ T_{1}. As M/e is 3-connected, for e ∈ T_{1} − T_{2}, it follows that R_{a}^{∗}(M) = R_{{a,e}}^{∗}(M), by Lemma 4. But T_{1} − e is a series class of M\e contained in a triangle and so M\T_{1} is connected; a contradiction. So a ∈ T_{1}.

For T_{n}, we have a similar result, namely:

(iii) T_{n} is a triangle and T_{n} − T_{n−1} = {a}; or (iv) T_{n} is a triad and a ∈ T_{n}.

So (ii) and (iv) hold. Hence T_{1} and T_{n} are triads such that a ∈ T_{1} ∩T_{n}. Thus n = 3 and a ∈ T_{2}. □

Lemma 6. If T is a triangle of M, then there are triads T_{1}^{∗} and T_{2}^{∗} of M such that T_{1}^{∗}, T, T_{2}^{∗} is a fan of M and a ∈ T_{1}^{∗} ∩ T ∩ T_{2}^{∗}.

Proof. Observe that M is not isomorphic to a wheel because the result holds for graphic matroids. Thus every chain of M is contained in a fan of M, by Theorem 1.6 of Oxley and Wu[15]. By Lemma 3, T is a link of a non-trivial chain of M. The result follows from Lemma 5. □

Lemma 7. If C^{∗} is a cocircuit of M such that a ∉ C^{∗}, then there is e ∈ C^{∗} such that M/e is 3-connected.

Proof. Suppose that M/e is not 3-connected, for every e ∈ C^{∗}. By the dual of Theorem 1 of Lemos[9], there are distinct triangles T_{1} and T_{2} of M meeting C^{∗}. By Lemma 6, a ∈ T_{1} ∩ T_{2}. Moreover, there are triads T_{1}^{∗} and T_{2}^{∗} of M such that a ∈ T_{1}^{∗}∩T_{2}^{∗} and T_{1}^{∗}, T_{1}, T_{2}^{∗} is a fan of M; a contradiction because T_{2} cannot intersect T_{1}^{∗} or T_{2}^{∗}. □

By Corollary 3.5 of Oxley and Wu[15], M must have at least two elements which are non-essential, since it is not isomorphic to a wheel. Let e be a non-essential element of M other than a. By Lemma 2, M/e is 3-connected. By Lemma 4, dim_{GF (2)}R_{a}^{∗}(M) = r(M) − 2 ≥ 1. So R_{a}^{∗}(M) ≠ ∅. Let C^{∗} be a cocircuit of M such that M\C^{∗} is connected and a ∉ C^{∗}. By Lemma 4, M/f is not 3-connected, for every f ∈ C^{∗} because C^{∗} ∈ R_{a}^{∗}(M) − R_{{a,f}}^{∗}(M); a contradiction to Lemma 7. So Theorem 4 follows. □

From Theorem 4, we have the next result which generalizes the bound obtained by McNulty and Wu[12] for the number of non-separating cocircuits avoiding an element of a simple and cosimple connected binary matroid. We omit its proof because it is similar to the proof of Theorem 6. Corollary 2. Suppose that a is an element of a simple and cosimple connected binary matroid M. If M is not 3-connected, then

R_{a_{1}}^{∗}(M_{1}) ∪ R_{a_{2}}^{∗}(M_{2}) ∪ ⋯ ∪ R_{a_{t}}^{∗}(M_{t}) ⊆ R_{a}^{∗}(M),  (1)

where M_{1}, M_{2}, …, M_{t} label the terminal vertices of T (M) avoiding the element a and, for i ∈ {1, 2, …, t}, a_{i} labels the edge of T (M) incident to M_{i}. Moreover,

|R_{a}^{∗}(M)| ≥ ∑_{i=1}^{t}[r(M_{i}) − 1].

This corollary is the best possible as the next examples show. Let m, B_{m}, H, H′ and f be as in the two paragraphs after the proof of Theorem 4. When a is chosen in E(B_{m}) − {e, f}, the matroid H attains equality in (1). When a is chosen to be equal to f, the equality in (1) holds for H′.

References

[1] R. E. Bixby and W. Cunningham, Matroids, graphs, and 3-connectivity, in “Graph Theory and Related Topics” (J. A. Bondy and U. S. R. Murty, Eds.), pp. 91-103, Academic Press, New York, 1979.

[2] W. H. Cunningham, A combinatorial decomposition theory, Ph. D. Thesis, University of Waterloo, 1973.

[3] L. Goddyn, J. van der Heuvel and S. McGuinness, Removable circuits in multigraphs, J. Combin. Theory Ser. B 71 (1997), 130-143.

[4] L. Goddyn and B. Jackson, Removable circuits in binary matroids, Combin. Probab. Comput. 8 (199), 539-545.

[5] B. Jackson, Removable cycles in 2-connected graphs of minimum degree at least four, J. London Math. Soc. (2) 21 (1980), 385-392.

[6] A. K. Kelmans, The concepts of a vertex in a matroid, the non-separating circuits and a new criterion for graph planarity, in “Algebraic Methods in Graph Theory, Vol. 1”, Colloq. Math. Soc. János Bolyai (Szeged, Hungary, 1978), Vol. 25, pp 345-388, North Holland, Amsterdam, 1981.

[7] A. K. Kelmans, A new planarity criterion for 3-connected graphs, J. Graph Theory 5 (1981), 259-267.

[8] A. K. Kelmans, Graph planarity and related topics, in “Graph Structure Theory” (N. Robertson and P. D. Seymour, Eds.), Contemporary Mathematics, Vol. 147, pp. 635-667, 1991.

[9] M. Lemos, On 3-connected matroids, Discrete Math. 73 (1989), 273-283.

[10] M. Lemos and J. Oxley, On removable circuits in graphs and matroids, J. Graph Theory 30 (1999), 51-66.

[11] M. Lemos and J. Oxley, On size, circunference and circuit removal in 3-connected matroids, Discrete Math. 220 (2000), 145-157.

[12] J. McNulty and H. Wu, Connected Hyperplanes in Binary Matroids, J. Combin. Theory Ser. B 79 (2000), 87-97.

[13] J. G. Oxley, Cocircuit coverings and packings for binary matroids, Math. Proc. Cambridge Phil. Soc. 83 (1978), 347-351.

[14] J. G. Oxley, Matroid Theory, Oxford Univ. Press, New York, 1992.

[15] J. Oxley and H. Wu, On the structure of 3-connected matroids and graphs, Europ. J. Combinatorics 21 (2000), 667-688.

[16] T. J. Reid and H. Wu, On minimally 3-connected binary matroids, Combin. Probab. Comput. 10 (2001), 453-461.

[17] C. Thomassen and B. Tøft, Non-separating induced cycles in graphs, J. Combin. Theory Ser. B 31 (1980), 199-224.

[18] W. T. Tutte, How to draw a graph, Proc. London Math. Soc. 13 (1963), 734-768.

[19] W. T. Tutte, Connectivity in matroids, Can. J. Math. 18 (1966), 1301-1324.

Departamento de Matemática, Universidade Federal de Pernambuco, Cidade Universitária, Recife, Pernambuco, Brazil

   E-mail address: manoel@dmat.ufpe.br