Parity Systems and the Delta-Matroid Intersection Problem

André Bouchet ^{∗} and Bill Jackson ^{†}

Submitted: February 16, 1998; Accepted: September 3, 1999.

Abstract

We consider the problem of determining when two delta-matroids on the same ground-set have a common base. Our approach is to adapt the theory of matchings in 2-polymatroids developed by Lovász [13] to a new abstract system, which we call a parity system. Examples of parity systems may be obtained by combining either, two deltamatroids, or two orthogonal 2-polymatroids, on the same ground-sets. We show that many of the results of Lovász concerning ‘double flowers’ and ‘projections’ carry over to parity systems.

1 Introduction: the delta-matroid intersection problem

A delta-matroid is a pair (V, B) with a finite set V and a nonempty collection B of subsets of V, called the feasible sets or bases, satisfying the following axiom:

∗Département d’informatique, Université du Maine, 72017 Le Mans Cedex, France.

bouchet@lium.univ-lemans.fr

†Department of Mathematical and Computing Sciences, Goldsmiths’ College, London

SE14 6NW, England. maa01wj@gold.ac.uk

1.1 For B_{1} and B_{2} in B and v_{1} in B_{1}ΔB_{2}, there is v_{2} in B_{1}ΔB_{2} such that B_{1}Δ{v_{1}, v_{2}} belongs to B.

Here P ΔQ = (P \ Q) ∪ (Q \ P) is the symmetric difference of two subsets P and Q of V. If X is a subset of V and if we set BΔX = {BΔX : B ∈ B}, then we note that (V, BΔX) is a new delta-matroid. The transformation (V, B) → (V, BΔX) is called a twisting. The rank of a subset P of V is

r(P) = max_{B∈B} |P ∩ B| + |(V \ P) ∩ (V \ B)|.  (1)

Thus r(P) = |V | if and only if P belongs to B.

Proposition 1.2 A nonempty collection B of subsets of V is the collection of bases of a matroid if and only if (V, B) is a delta-matroid and the members of B have the same cardinality.

We refer the reader to [4] for an introduction to delta-matroids and some of the problems considered in that paper.

Problem 1.3 Given delta-matroids (V, B_{1}) and (V, B_{2}) with rank functions r_{1} and r_{2}, respectively, search for a subset P of V that maximizes r_{1}(P)+r_{2}(P).

Problem 1.4 Given delta-matroids (V, B_{1}) and (V, B_{2}), search for B in B_{1} ∩ B_{2}.

The intersection problem 1.4 is a specialization of Problem 1.3 since the subsets P in B_{1}∩B_{2} are characterized by the relation r_{1}(P)+r_{2}(P) = 2|V |. A related problem considered in [4] is to find B_{1} in B_{1} and B_{2} in B_{2} maximizing |B_{1}ΔB_{2}|. The maximum is equal to |V | if and only if B_{1} ∩ (B_{2}ΔV) ≠ ∅.

The matroid parity problem is to find in a matroid, whose ground-set is partitioned into pairs, an independent set that is a union of pairs and of maximal cardinality. Lovász [13] has given a general solution of that problem, which is efficient when a linear representation of the matroid is known. He has also described in [12] an instance of the matroid parity problem, whose solution requires exponential time, with respect to the size of the ground-set, when an independence oracle is known. It is shown in

[5] that the matroid parity problem can be expressed as a delta-matroid intersection problem. It follows that to solve the delta-matroid intersection problem requires in general exponential time when a separation oracle is known. The separation oracle, for a delta-matroid (V, B), tells whether an ordered pair (P, Q) of disjoint subsets of V is such that P ⊆ B and Q∩B = ∅, for some B in B.

We shall approach the delta-matroid intersection problem by adapting Lovász’ method. However the last step, giving an efficient solution when linear delta-matroids are involved, is still unsolved. We now recall two natural instances of the delta-matroid intersection problem, where linear representations are known.

Complementary nonsingular principal submatrices

Let A = (A_{vw})_{v,w∈V} be a symmetric or skew-symmetric matrix with entries in a field F. For every subset W of V we denote by A[W] the principal submatrix (A_{vw})_{v,w∈W} and we make the convention that A[∅] is a nonsingular matrix. Set

B(A) = {B ⊆ V : A[B] is nonsingular}.

It is shown in [3] that (V, B(A)) is a delta-matroid. If A is skew-symmetric, then every member of B(A) has even cardinality, whereas this is false in general when A is symmetric. A delta-matroid is said to be even if the symmetric difference of ant pair of bases has even cardinality. So every deltamatroid obtained by twisting (V, B(A)) is even when A is skew-symmetric.

Problem 1.5 Given a symmetric or skew-symmetric matrix A = (A_{vw})_{v,w∈V}, search for two complementary subsets P and Q of V such that A[P] and A[Q] are nonsingular.

Problem 1.6 Given two matrices A′ = (A′_{vw})_{v,w∈V} and A′′ = (A′′_{vw})_{v,w∈V}, which are both symmetric or both skew-symmetric, and a subset X of V, search for two subsets P′ and P′′ of V such that A′[P′] and A′′[P′′] are nonsingular and P′ΔP′′ = X.

Problem 1.5 is an instance of Problem 1.6: take A′ = A′′ = A and X = V. Problem 1.6 is an instance of the delta-matroid intersection problem 1.4: take B_{1} = B(A′) and B_{2} = B(A′′)ΔX.

Orthogonal Euler tours

Let G be a connected 4-regular graph that is evenly directed: each vertex is the head of precisely two directed edges. A directed transition is a pair of directed edges incident to the same vertex v, one entering v and one leaving v. A pair of successive directed edges of an Euler tour T is called a directed transition used by T. Two directed Euler tours of G are orthogonal if they use no common directed transition.

Problem 1.7 Find whether G admits a pair of orthogonal Euler tours.

Let us fix a reference directed Euler tour U of G and let us consider the sequence of vertices S that are encountered while running along U. The sequence S is defined up to a rotation, depending on the starting point of U, and each vertex occurs precisely twice in S. For example

S = (a e f a c d e c b f d b),

when U is the directed Euler tour depicted on the left side of Figure 1. An alternance of S is a nonordered pair vw of vertices such that v and w alternatively occur in S. Let A = (A_{vw})_{v,w∈V} be the matrix with entries in GF(2) such that

A_{vw} = 1 ⟺ vw is an alternance of U.

The matrix corresponding to the example is depicted on the right side of Figure 1. If T is another Euler tour of G, let C(U, T) be the subset of vertices v such that U and T use distinct transitions at v. Clearly T is determined when U and C(U, T) are known. The results of [2] imply that A[P] is nonsingular if and only if there is an Euler tour T such that C(U, T) = P. Hence to find a pair of orthogonal Euler tours in G amounts to finding two complementary subsets P and Q of V such that A[P] and A[Q] are nonsingular, which is a solution to Problem 1.5.

Figure 1: An Euler tour and the corresponding binary matrix.

A solution to Problem 1.7 is given in [1] when G is plane and the boundary of each face is consistently directed. One may also consider two connected and evenly directed 4-regular graphs G_{1} and G_{2} on the same vertex-set V, each with a bicoloring of the directed transitions satisfying the following property: any two directed transitions incident to the same vertex have the same colour if and only if they are disjoint. An Euler tour T_{1} of G_{1} is orthogonal to an Euler tour T_{2} of G_{2} if, for every vertex v in V, the directed transitions of T_{1} and T_{2} incident to v have distinct colours.

Problem 1.8 Find whether G_{1} and G_{2} have orthogonal Euler tours.

If G_{1} and G_{2} are equal to the graph G of Problem 1.7 and each directed transition of G has the same colour in G_{1} and G_{2}, then T_{1} and T_{2} are orthogonal in the new sense if and only if they are orthogonal in the first sense. Hence Problem 1.7 is an instance of Problem 1.8. By generalizing the preceding argument one shows that Problem 1.8 is an instance of Problem 1.6.

Finally one may consider the following more general situation. Given a connected 4-regular graph G, let us define a transition as a pair of edges incident to the same vertex. Let us forbid one transition at each vertex and let us consider the collection of Euler tours that use no forbidden transition. If G is evenly directed one retrieves the collection of directed Euler tours by forbidding at each vertex the transition made of the two directed edges leaving that vertex. If we define two Euler tours to be orthogonal if they use no common transition, then one generalizes Problems 1.7 and 1.8. One can show, by using the property 5.3 of [3], that the two new problems are instances of Problems 1.5 and 1.6, respectively, where the matrices are symmetric with entries in GF(2). Note that a matrix with entries in GF(2) is skew-symmetric if and only if it is symmetric with a null diagonal.

2 Background on 2-matroids

Many properties of delta-matroids are invariant by twisting. For example if B is a common base of the delta-matroids (V, B_{1}) and (V, B_{2}) in the intersection problem 1.4, then BΔX is a common base of (V, B_{1}ΔX) and (V, B_{2}ΔX), for every subset X of V. The structure of a 2-matroid, which is a particular case of the structure of multimatroid introduced in [5], encompasses a twisting class of delta-matroids.

If Ω is a partition of a set U, then a subtransversal (resp. transversal) of Ω is a subset A of U such that |A∩ω| ≤ 1 (resp. |A∩ω| = 1) holds for all ω in Ω. The set of subtransversals of Ω is denoted by S(Ω). A class of Ω is called a skew class or, if it has cardinality 2, a skew pair. Two subtransversals are compatible if their union is also a subtransversal. A multimatroid is a triple Q = (U, Ω, r), with a partition Ω of a finite set U and a rank function r : S(Ω) → IN, satisfying the four following axioms:

2.1 r(∅) = 0;

2.2 r(A) ≤ r(A+x) ≤ r(A)+1 if A is a subtransversal of Ω, x is an element of U, and A is disjoint from the skew class of Ω containing x;

2.3 r(A) + r(B) ≥ r(A ∪ B) + r(A ∩ B) if A and B are compatible subtransversals of Ω;

2.4 r(A + x) − r(A) + r(A + y) − r(A) ≥ 1 if A is a subtransversal of Ω, x and y are distinct elements in the same class ω of Ω, and A ∩ ω = ∅.

If each class of Ω has cardinality equal to the positive integer q then Q is also called a q-matroid. If q = 1, then r is defined for every subset of U and the first three axioms amount to say that r is a matroid rank function, whereas the fourth axiom is void. We shall be more especially interested in 2matroids. An independent set of a multimatroid (U, Ω, r) is a subtransversal I such that r(I) = |I|. A base is a maximal independent set. The following property, which is an easy consequence of the axiom 2.4, implies that the bases of a 2-matroid are transversals.

Proposition 2.5 [5] The bases of a multimatroid (U, Ω, r) are transversals of Ω if every class of Ω has at least two elements.

In particular, if B(Q) is the collection of bases of a 2-matroid Q, then each member of B(Q) is a transversal of Ω. Let T be a transversal of Ω. The set system Q ∩ T = (T, {B ∩ T : B ∈ B(Q)}) is the section of Q by T.

Theorem 2.6 [5] A set system is a delta-matroid if and only if it is a section of a 2-matroid.

To compare the various sections Q ∩ T of the same 2-matroid Q = (U, Ω, r), when T ranges in the collection of transversals of Ω, it is convenient to define a surjective mapping p : U → V such that p(u′) = p(u′′) if and only if u′ and u′′ belong to the same class of Ω. In particular we can take V = Ω. If we denote by p(Q ∩ T) the isomorphic image of the delta-matroid Q ∩ T by the bijective mapping p_{|T}, then one easily verifies that

p(Q ∩ T) = p(Q ∩ T′)Δp(T ΔT′),

for every transversal T′ of Ω. This implies that p(Q ∩ T) ranges in a twisting class of delta-matroids when T ranges in the collection of transversals of Ω. Thus Problems 1.3 and 1.4 can be restated as Problem 2.7 Given 2-matroids (U, Ω, r_{1}) and (U, Ω, r_{2}), search for a subtransversal A of Ω that maximizes r_{1}(A) + r_{2}(A).

Problem 2.8 Given 2-matroids Q_{1} = (U, Ω, r_{1}) and Q_{2} = (U, Ω, r_{2}), search for a base B ∈ B(Q_{1}) ∩ B(Q_{2}).

We shall investigate these problems using a similar technique to Lovász [13], who replaced the parity problem by the search for a maximum matching in a 2-polymatroid. We similarly extend the two preceding problems into a search for a maximum matching in a parity system.

3 Parity system

A 2-polymatroid is a pair (V, ρ) with a finite set V and a rank function ρ : V → IN satisfying the following axioms

3.1 ρ(∅) = 0;

3.2 ρ(A) ≤ ρ(A + x) ≤ ρ(A) + 2 is satisfied for every subset A of V and every element x in V \ A;

3.3 ρ(A) + ρ(B) ≥ ρ(A ∪ B) + ρ(A ∩ B) is satisfied for every pair of subsets A and B of V.

A matching is a subset M such that ρ(M) = 2|M|.

The definition of a 2-polymatroid becomes the definition of a matroid, when the value 2 in the axiom 3.2 is replaced by 1. A parity system generalizes a 2-matroid in the same way; the value 1 that occurs in the axioms 2.2 and 2.4 is replaced by 2 in the following axioms 3.5 and 3.7. Throughout the paper we shall use the notation r for a 2-matroid, ρ for a 2-polymatroid, and R for a parity system.

A parity system is a triple P = (U, Ω, R) with a paired set (U, Ω) and a rank function R : S(Ω) → IN satisfying the four following axioms:

3.4 R(∅) = 0;

3.5 R(A) ≤ R(A + x) ≤ R(A) + 2 is satisfied for every subtransversal A of Ω and every x in U provided that A is disjoint from the skew class containing x;

3.6 R(A) + R(B) ≥ R(A ∪ B) + R(A ∩ B) is satisfied for every pair of compatible subtransversals A and B of Ω; 3.7 R(A+x)−R(A)+R(A+y)−R(A) ≥ 2 is satisfied for every subtransversal A of Ω and every skew pair {x, y} provided that A is disjoint from the skew class including {x, y}.

We say that P is indexed on a set V if Ω is indexed on V, that is Ω = {Ω_{v} : v ∈ V }. (The free sum of two orthogonal 2-polymatroids, constructed in the sequel, is indexed on a set V in a natural way.) We can always assume that P is indexed on a set V, taking V = Ω if no natural index-set is specified. If A is a subtransversal of Ω then we set σ(A) = {v ∈ V : A ∩ Ω_{v} ≠ ∅} and we call σ(A) the support of A. If W is a subset of V, then we denote by P [W] the parity system (U′, Ω′, R′), where U′ = ∪_{v∈W} Ω_{v}, Ω′ = {Ω_{v} : v ∈ W }, and R′ is the restriction of R to S(Ω′).

A matching is a subtransversal M of Ω such that R(M) = 2|M|. Let ν(P) denote the size of a maximum matching in P. We shall be interested in the following problem.

Problem 3.8 Given a parity system P, search for a maximum matching in P.

In the following two subsections we will describe two natural constructions for parity systems.

Sum of a pair of 2-matroids

If (U, Ω) is a paired set, then for every element u in U, we denote by ũ the element that belongs to the same pair as u and is distinct from u.

Consider a pair of 2-matroids, Q_{1} = (U, Ω, r_{1}) and Q_{2} = (U, Ω, r_{2}), defined on the same partitioned set (U, Ω). Set R = r_{1} + r_{2}. Then P = (U, Ω, R) is a parity system, which we call the sum of Q_{1} and Q_{2}. Furthermore a solution to Problem 3.8 for P will give rise to a solution to Problem 2.7 for Q_{1} and Q_{2}. We shall be especially interested in the case when P is a sum of a 2-matroid Q = (U, Ω, r) and the converse 2-matroid Q̃ = (U, Ω, r̃), where r̃ is defined by the relation r̃(A) = r(Ã), for every subtransversal A of Ω. In this case ν(P) = |Ω| if and only if Q has two complementary bases. Thus Problem 3.8 generalizes Problem 1.5, and hence also Problem 1.7.

More generally one may consider a 2-matroid Q and a partition Π of U into pairs such that π = {u_{1}, u_{2}} ∈ Π implies π̃ := {ũ_{1}, ũ_{2}} ∈ Π. By setting U′ = Π, Ω′ = {{π, π̃} : π ∈ Π} and

R′(A′) = r( ⋃_{π∈A′} π), A′ ∈ S(Ω′),

one defines a parity system Q/Π := (U′, Ω′, R′). A solution to Problem 3.8 for this parity system would give a solution to a parity problem for the 2matroid Q which is analogous to the parity problem for matroids considered by Lovász in [13].

Free sum of two orthogonal 2-polymatroids

If (V, ρ) is a 2-polymatroid, then one easily verifies that the mapping ρ^{∗}, defined on the power-set of V by the formula

ρ^{∗}(A) = 2|A| + ρ(V \ A) − ρ(V),

defines a 2-polymatroid (V, ρ^{∗}), which we call the dual of (V, ρ).

Consider a pair of 2-polymatroids defined on the same ground-set, say (V, ρ_{1}) and (V, ρ_{2}). We say that (V, ρ_{2}) is orthogonal to (V, ρ_{1}) if ρ_{1}^{∗} − ρ_{2} is a nondecreasing function. We note that a pair of orthogonal 2-polymatroids is a special type of generalized polymatroids due to A. Frank [7] and R. Hassin [11]. See also Frank and Tardos [8] for relevant references.

Proposition 3.9 The 2-polymatroid (V, ρ_{1}) is orthogonal to (V, ρ_{2}) if and only if the relation

ρ_{1}(A + x) − ρ_{1}(A) + ρ_{2}(B + x) − ρ_{2}(B) ≥ 2  (2)

is satisfied for every pair of disjoint subsets A and B of V and every element x in V \ (A ∪ B).

Construction 3.10 Consider two orthogonal 2-polymatroids (V, ρ_{1}) and (V, ρ_{2}). Set

U = V_{1} + V_{2}, where
V_{i} = {v_{i} : v ∈ V }, i = 1, 2,
Ω = {Ω_{v} : v ∈ V }, where
Ω_{v} = {v_{1}, v_{2}}, v ∈ V,
R(A) = R_{1}(A ∩ V_{1}) + R_{2}(A ∩ V_{2}), A ∈ S(Ω), where
R_{i}({v_{i} : v ∈ W }) = ρ_{i}(W), i = 1, 2, W ⊆ V.

By using the relation (2), one verifies that P (V, ρ_{1}, ρ_{2}) := (U, Ω, R) is a parity system. We call that parity system the free sum of (V, ρ_{1}) and (V, ρ_{2}). Then ν(P) = |Ω| if and only if (V, ρ_{1}) and (V, ρ_{2}) have two complementary polymatroid matchings.

4 Flowers and double flowers

Let P be a parity system. A base of P is a transversal B such that R(B) has a maximal value. A circuit is a subtransversal C of Ω such that R(C) is odd and every proper subset of C is a matching.

A flower (resp. double flower) is a subtransversal that is the disjoint union of a maximum matching with a subtransversal of cardinality 1 (resp. 2). A flower contains precisely one circuit. A circuit is essential if it is contained in a flower. A double flower contains at least two circuits (which are essential). A double flower is trivial if it contains two disjoint circuits (then there are no other circuits contained in that double flower).

Let F be a collection of subsets of a set V. A separator of F is a subset W of V such that every member of F is either contained in W or disjoint from W. The separator is proper if it is neither empty nor equal to V.

A parity system P, indexed on the set V, is reducible if there exists a bipartition {V_{1}, V_{2}} of V such that

ν(P) = ν(P [V_{1}]) + ν(P [V_{2}]).

Proposition 4.1 If a parity system is irreducible, then the collection of supports of its essential circuits has no proper separator.

Proof. Consider an irreducible parity system P = (U, Ω, R) indexed on V and assume for a contradiction that the collection of supports of its essential circuits admits a proper separator V_{1}. Set V_{2} = V \ V_{1} and denote by U_{i} the ground-set of P [V_{i}], for i = 1, 2. Consider a maximum matching M of P. Since P is irreducible, the matching M ∩ U_{i} is not a maximum matching of P_{i}, for some i = 1, 2 (otherwise we would have ν(P) = |M| = |M ∩ U_{1}| + |M ∩ U_{2}| = ν(P [V_{1}] + ν(P [V_{2}])). Choose M, i and a maximum matching M_{i} of P_{i} such that

|M ∩ M_{i}| is maximal.  (3)

We have |M ∩ U_{i}| < |M_{i}|. Hence we can find an element u in M_{i} such that M ∩ {u, ũ} = ∅ (we recall that ũ is the element of U − u which belongs to the same skew pair of Ω as u). So M + u is a flower of P. Let C be the essential circuit contained in M + u. The element u is contained in C and u is supported by V_{i}. Since V_{1} separates the essential circuits of P, the support of C is contained in V_{i}. Since the circuit C is not contained in the matching M, we can find an element u′ in C \ M. Then M′ := M + u − u′ is a new matching of P that contradicts (3). ⊓ ⊔

The deficiency of a parity system is the number of its skew pairs less the cardinality of a maximum matching.

Proposition 4.2 An irreducible parity system P of deficiency at least two admits a nontrivial double flower.

Proof. First we show that we can find an essential circuit C_{1} and a flower F_{2} satisfying the two following properties:

(i) σ(C_{1}) ∩ σ(C_{2}) ≠ ∅, for the circuit C_{2} contained in F_{2};

(ii) σ(F) ≠ σ(F_{2}), for all flowers F containing C_{1}.

Consider any essential circuit D′ and a flower F′ that contains D′. There is an element v in V \ σ(F′) because P has deficiency at least two. There is an essential circuit D′′ whose support contains v, otherwise V − u would be a proper separator of the supports of the essential circuits of P, contradicting Proposition 4.1 and the fact that P is irreducible. By Proposition 4.1, we may choose a sequence of essential circuits D′ = D_{1}, D_{2}, ⋯, D_{p} = D′′ such that σ(D_{i}) ∩ σ(D_{i+1}) ≠ ∅, for 1 ≤ i < p. Let j, 1 ≤ j ≤ p, be the minimal index such that all flowers F′′ containing D_{j} satisfy σ(F′′) ≠ σ(F′). The index j exists because all flowers F′′ containing D_{p} satisfy v ∈ σ(D_{p}) ⊆ σ(F′′), whereas v ∉ σ(F′). We have obviously j > 1. Therefore we can take C_{1} = D_{j} and F_{2} equal to any flower containing D_{j−1} and such that σ(F_{2}) = σ(F′). Then C_{1} and F_{2} will satisfy (i) and (ii).

To complete the proof of the proposition, we choose a flower F_{1} that contains C_{1} and such that

|F_{1} ∩ F_{2}| is maximal.  (4)

According to the property (ii) there is an element u in F_{2} such that σ(u) does not belong to σ(F_{1}). Hence F_{1} + u is a double flower. Suppose for a contradiction that F_{1} + u is trivial. Let C be the circuit contained in F + u and disjoint from C_{1}. The supports of C and C_{2} are distinct by the property (i). Hence we can find an element u′ in C \ C_{2}. Then F′_{1} := F_{1} + u − u′ is a new flower that contains C_{1} and contradicts (4). ⊓ ⊔

We are now able to prove our first result on Problem 3.8.

Theorem 4.3 Let P be a parity system. Then at least one of the following alternatives holds.

(a) There exists a partition {V_{1}, V_{2}, …, V_{m}} of V such that

(i) ν(P) = ∑_{i=1}^{m} ν(P [V_{i}]), and (ii) ν(P [V_{i}]) = |V_{i}| − 1 = ν(P [V_{i} − v])

for all 1 ≤ i ≤ m and all v ∈ V_{i}.

(b) There exists v ∈ V such that every maximum matching of P covers v.

(c) P has a nontrivial double flower.

Proof. If ν(P) = |V | then (b) holds for all v ∈ V. Suppose ν(P) = |V |−1. If

(a) does not hold for the trivial partition {V } then ν(P [V −v]) = ν(P)−2 for some v ∈ V and (b) holds for v. Thus we may suppose that ν(P) ≤ |V |−2. If P is irreducible then (c) holds by Proposition 4.2 so we may also suppose that P is reducible. Choose a partition {V_{1}, V_{2}, …, V_{m}} of V such that ν(P) = ∑_{i=1}^{m} ν(P [V_{i}]) and m is as large as possible. Then each maximum matching of P is the disjoint union of maximum matchings in P [V_{i}] for 1 ≤ i ≤ m. Thus we have ν(P [V_{i}]) ≤ |V_{i}| − 2 for 1 ≤ i ≤ m, otherwise (a) or (b) hold for P as above. Moreover the maximality of m implies that each P [V_{i}] is irreducible. Hence, by Proposition 4.2, we may choose a nontrivial double flower F_{1} in P [V_{1}]. Let M_{i} be a maximum matching in P [V_{i}] for 2 ≤ i ≤ m. Then the union of F_{1} with ∪_{i=2}^{m}M_{i} is a nontrivial double flower in P and hence P satisfies (c). ⊓ ⊔

We shall use Theorem 4.3 in a later section to reduce the problem of determining ν(P) to smaller parity systems than P. To conclude this section we need one further result on the structure of double flowers. We define a double circuit in a parity system to be a subtransversal D such that R(D) = 2|D| − 2 and for all t ∈ D we have R(D − t) = 2|D| − 3.

Proposition 4.4 Let D be a double circuit in a parity system P. Then there exists a unique partition {D_{1}, D_{2}, …, D_{m}} of D such that D −D_{i} is a circuit of P for all 1 ≤ i ≤ m.

Proof. For each t ∈ D we have R(D − t) = 2|D − t| − 1. Thus D − t contains a unique circuit C(t). Let D(t) = D − C(t) and choose s ∈ D(t). Then s ∉ C(t) so C(t) ⊆ D − s. Thus C(s) = C(t) and D(s) = D(t). Hence {D(t) : t ∈ D} is the required partition of D. ⊓ ⊔

We call the partition of a double circuit D given by Proposition 4.4 the principal partition of D. Thus D is a trivial double circuit if and only if its principal partition has exactly two elements.

5 Compressing double flowers

Let P = (U, Ω, R) and P′ = (U, Ω, R′) be parity systems. We say that P′ is a switching of P if

(a) |R(A) − R′(A)| ≤ 1 for all A ∈ S(Ω),

(b) |R(A) − R′(A)| ≤ |R(B) − R′(B)| for all A ⊆ B ∈ S(Ω), and

(c) (R(A) − R′(A))(R(B) − R′(B)) ≥ 0 for all A ⊆ B ∈ S(Ω).

Note that if P′ is a switching of P then (a) implies that ν(P′) ≥ ν(P) − 1.

We say that a switching P′ of P compresses a double flower F of P if R′(C) < R(C) for all circuits C of F in P. The following three propositions will be used to deduce that if P′ is a switching of P which compresses a double flower F of P then ν(P′) = ν(P) − 1.

Proposition 5.1 Let P = (U, Ω, R) be a parity system, F be a double flower in P and P′ = (U, Ω, R′) be a switching of P which compresses F. Suppose that ν(P′) = ν(P) = ν and let M be a ν-matching in P′. Then R(M) < 2ν.

Proof. Suppose that R(M) = 2ν. We may suppose that M has been chosen such that |M ∩F | is maximum. Since |M| = ν and |F | = ν +2 we can choose f ∈ F such that σ(f) ∉ σ(M). Then R′(M + f) = 2ν + 1 = R(M + f), since M is a maximum matching in both P′ and P. Since P′ is a switching of P we have R′(A) = R(A) for all A ⊆ M + f. Since P′ compresses F it follows that C ⊈ M + f for all circuits C of F in P. Let C′ be the unique circuit of M + f in P′ and P. Then C′ ⊈ F and so we may choose g ∈ C′ − F. Let M′ = M − g + f. Then M′ is a ν-matching in both P′ and P. Furthermore |M′ ∩ F | > |M ∩ F |. This contradicts the choice of M and completes the proof of the proposition. ⊓ ⊔

Proposition 5.2 Let P = (U, Ω, R) be a parity system, F be a double flower in P and P′ = (U, Ω, R′) be a switching of P which compresses F. Suppose that ν(P′) ≤ ν(P). Then ν(P′) = ν(P) − 1.

Proof. Suppose that ν(P′) = ν(P). By Proposition 5.1, we have R(M) < 2ν for all ν-matchings M of P′. Choose a ν-matching M of P′ such that |M ∩F | is maximum. Since |M| = ν and |F | = ν + 2 we can choose f ∈ F such that σ(f) ∉ σ(M). Then R′(M +f) = 2ν +1 ≥ R(M +f), since M is a maximum matching in P′. Since P′ is a switching of P we have R′(A) ≥ R(A) for all A ⊆ M + f. Since P′ compresses F it follows that C ⊈ M + f for all circuits C of F in P. Let C_{1} be the unique circuit of M + f in P′. Then R′(C_{1}) = |C_{1}| − 1 ≥ R(C_{1}). Let C_{2} be a circuit of P contained in C_{1}. Then C_{2} ⊆ M + f so R′(C_{2}) ≥ R(C_{2}). Thus C_{2} ⊈ F and so we may choose g ∈ C_{2} − F ⊆ C_{1} − F. Let M′ = M − g + f. Then M′ is a ν-matching in P′. Furthermore |M′ ∩ F | > |M ∩ F |. This contradicts the choice of M and completes the proof of the proposition. ⊓ ⊔

Proposition 5.3 Let P = (U, Ω, R) be a parity system, F be a double flower in P and P′ = (U, Ω, R′) be a switching of P which compresses F. Then ν(P′) = ν(P) − 1.

Proof. Suppose that the proposition is false. Using condition (a) in the definition of a switching we have ν(P′) ≤ ν(P)+1. Using Proposition 5.2 we deduce that ν(P′) = ν(P)+1. Let ν(P) = ν. Choose a (ν+1)-matching M of P′ such that |M ∩ F | is maximum. Since |M| = ν + 1 and |F | = ν + 2 we can choose f ∈ F such that σ(f) ∉ σ(M). Then R′(M +f) = 2ν +3 ≥ R(M +f), since M is a maximum matching in P′. Since P′ is a switching of P we have R′(A) ≥ R(A) for all A ⊆ M + f. Since P′ compresses F it follows that C ⊈ M + f for all circuits C of F in P. Let C_{1} be the unique circuit of M + f in P′. Then R′(C_{1}) = |C_{1}| − 1 ≥ R(C_{1}). Let C_{2} be a circuit of P contained in C_{1}. Then C_{2} ⊆ M + f so R′(C_{2}) ≥ R(C_{2}). Thus C_{2} ⊈ F and so we may choose g ∈ C_{2} − F ⊆ C_{1} − F. Let M′ = M − g + f. Then M′ is a (ν + 1)-matching in P′. Furthermore |M′ ∩ F | > |M ∩ F |. This contradicts the choice of M and completes the proof of the proposition. ⊓ ⊔

6 Sums of two 2-matroids

Let Q_{1} and Q_{2} be 2-matroids. When Q_{1} and Q_{2} have the same ground-set and skew classes we shall use Q_{1} + Q_{2} to denote the parity system which is the sum of Q_{1} and Q_{2}. When Q_{1} and Q_{2} have disjoint ground-sets we shall use Q_{1} ⊕ Q_{2} to denote the 2-matroid which is the direct sum of Q_{1} and Q_{2}.

Let Q = (U, Ω, r) be a 2-matroid and v = {t, t̃} be a skew class of Q. Following [6, Section 5] we define the 2-matroid Q^{t} = (U^{t}, Ω^{t}, r^{t}) by putting U^{t} = U − v, Ω^{t} = Ω − {v} and r^{t}(A) = r(A + t) − r(t) for all A ∈ S(Ω^{t}). We shall use this operation to construct switchings.

Proposition 6.1 Let P = Q_{1} + Q_{2} and {t, t̃} be a skew class of P. Let P′ = Q_{1}^{t} + Q_{2}^{t} and P′′ = Qt̃ ; 1 + Q_{2}^{t}. Then P′′ is a switching of P′.

Proof. Since R′ = r_{1}^{t} + r_{2}^{t} and R′′ = rt̃ ; 1 + r_{2}^{t} it suffices to show that:

(a) |r_{1}^{t}(A) − rt̃ ; 1(A)| ≤ 1 for all A ∈ S(Ω^{t}). This follows since

r_{1}(A) ≤ r_{1}^{t}(A) ≤ r_{1}(A) + 1 and r_{1}(A) ≤ rt̃ ; 1(A) ≤ r_{1}(A) + 1.

(b) |r_{1}^{t}(A) − rt̃ ; 1(A)| ≤ |r_{1}^{t}(B) − rt̃ ; 1(B)| for all A ⊆ B ∈ S(Ω^{t}). Suppose this is false. Then by symmetry we may assume that r_{1}^{t}(B) − rt̃ ; 1(B) = 0 and r_{1}^{t}(A) − rt̃ ; 1(A) = 1. This implies that r_{1}(B + t) − r_{1}(B + t̃) = 0 and r_{1}(A + t) − r_{1}(A + t̃) = 1. Applying the fourth axiom of 2-matroids to B we deduce that r_{1}(B + t) = r_{1}(B) + 1 = r_{1}(B + t̃). Submodularity now implies that r_{1}(A + t) = r_{1}(A) + 1 = r_{1}(A + t̃) contradicting the second previous equality.

(c) (r_{1}^{t}(A)−rt̃ ; 1(A))(r_{1}^{t}(B)−rt̃ ; 1(B)) ≥ 0 for all A ⊆ B ∈ S(Ω). Suppose this is false. Then by symmetry we may assume that r_{1}^{t}(B) − rt̃ ; 1(B) = −1 and r_{1}^{t}(A) − rt̃ ; 1(A) = 1. This implies that r_{1}(B + t) − r_{1}(B + t̃) = −1 and r_{1}(A + t) − r_{1}(A + t̃) = 1. Thus r_{1}(B + t) = r_{1}(B) = r_{1}(B + t̃) − 1 and r_{1}(A + t̃) = r_{1}(A) = r_{1}(A + t) − 1. But r_{1}(B + t̃) = r_{1}(B) + 1 implies that r_{1}(A + t̃) = r_{1}(A) + 1 by submodularity, contradicting the third previous equality.

⊓ ⊔

We use Q(t) to denote the 2-matroid (U, Ω, r) where U = {t, t̃}, Ω = {{t, t̃}}, r(t) = 0, and r(t̃) = 1.

Proposition 6.2 Let P = Q_{1} + Q_{2}. Let {t, t̃} be a skew class of P and let P′ = (Q_{1}^{t} ⊕ Q(t)) + Q_{2}. Then P′ is a switching of P.

Proof. The proposition can be proved in a similar way to Proposition 6.1. ⊓ ⊔

Proposition 6.3 Let P = Q_{1} + Q_{2} and v = {t, t̃} be a skew class of P which is covered by every maximum matching of P. Let P′ = (Q_{1}^{t} ⊕ Q(t)) +

(Qt̃ ; 2 ⊕ Q(t̃)). Then ν(P′) < ν(P).

Proof. Suppose ν(P′) ≥ ν(P) = ν, and let M be a matching in P′ of size ν. Since R′(t) = 1 = R′(t̃), M does not cover v. Thus

2|M| = R′(M) = r_{1}(M + t) − r_{1}(t) + r_{2}(M + t̃) − r_{1}(t̃).

It follows that r_{1}(M) = |M| = r_{2}(M) and hence M is a matching in P. This contradicts the fact that all maximum matchings of P cover v. Hence ν(P′) < ν(P). ⊓ ⊔

Proposition 6.4 Let P = Q_{1} + Q_{2} and D be a nontrivial double circuit of P. Then r_{i}(D) = |D| − 2 and r_{j}(D) = |D| for some {i, j} = {1, 2}.

Proof. Suppose the proposition is false. Since r_{1}(D) + r_{2}(D) = 2|D| − 2 and r_{i}(D) ≤ |D| for 1 ≤ i ≤ 2, we must have r_{1}(D) = |D| − 1 = r_{2}(D). Hence D contains a unique circuit C_{i} of Q_{i} for 1 ≤ i ≤ 2. Furthermore, since R(D − t) = R(D) − 1 for all t ∈ D, each element of D belongs to exactly one of C_{1} or C_{2}. Thus the elementary partition of D is precisely {C_{1}, C_{2}} and D is a trivial double circuit of P. ⊓ ⊔

7 Tight parity systems

We say that a 2-matroid Q is tight if for all transversals T and all skew classes v of Q we have r(T) ≡ r(T Δv) + 1 mod 2. We say that a parity system P is tight if for all transversals T and all skew classes v of P we have R(T) ≡ R(T Δv) mod 2. Thus if P is the sum of two tight 2-matroids then P is a tight parity system. Furthermore, if P is a tight parity system then the parity of R(T) is constant over all transversals T of P. We shall refer to this value as the sign of the tight parity system and denote it by sgn(P).

Proposition 7.1 If P is a tight parity system then

ν(P) ≡ sgn(P) + |Ω| mod 2.

Proof. Let ν(P) = ν and M be a maximum matching in P. We shall show that R(A) = ν + |A| for all subtransversals A of P which contain M. We use induction on |A − M|. The assertion is true when A = M by the choice of M. Hence suppose |A − M| > 0 and choose t ∈ A − M. By the inductive hypothesis R(A − t) = ν + |A| − 1. Thus

ν + |A| − 1 ≤ R(A) ≤ ν + |A| + 1.

If R(A) = |A|+ν +1 then A would contain a (ν +1)-matching, contradicting the maximality of ν. If R(A) = ν + |A| − 1 then by the fourth axiom for parity systems we have R(A − t + t̃) = ν + |A| + 1 and we again contradict the maximality of ν. Thus R(A) = ν + |A|.

Let T be a transversal of P which contains M. Then by the above we have R(T) = ν + |T | = ν + |Ω|. The proposition now follows since P is tight and hence R(T) ≡ sgn(P) mod 2. ⊓ ⊔

Corollary 7.2 Let P be the sum of a tight 2-matroid Q and its converse. Then ν(P) is even.

Proof. Let T be a transversal of Ω. Since Q is tight we have

r(T) ≡ r(T̃) + |Ω| mod 2.

Thus R(T) = r(T) + r(T̃) ≡ |Ω| mod 2. Hence sgn(P) ≡ |Ω| mod 2 and the corollary follows by applying Proposition 7.1. ⊓ ⊔

8 Sums of linear 2-matroids

Let Q be a 2-matroid. We say that Q is linear if there exists a base T of Q and a symmetric or skew-symmetric matrix M with rows and columns indexed by T such that for each subtransversal A we have

r(A) = rk(M[Ã_{1}, T − A_{2}]) + |A_{2}|

where A_{1} = A − T, A_{2} = A ∩ T, M[X, Y] is the submatrix of M with rows indexed by X and columns indexed by Y, and rk denotes the matrix rank function. We will refer to M as the matrix representing Q with respect to T. We will denote the row and column spaces of M by sp_{R}(M) and sp_{C}(M), respectively. It follows from [3] that a linear 2-matroid is tight if it can be represented by a skew-symmetric matrix. Though it is not known whether the converse is true, we shall reserve the expression linear tight 2-matroid for a 2-matroid representable by a skew-symmetric matrix. Proposition 4.3.3 of

[3] implies that such a 2-matroid can be represented by a skew-symmetric matrix with respect to every base.

Proposition 8.1 Let Q be a linear 2-matroid, M be a matrix representing Q with respect to some base T and t ∈ T. Then M′ = M[T − t, T − t] is a matrix representing Q^{t} with respect to the base T′ = T − t.

Proof. Let A be a subtransversal in Q^{t}. Put A_{1} = A − T and A_{2} = A ∩ T. Then r(t) = 1 since t ∈ T and

r^{t}(A) = r(A + t) − 1 = rk(M[Ã_{1}, T − A_{2} − t]) + |A_{2} + t| − 1
= rk(M′[Ã_{1}, T′ − A_{2}]) + |A_{2}|.

Thus M′ represents Q^{t} with respect to T′. ⊓ ⊔

Proposition 8.2 Let Q be a linear 2-matroid and D be a subtransversal such that r(D) = |D| − 2 and r(D̃) = |D|. Let {D_{1}, D_{2}, …, D_{m}} be a partition of D such that C_{i} = D − D_{i} is a circuit of Q for all 1 ≤ i ≤ m. Let T be a base of Q which contains D̃ and M be a matrix representing Q with respect to T. Let K_{i} = sp_{R}(M[C̃_{i}, T]). If m ≥ 3 then ∩_{i=1}^{m}K_{i} contains a nonzero vector.

Proof. We use an elementary result from linear algebra given in [14, Lemma 11.3.3]

dim(∩_{i=1}^{m}K_{i}) ≥ ∑_{i=1}^{m} dim(K_{i}) − (m − 1)dim(∪_{i=1}^{m}K_{i}).

Since C_{i} is a circuit of Q contained in T̃, we have

dim(K_{i}) = rk(M[C̃_{i}, T]) = r(C_{i}) = |C_{i}| − 1.

Also

dim(∪_{i=1}^{m}K_{i}) = dim(sp_{R}(M[D, T])) = r(D) = |D| − 2.

Thus

dim(∩_{i=1}^{m}K_{i}) ≥ ∑_{i=1}^{m}(|C_{i}| − 1) − (m − 1)(|D| − 2) = m − 2 ≥ 1,

since m ≥ 3. ⊓ ⊔

Henceforth we will only consider parity systems P which can be expressed as Q+Q̃, where Q is a linear tight 2-matroid. Recall that, if Q = (U, Ω, r) is a 2-matroid, then Q̃ = (U, Ω, r̃), where r̃ is defined by the relation r̃(A) = r(Ã), for every subtransversal A of Ω.

Proposition 8.3 Let Q = (U, Ω, r) be a linear tight 2-matroid and P = Q + Q̃. If P has a nontrivial double flower F, then there exists a linear tight 2-matroid Q′ such that P′ = Q′ + Q̃′ can be obtained from P by a sequence of two switchings and ν(P′) = ν(P) − 2.

Proof. Let D be the nontrivial double circuit in F. Using Proposition 6.4 and symmetry we may suppose that r(D) = |D|−2 and r(D̃) = |D|. Let the principal partition of D be {D_{1}, D_{2}, …, D_{m}}. Let T be a base of Q which contains D̃. Since Q is a linear tight 2-matroid, there exists a skew-symmetric matrix M representing Q with respect to T. Let K_{i} = sp_{R}(M[C_{i}, T]). Using Proposition 8.2 we deduce that ∩_{i=1}^{m}K_{i} contains a nonzero vector d. Let M_{1} be the matrix obtained from M by adding a new first row equal to (0, d) and a new first column equal to (0, −d). Extend the indexing of M with T by indexing the new row and column with d. Then M_{1} is a linear representation of a tight 2-matroid Q_{1} = (U_{1}, Ω_{1}, r_{1}) with respect to a base T_{1} = T +d where U_{1} = U ∪ {d, d̃}, Ω_{1} = Ω ∪ {{d, d̃}} and for each subtransversal A of Ω_{1} we have r_{1}(A) = rk(M_{1}[Ã_{1}, T_{1} − A_{2}]) + |A_{2}| for A_{1} = A − T_{1} and A_{2} = A ∩ T_{1}.

Using Proposition 8.1, we have Q = Q_{1}^{d} and hence P = Q_{1}^{d} + (Q̃_{1})d̃. Let P^{∗} = Qd̃ ; 1 + (Q̃_{1})d̃, and P′ = Qd̃ ; 1 + (Q̃_{1})^{d}. Then by Proposition 6.1, P^{∗} is a switching of both P and P′.

Since d is not the zero vector, r_{1}(d̃) = rk(M_{1}[d, T_{1}]) = 1, and hence we can find a basis for Q_{1} which contains d̃. Choosing a skew-symmetric matrix representing Q_{1} with respect to this basis, we deduce from Proposition 8.1 that Q′ = Qd̃ ; 1 is linear and tight. Thus P′ = Q′ + Q̃′ is linear and tight.

We shall show that P^{∗} compresses F in P. Let C be a circuit of P contained in F. Then C ⊆ T̃ and

R(C) − R^{∗}(C) = r_{1}^{d}(C) − rd̃ ; 1(C) = r(C) − rd̃ ; 1(C).

Now

rd̃ ; 1(C) = r_{1}(C + d̃) − r_{1}(d̃)
= rk(M_{1}[C + d, T_{1}]) − rk(M_{1}[d, T_{1}])
= rk(M[C, T]) − 1
= r(C) − 1,  (5)

since d is a nonzero vector in sp_{R}(M[C, T]) and M is skew-symmetric. Thus R(C) < R^{∗}(C) and P^{∗} compresses F. Using Proposition 5.3 we deduce that ν(P^{∗}) = ν(P) − 1.

Set P_{1} = Q_{1} + Q̃_{1}. We next show that ν(P_{1}) ≤ ν(P). Let M be a maximum matching in P_{1}. Then M̃ is also a maximum matching in P_{1}, and so, by replacing M with M̃ if necessary, we may assume that d ∉ M. If d̃∉ M then

R^{∗}(M) = rd̃ ; 1(M) + r_{1}^{d}(M̃) ≥ R_{1}(M) − 2 = 2|M| − 2.

Thus ν(P^{∗}) ≥ ν(P_{1}) − 2. Since ν(P^{∗}) < ν(P) we have ν(P′) ≤ ν(P) + 1. Using Corollary 7.2 we deduce that ν(P_{1}) ≤ ν(P). If, on the other hand, d̃∈ M then putting M^{∗} = M − d̃ we have,

R^{∗}(M^{∗}) = rd̃ ; 1(M^{∗}) + r_{1}^{d}(M̃^{∗})
= r_{1}(M^{∗} + d̃) − r_{1}(d̃) + r_{1}(M̃^{∗} + d) − r_{1}(d)
= (r_{1}(M) − 1) + (r_{1}(M̃) − 1) = 2|M^{∗}|.

Thus ν(P^{∗}) ≥ ν(P_{1}) − 1 and we deduce as above that ν(P_{1}) ≤ ν(P).

We next show that F is a nontrivial double flower in P_{1}, with the same principal partition as in P. Let B be any subtransversal of P. Then

R(B) = r_{1}^{d}(B) + r_{1}^{d}(B̃)
= r_{1}(B + d) − r_{1}(d) + r_{1}(B̃ + d) − r_{1}(d)
≤ r_{1}(B) + r_{1}(B̃) = R_{1}(B).

Furthermore, it follows from the above inequalities and the submodularity of r_{1} that if R(B) = R_{1}(B), then R(A) = R_{1}(A) for all subtransversals A of P with A ⊆ B. Taking B to be a maximum matching of P, we deduce that B is a matching in P_{1}, and hence ν(P_{1}) ≥ ν(P). Thus ν(P_{1}) = ν(P). Taking B = F, we have R_{1}(F) ≥ R(F) = 2|F | − 2. Strict inequality cannot occur since otherwise P_{1} would have a matching of size |F | − 1 = ν(P) + 1. Thus R_{1}(F) = 2|F | − 2 and F is a double flower in P_{1}. Furthermore if A ⊆ F, then since R_{1}(F) = R(F) we have R_{1}(A) = R(A). Thus F has the same principal partition in P_{1} as in P.

Our next step is to show that

P_{1}^{∗} = (Qd̃ ; 1 ⊕ Q(d̃)) + Q̃_{1}

is a switching of P_{1} which compresses F. The fact that P_{1}^{∗} is a switching of P_{1} follows from Proposition 6.2. Let C be a circuit of P_{1} contained in F. Then

R_{1}(C) − R′_{1}(C) = r(C) − rd̃ ; 1(C) > 0

by (5). Thus P_{1}^{∗} compresses F in P_{1}. Hence, by Proposition 5.3, ν(P_{1}^{∗}) < ν(P_{1}).

Let

P′_{1} = (Qd̃ ; 1 ⊕ Q(d̃)) + ((Q̃_{1})^{d} ⊕ Q(d)) = P′ ⊕ (Q(d̃) + Q(d)) .

Since R′_{1}(d) = 1 = R′_{1}(d̃), we have ν(P′_{1}) = ν(P′). We shall show that ν(P′_{1}) ≤ ν(P_{1}^{∗}). Suppose ν(P′_{1}) > ν(P_{1}^{∗}) and let M be matching of size ν(P_{1}^{∗}) + 1 in P′_{1}. Since R′_{1}(d) = 1 = R′_{1}(d̃), M does not cover {d, d̃}. Thus

2|M| = R′_{1}(M) = rd̃ ; 1(M) + rd̃ ; 1(M̃) = rd̃ ; 1(M) + r_{1}(M̃ + d̃) − r_{1}(d̃)

and rd̃ ; 1(M) = |M| = r_{1}(M̃). This would imply that M is a matching of size ν(P_{1}^{∗})+1 in P_{1}^{∗}. Thus ν(P′_{1}) ≤ ν(P_{1}^{∗}) < ν(P_{1}). Since P′_{1} and P_{1} are both tight, it follows from Corollary 7.2 that ν(P′_{1}) ≤ ν(P_{1})−2. Since ν(P_{1}) = ν(P) and ν(P′_{1}) = ν(P′), we have ν(P′) ≤ ν(P) − 2. Since P′ can be obtained from P by a sequence of two switchings, the proposition follows. ⊓ ⊔

We are now ready to prove our main result.

Theorem 8.4 Let Q be a a linear tight 2-matroid and P = Q + Q̃. Then there exists a linear tight 2-matroid Q′ and a partition {V_{1}, V_{2}, …, V_{m}} of V such that

(a) P′ = Q′ + Q̃′ can be obtained from P by a sequence of 2k switchings,

(b) ν(P) = ν(P′) + 2k,

(c) ν(P′) = ∑_{i=1}^{m} ν(P′[V_{i}]), and

(d) ν(P′[V_{i}]) = |V_{i}| − 1 = ν(P′[V_{i} − v]) for all v ∈ V_{i} and 1 ≤ i ≤ m.

Proof. We use induction on ν(P). If ν(P) = 0 then the theorem is valid taking k = 0, P′ = P, and V_{i} = {v_{i}} for each v_{i} ∈ V. Hence suppose that ν(P) > 0. We apply Theorem 4.3 to P. If P satisfies alternative (a) of Theorem 4.3 then the theorem is valid with P′ = P.

Suppose that P satisfies alternative (b) of Theorem 4.3. Then by Proposition 6.3 there exists a linear tight 2-matroid Q′ such that P′ = Q′ + Q̃′ can be obtained from P by a sequence of two switchings and ν(P′) < ν(P). (To see this we use the fact that Q is linear and tight if and only if it can be represented by a skew-symmetric matrix M. The operation used in Proposition 6.3 is equivalent to replacing the ‘t’-th row and column of M by a zero row and column. Hence the resulting matrix will again be skew-symmetric.) Thus P′ is the sum of a linear tight 2-matroid and its converse and by Corollary 7.2 we have ν(P) and ν(P′) are both even. Since P′ can be obtained from P by two switchings, we have ν(P′) ≥ ν(P)−2. Thus ν(P′) = ν(P)−2. The theorem now follows by applying the inductive hypothesis to P′.

Finally we suppose that P satisfies alternative (c) of Theorem 4.3. Then by Proposition 8.3 there exists a linear tight 2-matroid Q′ such that P′ = Q′ +Q̃′ can be obtained from P by a sequence of two switchings and ν(P′) = ν(P) − 2. The theorem now follows by applying the same argument as in the previous paragraph. ⊓ ⊔

Note Theorem 8.4 implies that ν(P) = |V | − m + 2k. Unfortunately, the theorem is not strong enough to yield a good characterization for this fact since it does not provide a certificate that ν(P′[V_{i}]) ≤ |V_{i}| − 1. A result which is similar to Theorem 8.4 but which does give a good characterization for ν(P) has recently been obtained by Geelen, Iwata and Murota [10]. The proof technique they use is to adapt the algorithm for solving the matroid parity problem of Gabow and Stallman [9] to delta matroids. Thus their approach is to a large extent independent of ours.

References

[1] L. Andersen, A. Bouchet, and B. Jackson, Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus, J. Combin. Theory Ser. B, (1996), pp. 232–246.

[2] A. Bouchet, Unimodularity and circle graphs, Discrete Math., 66 (1987), pp. 203–208.

[3] , Representability of Δ–matroids, Colloquia Societatis Janos Bolyai, 52 (1988), pp. 167–182.

[4] , Coverings and Delta-coverings, in Proceedings of the 4th Conference on Integer Programming and Combinatorial Optimization, Copenhagen, 1995, Springer-Verlag, pp. 228–243.

[5] , Multimatroids I. Coverings by independent sets, SIAM J. Discrete Math., 10 (1997), pp. 626–646.

[6] , Multimatroids II. Orthogonality, minors and connectivity, The Electronic Journal of Combinatorics, 8 (1998), p. R8.

[7] A. Frank, Generalized polymatroid, in Finite and Infinite Sets, L. L. A. Hajnal and V. T. Sós, eds., North-Holland, 1984, pp. 285–294.

[8] A. Frank and E. Tardos, Generalized polymatroids and submodular flows, Math. Programming, 42 (1988), pp. 489–563.

[9] H. N. Gabow and M. Stallman, An augmenting path algorithm for linear matroid parity, Combinatorica, 6 (1986), pp. 123–150.

[10] J. Geelen, S. Iwata, and K. Murota, The linear delta-matroid parity problem. submitted.

[11] R. Hassin, Minimum cost flow with set-constraints, Networks, 12 (1982), pp. 1–22.

[12] L. Lovász, The matroid matching problem, in Algebraic Methods in Graph Theory, L. Lovász and V. T. Sós, eds., North-Holland, 1978, pp. 495–517.

[13] L. Lovász, Matroid matching and some applications, J. Combin. Theory Ser. B, 28 (1980), pp. 208–236.

[14] L. Lovász and M. Plummer, Matching Theory, North–Holland,

Index

q-matroid, 6 2-polymatroid, 7

alternance, 4

base, 6, 10 bases, 1

circuit, 10 compatible, 5

deficiency, 10 delta-matroid, 1 directed transition, 3 double flower, 10 dual, 9

essential, 10 even, 3 evenly directed, 3

feasible sets, 1 flower, 10 free sum, 9

independent set, 6 indexed, 8 intersection problem, 2

linear tight 2-matroid, 17

matching, 7, 8 matroid parity problem, 2 multimatroid, 5

orthogonal, 3, 5, 9

parity system, 7 proper, 10

rank, 2 rank function, 5, 7 reducible, 10 section, 6 separation oracle, 2 separator, 10 skew class, 5 skew pair, 5 subtransversal, 5 sum, 8 support, 8

transversal, 5 trivial, 10 twisting, 2

used, 3