Multimatroids II. Orthogonality, minors and connectivity

André Bouchet Département d’Informatique Université du Maine 72017 Le Mans Cedex France

                        bouchet@lium.univ-lemans.fr

Submitted: May 15, 1997. Accepted: November 20, 1997

Abstract A multimatroid is a combinatorial structure that encompasses matroids, delta-matroids and isotropic systems. This structure has been introduced to unify a theorem of Edmonds on the coverings of a matroid by independent sets and a theorem of Jackson on the existence of pairwise compatible Euler tours in a 4-regular graph. Here we investigate some basic concepts and properties related with multimatroids: matroid orthogonality, minor operations and connectivity. Mathematical Reviews: 05B35

1 Introduction

In a preceding paper [5] we unified a theorem of Jackson [15], on the existence of pairwise compatible Euler tours in a 4-regular graph, with a theorem of Edmonds [12], on the minimum number of independent sets to cover the ground-set of a matroid. For this purpose we introduced a new combinatorial structure, called a multimatroid, which unifies matroids, delta-matroids and isotropic systems. We complete in the present paper and subsequent ones [6, 7] the basic properties of multimatroids.

In Section 2 we review the results already proved in [5]. We also introduce the extended submodularity inequality, equivalent to a kind of supermodularity inequality used by Jackson [15], and we relate it with the bisubmodularity inequality introduced by Kabadi and Chandrasekaran [16]. In Section 3 we introduce an orthogonality relation between matroids, similar to the classical strong map relation, and we show that a multimatroid gives raise to orthogonal matroids. Conversely we derive in Section 4 a multimatroid from a sequence of orthogonal matroids and we retrieve as a particular case the generalized matroids of Tardos [17]. We introduce the minor operations and the separators in Sections 5 and 6. Finally we study some relations between multimatroids and Eulerian graphs in Section 7.

2 A survey

Consider a partition Ω of a finite set U. Each class of Ω is called a skew class. Each pair of distinct elements belonging to the same skew class is called a skew pair. A subtransversal (resp. transversal) of Ω is a subset A of U such that |A ∩ ω| ≤ 1 (resp. |A ∩ ω| = 1) holds for every ω in Ω. Two subtransversals are compatible if their union is also a subtransversal. We denote by S(Ω) (resp. T (Ω)) the set of subtransversals (resp. transversals) of Ω.

A weak multimatroid is a triple Q = (U, Ω, r) with a partition Ω of a finite set U and a rank function r : S(Ω) → N satisfying the three following axioms:

2.1 r(∅) = 0;

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

2.3 Submodularity inequality: r(A) + r(B) ≥ r(A ∪ B) + r(A ∩ B) is satisfied for every pair of compatible subtransversals A and B of Ω;

The following axiom has also to be satisfied in order to derive interesting properties. Then Q is called a multimatroid.

2.4 r(A + x) − r(A) + r(A + y) − r(A) ≥ 1 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}.

If each skew class has cardinality equal to the positive integer q, then Q a qmatroid. An independent set is a subtransversal I of Ω such that r(I) = |I|, a base is a maximal independent set, and a circuit is a subtransversal C of Ω that is not independent and is minimal with this property. We denote by I(Q), B(Q) and C(Q) the collections of independent sets, bases and circuits, respectively.

If A is a subtransversal of Ω, then r(P) is defined for every subset P of A. The axioms 2.1 to 2.3 imply that the restriction of r to the power-set of A is the rank function of a matroid on the set A, denoted by Q[A] and called the submatroid induced on A. The independent sets (resp. circuits) of Q[A] are the independent sets (resp. circuits) of Q included in A. If Q is a 1-matroid, then U is a transversal of Ω and we identify Q to the matroid Q[U]. The inverse construction that associates a 1-matroid to a matroid is obvious. The multimatroid Q may be thought as the aggregation of the submatroids Q[A], when A ranges in the collection of subtransversals of Ω, which gives the name to the structure.

A multimatroid Q will often be given with a projection onto a set V: this is a surjective mapping p : U → V such that p(x_{1}) = p(x_{2}) is satisfied if and only if the elements x_{1} and x_{2} belong to the same skew class. We set Ω_{v} = {v : p(x) = v} for every element v in V, so that Ω = {Ω_{v} : v ∈ V }. We also say that Q is indexed on V. For every transversal T of Ω, the restriction p_{|T} is a bijection from T onto V. The isomorphic image of Q[T] by p_{|T} is called the projection of Q[T] and is denoted by p(Q[T]).

Properties of the independent sets, circuits, and bases

Consider a, possibly weak, multimatroid Q = (U, Ω, r). For every subtransversal A of Ω, the relation

r(A) = max_{I⊆A,I∈I(Q)} |I|

is satisfied. Therefore Q is determined when either I(Q), B(Q) or C(Q) is known. In the two following characterizations the properties (a) to (c) correspond to the axioms 2.1 to 2.3 and the property (d) corresponds to Axiom 2.4. A pair (U, Ω) with a finite set U and a partition Ω is called a partitioned set.

Proposition 2.5 [5] Let (U, Ω) be a partitioned set. A subset I of S(Ω) is the collection of independent sets of a multimatroid on (U, Ω) if and only if the following properties are satisfied:

(a) ∅ ∈ I;

(b) If I ∈ I and J ⊆ I then J ∈ I;

(c) Augmentation: If I, J ∈ I are compatible and |I| < |J| then I + x ∈ I for some x ∈ J \ I;

(d) If I ∈ I and {x, y} is a pair included in a class of Ω disjoint from I, then I + x ∈ I or I + y ∈ I.

Proposition 2.6 [5] Let (U, Ω) be a partitioned set. A subset C of S(Ω) is the collection of circuits of a multimatroid on (U, Ω) if and only if the following properties are satisfied:

(a) ∅ ∉ C;

(b) If C_{1}, C_{2} ∈ C and C_{1} ⊆ C_{2} then C_{1} = C_{2};

(c) Elimination: If C_{1}, C_{2} ∈ C are distinct and compatible and x ∈ C_{1} ∩ C_{2}, then C ⊆ (C_{1} ∪ C_{2}) − x for some C ∈ C;

(d) If C_{1}, C_{2} ∈ C, then C_{1} ∪ C_{2} cannot include precisely one skew pair.

A multimatroid is said to be nondegenerate if each of its skew classes has at least cardinality 2.

Proposition 2.7 The bases of a nondegenerate multimatroid are transversal.

Proof. Suppose indirectly that a base B of a nondegenerate multimatroid is not transversal. Consider a skew class ω disjoint from B. Since Q is nondegenerate we can chose distinct elements x and y in ω. Proposition 2.5(d) implies that B + x or B + y is independent, and so B cannot be a base. ⊓ ⊔

Corollary 2.8 The bases of a q-matroid are transversal if q ≥ 2.

Let U′ be a subset of U. The restriction of Q to U′ is Q[U′] = (U′, Ω′, r′), where Ω′ = {ω ∩ U′ : ω ∈ Ω, ω ∩ U′ ≠ ∅} and r′ is the restriction of r to S(Ω′). Clearly Q[U′] is a multimatroid. We say that Q[U′] is spanning if U′ ∩ ω is nonempty for every skew class ω of Q.

Proposition 2.9 If Q[U′] is a nondegenerate spanning restriction of a (nondegenerate) multimatroid Q, then the bases of Q[U′] are the bases of Q contained in U′.

Proof. Set Q = (U, Ω, r) and Q′ = (U′, Ω′, r′). Every base of Q contained in U′ is obviously a base of Q′. Conversely let B′ be a base of Q′. Then B′ is an independent set of Q contained in U′. Since Q[U′] is nondegenerate, B′ is a transversal of Ω′ by Proposition 2.7. Since Q[U′] is spanning, B′ is also a transversal of Ω. Hence B′ is a transversal independent set of Q, which is a base of Q. ⊓ ⊔

Proposition 2.7 implies that the bases of a nondegenerate multimatroid are equicardinal. It is easy to construct a degenerate multimatroid where this property is false. Proposition 2.9 also is false when it is applied to a restriction that is degenerate or not spanning.

Relation with delta-matroids

The structure of delta-matroid has been independently introduced by Dress and Havel [11], Chandrasekaran and Kabadi [9], and the author [2]. A delta-matroid is a set-system D = (V, F), where V is a finite set and F is a nonempty collection of subsets of V, called the feasible sets or bases, satisfying the following symmetric exchange axiom:

2.10 For F_{1}, F_{2} ∈ F, for v ∈ F_{1}ΔF_{2}, there is w ∈ F_{1}ΔF_{2} with F_{1}Δ{v, w} ∈ F.

Proposition 2.11 [2] A nonempty collection F of subsets of a finite set V is the collection of bases of a matroid if and only if F satisfies the symmetric exchange axiom and the members of F are equicardinal.

Accordingly one identifies a matroid to a delta-matroid with equicardinal bases. For a set system D = (V, F) and a subset X of V, set FΔX = {F ΔX : F ∈ F} and DΔX = (V, FΔX). If F satisfies the symmetric exchange axiom then FΔX also clearly satisfies the same axiom. Hence DΔX is a delta-matroid if D is a deltamatroid. The transformation D ↦ DΔX is called twisting. If D is a matroid and X = V, then DΔX is the matroid dual of D. A paired set is a pair (U, Ω) with a finite set U and a partition Ω of U into pairs.

Theorem 2.12 [5] Let (U, Ω) be a paired set and let T be a transversal of Ω. A nonempty collection B of transversals of Ω is the set of bases of a 2-matroid Q defined on (U, Ω) if and only if {B ∩ T : B ∈ B} is the collection of bases of a delta-matroid.

The delta-matroid of Theorem 2.12 is called the trace of Q on T and is denoted by Q ∩ T. Consider a projection p of Q onto a set V. The isomorphic image of Q ∩ T by p_{|T} is a delta-matroid on the ground-set V, which we denote by p(Q ∩ T). For every transversal T′ of Ω, we easily verify that

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

The subset X = p(T ΔT′) ranges in the power-set of V when T′ ranges in the set of transversals of Ω. Hence, if we fix T and we set D = p(Q∩T), the delta-matroid p(Q∩ T′) = DΔX ranges in the twisting class of D. Conversely the following construction shows that every twisting class of delta-matroids can be derived from an indexed 2-matroid.

Construction 2.13 Let D = (V, F) be a delta-matroid. Set

V_{i} = {v_{i} : v ∈ V }, i = 1, 2,
U = V_{1} + V_{2}
Ω_{v} = {v_{1}, v_{2}}, v ∈ V
Ω = {Ω_{v} : v ∈ V }
F_{i} = {v_{i} : v ∈ F }, F ∈ F, i = 1, 2,
B = {F_{1} ∪ (V_{2} \ F_{2}) : F ∈ F}.

Theorem 2.12 implies that B is the collection of bases of a 2-matroid Q defined on (U, Ω). We have D = p(Q ∩ V_{1}), where p is the projection of Q onto V defined by the relation p(v_{1}) = p(v_{2}) = v for every v in V. We call Q the lift of D.

Eulerian multimatroids

A graph (finite and undirected) G is said to be Eulerian if each vertex has even degree. The number of components of G is denoted by k(G). We consider that each edge e of G is incident to two half-edges h_{1} and h_{2}, each of them incident to one vertex, the ends of e being the vertices incident to h_{1} and h_{2}. The set of half-edges incident to a vertex v is denoted by h(v). A pair of half-edges incident to the same vertex (resp. edge) is called a vertex-transition (resp. edge-transition).

Assume G is Eulerian. A local splitter incident to v is a pair S_{v} = {S′_{v}, S′′_{v}}, where S′_{v} and S′′_{v} are complementary subsets of h(v) having even cardinalities. If S′_{v} and S′′_{v} are nonempty, then S_{v} is said to be proper. A splitter is a set S = {S_{v} : v ∈ W }, where W is a subset of vertices, and S_{v} is a proper local splitter incident to v. The splitter S is complete if W is equal to the set of vertices of G.

To detach the proper local splitter S_{v} is to replace the vertex v by two vertices v′ and v′′ such that h(v′) = S′_{v} and h(v′′) = S′′_{v}. The resulting graph, denoted by G||S_{v}, is still an Eulerian graph. To detach the splitter S is to replace G by G||S = G||S_{v_{1}}||S_{v_{2}}|| ⋯ ||S_{v_{p}}, where (v_{1}, v_{2}, ⋯, v_{p}) is an enumeration of W. (Obviously G||S does not depend on the actual enumeration.) The rank of the splitter S is |S| − k(G||S) + k(G).

Consider a subset U of proper local splitters of G. A splitter contained in U is said to be allowed and the pair G_{U} = (G, U) is called a restricted Eulerian graph. Denote by V (G_{U}) = V the subset of vertices of G that are incident to some local splitter in U and, for each v in V, denote by Ω_{v} the set of local splitters in U incident to v. The set Ω = {Ω_{v} : v ∈ V } is a partition of U and S(Ω) is the set of allowed splitters. Denote by r the restriction of the splitter rank function to S(Ω) and set Q(G_{U}) = (U, Ω, r). It is proved in [5] that Q(G_{U}) is a weak multimatroid. It is a multimatroid if the following skewness condition is satisfied:

2.14 If S_{v} = {S′_{v}, S′′_{v}} and T_{v} = {T′_{v}, T′′_{v}} are distinct allowed local splitters incident to the same vertex v, then |S′_{v} ∩ T′_{v}| is odd.

Note that Q(G_{U}) is naturally indexed on V. We set Q(G) = Q(G_{U}) when all splitters are allowed. The (weak) multimatroid Q(G_{U}) is said to be Eulerian.

The 3-matroid of a 4-regular Graph

In the particular case where G is a 4-regular graph, every proper local splitter is made of two disjoint vertex-transitions. Accordingly it is also called a bitransition. The skewness condition is satisfied because, if {S′_{v}, S′′_{v}} and {T′_{v}, T′′_{v}} are two bitransitions incident to the same vertex, we have |S′_{v} ∩ T′_{v}| = 1. Moreover there are three bitransitions incident to each vertex. Hence Q(G) is a 3-matroid.

Assume G is connected. We describe an Euler tour T by an enumeration of the half-edges h′_{0}h′′_{0}h′_{1}h′′_{1} ⋯ h′_{m−1}h′′_{m−1} such that {h′_{i}, h′′_{i}} is an edge-transition and {h′′_{i}, h′_{i+1}} is a vertex-transition, for 0 ≤ i < m, with the convention h′_{i+1} = h′_{0} when i = m − 1 ^{1}. For each vertex v let T_{v} be the bitransition made of the two vertex-transitions incident to v and belonging to {{h′′_{i}, h′_{i+1}} : 0 ≤ i < m}. Then B(T) := {T_{v} : v ∈ V } is a complete splitter and G||B(T) is a regular graph of degree 2 that admits T as a (unique) Euler tour. We have k(G||B(T)) = k(G) = 1, and so B(T) is a base of the 3-matroid Q(G). Conversely if B is a base of Q(G), then the unique Euler tour T of G||B is also an Euler tour of G such that B = B(T). Hence there is a bijective correspondance between the Euler tours of G and the bases of Q(G).

1An Euler tour is usually defined by means of an alternate sequence of edges and vertices. Note that the graph consisting of one vertex v incident to two loops e_{1} and e_{2}, where e_{i} is incident to the half-edges h′_{i} and h′′_{i}, for i = 1, 2, has two Euler tours described by h′_{1}h′_{2}h′′_{1}h′′_{2} and h′_{1}h′_{2}h′′_{2}h′′_{1}, whereas the usual definition gives only one Euler tour described by ve_{1}ve_{2}.

Theorems of Jackson and Edmonds

Let Q = (Q^{j} : j ∈ J) be a finite family of multimatroids defined on the same partitioned set (U, Ω). Denote by B(Q) the set of families B = (B^{j} : j ∈ J), where B^{j} is a base of Q^{j}. Set Cov(B) = ⋃_{j∈J} B^{j} for every B in B(Q). The rank function of Q is the mapping r, defined for S in S(Ω) by the formula r(S) = ∑_{j∈J} r^{j}(S), where r^{j} is the rank function of Q^{j}.

Theorem 2.15 [5] A finite family Q = (Q^{j} : j ∈ J) of multimatroids defined on the same partitioned set (U, Ω), with the rank function r, satisfies

max_{B∈B(Q)} |Cov(B)| = min_{S∈S(Ω)}(r(S) + |U \ S|),

provided that each skew class ω is such that 3 ≤ |ω| ≤ |J|. A base B of Q and a subtransversal S of Ω satisfying the equality can be efficiently computed.

The theorem still holds when every skew class ω satisfies |ω| = 1: then each Q^{j} is a matroid and the statement is a theorem of Edmonds [12]. However the theorem is false when |J| = 2 and every skew class ω satisfies |ω| = 2: it is shown in [5] that the parity problem for matroids can be transformed into the problem of searching for B in B(Q) maximizing |Cov(B)| with these assumptions.

Consider now a connected 4-regular graph G. We say that a bitransition is covered by an Euler tour T if it belongs to B(T). Set J = {1, 2, 3} and apply Theorem 2.15 to Q = (Q^{1}, Q^{2}, Q^{3}), where Q^{1} = Q^{2} = Q^{3} = Q(G). We find that the maximal number of bitransitions covered by three Euler tours of G is equal to

min_{S∈S(Ω)}(3|V | + 2|S| − 3k(G||S) + 3).

In particular there are three Euler tours that cover all the bitransitions if and only if

2|S| ≥ 3k(G||S) − 1

holds for every splitter S. This result has been originally proved by Jackson [15, 14], and a polynomial algorithm to find three Euler tours covering a maximal number of bitransitions is given in [4].

Extended submodularity inequality

Let Q = (U, Ω, r) be a multimatroid. If A_{1} and A_{2} are subtransversals of Ω then sk(A_{1}, A_{2}) denotes the number of skew pairs included in A_{1}∪A_{2}, and A_{1} ∪^{r} A_{2} denotes the union of A_{1} and A_{2} less the union of the skew pairs included in A_{1}∪A_{2}. A function f : S(Ω) → N is said to satisfy the extended submodularity inequality if

f(A) + f(B) ≥ f(A ∩ B) + f(A ∪^{r} B) + sk(A, B)  (1)

holds for every pair of subtransversals A_{1} and A_{2}.

Theorem 2.16 A triple Q = (U, Ω, r) is a multimatroid if and only if r satisfies the axioms 2.1 and 2.2, and the extended submodularity inequality.

We refer the reader to a paper of Allys [1] for a short proof of that theorem. A kind of extended submodularity inequality, obtained by inverting ≥ in the relation (1), was introduced by jackson [15].

Bisubmodularity inequality

Denote by 3^{V} the set of ordered pairs (P, Q), where P and Q are disjoint subsets of V. For X_{1} = (P_{1}, Q_{1}) and X_{2} = (P_{2}, Q_{2}) in 3^{V}, set

X_{1} ∧ X_{2} = (P_{1} ∩ P_{2}, Q_{1} ∩ Q_{2}),
X_{1} ∨ X_{2} = ((P_{1} ∪ P_{2}) \ (Q_{1} ∪ Q_{2}), (Q_{1} ∪ Q_{2}) \ (P_{1} ∪ P_{2})).

A function f : 3^{V} → R is said to be bisubmodular if

f(X_{1}) + f(X_{2}) ≥ f(X_{1} ∧ X_{2}) + f(X_{1} ∨ X_{2})  (2)

always holds. This inequality has been introduced by Chandrasekaran and Kabadi [9, 16]. They proved that, for a delta-matroid D = (V, F), the function R : 3^{V} → Z, defined by

R(P, Q) = max_{F ∈F}(|P ∩ F | − |Q ∩ (V \ F)|)

is bisubmodular. Moreover the convex hull of the characteristic vectors of the bases of D is the set of vectors x in R^{V} satisfying

x(P) − x(Q) ≤ R(P, Q), (P, Q) ∈ 3^{V} ,

where the notation x(W) stands for ∑_{w∈W} x_{w}. The integral bisubmodular functions, when they are allowed to take infinite values, have also been used by Bouchet and Cunningham [8] to study the jump systems (a generalization of delta-matroids in Z^{V}).

The fact that R is bisubmodular can be retrieved as follows. Use Construction 2.13 to lift D into a 2-matroid Q = (U, Ω, r).

It is easy to verify that R satisfies the bisubmodularity inequality (2) if and only if the function r′ : S(Ω) → Z, defined by the relation

r′(P_{1} ∪ Q_{2}) = R(P, Q) + |Q|,

satisfies the extended submodularity inequality (1). Since the collection of bases of Q is equal to {F_{1} ∪ (V_{2} \ F_{2}) : F ∈ F}, the rank of the subtransversal P_{1} ∪ Q_{2} is such that

r(P_{1} ∪ Q_{2}) = max_{F ∈F} |(P_{1} ∪ Q_{2}) ∩ (F_{1} ∪ (V_{2} \ F_{2})|
= max_{F ∈F}(|P_{1} ∩ F_{1}| + |Q_{2} ∩ (V_{2} \ F_{2})|)
= max_{F ∈F}(|P ∩ F | + |Q ∩ (V \ F)|)
= R(P, Q) + |Q|
= r′(P_{1} ∪ Q_{2}).

The rank function r satisfies the extended submodularity inequality by Theorem 2.16. So we retrieve that R is bisubmodular.

3 Orthogonality relation

Let M_{1} and M_{2} be two matroids on the same set E, with rank functions r_{1} and r_{2}, respectively. The matroid M_{1} is a strong map of the matroid M_{2} if r_{1} − r_{2} is an increasing function, that is

r_{1}(X) − r_{2}(X) ≤ r_{1}(X + x) − r_{2}(X + x)  (3)

holds whenever X is a subset of E and x is an element of E \ X. The matroids M_{1} and M_{2} are orthogonal if M_{1} is a strong map of M_{2}^{∗}. In this section we show that, if T_{1} and T_{2} are disjoint transversals of a multimatroid Q = (U, Ω, r) indexed on a set V, then the projections of the submatroids Q[T_{1}] and Q[T_{2}] are orthogonal.

The next proposition is known when it is expressed in terms of strong maps. We recall its proof for the reader’s convenience. The properties (b) and (c) imply that the orthogonality relation is symmetric.

Proposition 3.1 Let M_{1} and M_{2} be two matroids on the same set E, with rank functions r_{1} and r_{2}, respectively. The following properties are equivalent:

(a) M_{1} is orthogonal to M_{2};

(b) r_{1}(X_{1} + x) − r_{1}(X_{1}) + r_{2}(X_{2} + x) − r_{2}(X_{2}) ≥ 1 holds whenever X_{1} and X_{2} are disjoint subsets of E, and x belongs to E \ (X_{1} ∪ X_{2});

(c) |C_{1} ∩ C_{2}| ≠ 1 holds for every circuit C_{1} of M_{1} and every circuit C_{2} of M_{2}.

Proof. (a) ⟺ (b). Let r_{2}^{∗} be the rank function of M_{2}^{∗}. The relation ([18] p. 35)

r_{2}^{∗}(A) = r_{2}(E \ A) − r_{2}(E) + |A|

is satisfied for every subset A of E. The relation (3), applied to r_{1} and r_{2}^{∗}, implies that M_{1} and M_{2} are orthogonal if and only if

r_{1}(X + x) − r_{1}(X) ≥ r_{2}(E − X − x) − r_{2}(E − X) + 1  (4)

holds for every subset X of E and every element x in E \ X. Set Y = E − X − x. The relation (4) can be written

r_{1}(X + x) − r_{1}(X) + r_{2}(Y + x) − r_{2}(Y) ≥ 1.  (5)

Since r_{1} and r_{2} are submodular functions, the preceding inequality also holds when one replaces X by a subset X_{1} of X and Y by a subset X_{2} of Y. This proves (b). Conversely (b) ⟹ (5) ⟹ (4) ⟹ (3).

(b) ⟹ (c). Assume |C_{1}∩C_{2}| = 1 and consider the unique element x in C_{1}∩C_{2}. Set X_{1} = C_{1} −x and X_{2} = C_{2} −x. One has r_{1}(X_{1} +x) = r_{1}(X_{1}) and r_{2}(X_{2} +x) = r_{2}(X_{2}), which contradict (b).

(c) ⟹ (b). Assume (b) is false. Since r_{1} and r_{2} are increasing functions we have r_{1}(X_{1} + x) = r_{1}(X_{1}) and r_{2}(X_{2} + x) = r_{2}(X_{2}). The element x belongs to the closure of X_{1} in M_{1}. So there is a circuit C_{1} of M_{1} such that x ∈ C_{1} ⊆ X_{1} + x. Similarly there exists a circuit C_{2} of M_{2} such that x ∈ C_{2} ⊆ X_{2} + x. These circuits contradict (c). ⊓ ⊔

We informally represent a multimatroid Q indexed on a set V by drawing V and some transversals of interest as horizontal lines. An element v of V and the elements of Ω_{v} are placed on the same vertical line. We think of the projection associated to the indexing as an orthogonal projection onto V.

Theorem 3.2 If T_{1} and T_{2} are disjoint transversals of a multimatroid Q indexed on a set V, then the projections of Q[T_{1}] and Q[T_{2}] are orthogonal matroids.

Figure 1: Illustration of the proof of Theorem 3.2.

Proof. (See Figure 1) Let r_{i} be the rank function of the projection of Q[T_{i}], for i = 1, 2. According to Proposition 3.1 we have to verify that, for every pair of disjoint subsets X_{1} and X_{2} of V and every element v in V \ (X_{1} ∪ X_{2}), we have

r_{1}(X_{1} + v) − r_{1}(X_{1}) + r_{2}(X_{2} + v) − r_{2}(X_{2}) ≥ 1.  (6)

Let p be the projection of Q onto V and, for i = 1, 2, let Y_{i} be the subset of T_{i} such that p(Y_{i}) = X_{i} and let v_{i} be the element of T_{i} such that p(v_{i}) = v. The inequality (6) is equivalent to

r(Y_{1} + v_{1}) − r(Y_{1}) + r(Y_{2} + v_{2}) − r(Y_{2}) ≥ 1.  (7)

The set Y = Y_{1} + Y_{2} is a subtransversal of Ω and {v_{1}, v_{2}} is a skew pair included in a skew class disjoint from Y. Axiom 2.4 implies

r(Y + v_{1}) − r(Y) + r(Y + v_{2}) − r(Y) ≥ 1.

Since Y_{1} and Y_{2} are subsets of Y and the restriction of r to the powerset of Y is submodular by Axiom 2.3, the last inequality implies (7). ⊓ ⊔

Let D = (V, F) be a delta-matroid. Denote by max(F) and min(F) the collections of (inclusionwise) maximal members and minimal members of F, respectively. The set systems M(D) = (V, max(F)) and m(D) = (V, min(F)) are matroids [2, 3], called the upper matroid and lower matroid of D, respectively.

Theorem 3.3 If D is a delta-matroid, then M(D) is a strong map of m(D).

Proof. Consider the lift of D arising from Construction 2.13. Set F_{i} = {F_{i} : F ∈ F}, for i = 1, 2. The equality B(Q) = {F_{1} ∪ (V_{2} \ F_{2}) : F ∈ F} implies

I(Q) = {P_{1} ∪ Q_{2} : P ⊆ F, Q ∩ F = ∅, for some F ∈ F}.

The independent sets of the submatroid Q[V_{1}] are the independent sets of Q included in V_{1}. Hence

I(Q[V_{1}]) = {P_{1} : P ⊆ F, for some F ∈ F},

which implies

B(Q[V_{1}]) = max(F_{1}).

We similarly find

B(Q[V_{2}]) = max(F_{2}ΔV_{2}).

Therefore Q[V_{1}] and Q[V_{2}] are projected onto the set systems M(D) and m(D)ΔV, respectively. So M(D) and m(D)ΔV are orthogonal matroids by Theorem 3.2. (We also retrieve that M(D) and m(D) are actually matroids.) ⊓ ⊔

4 Free sums of orthogonal matroids

If Q = (U, Ω, r) is a q-matroid indexed on a set V, and (V_{1}, V_{2}, ⋯, V_{q}) is a partition of U into transversals of Ω, then Q[V_{1}], Q[V_{2}], ⋯, Q[V_{q}] are projected onto pairwise orthogonal matroids, by Theorem 3.2. Conversely, given a sequence (M_{1}, M_{2}, ⋯, M_{q}) of orthogonal matroids on the set V, we construct here a q-matroid Q = Q(M_{1}, M_{2}, ⋯, M_{q}) and a partition (V_{1}, V_{2}, ⋯, V_{q}) of the ground-set of Q into transversals such that Q[V_{1}], Q[V_{2}], ⋯, Q[V_{q}] are projected onto M_{1}, M_{2}, ⋯, M_{q}, respectively.

A q-matroid Q = (U, Ω, r) is free if there exists a partition of U into a sequence of transversals (V_{1}, V_{2}, ⋯, V_{q}) such that

r(S) = ∑_{1≤i≤q} r(S ∩ V_{i})

holds for every subtransversal S of Ω.

Proposition 4.1 Let Q = (U, Ω, r) be a q-matroid and let (V_{1}, V_{2}, ⋯, V_{q}) be a partition of U into transversals of Ω. The following properties are equivalent:

(a) Q is free with respect to (V_{1}, V_{2}, ⋯, V_{q});

(b) a subtransversal I of Ω is an independent set of Q if and only if I ∩ V_{i} is an independent set of Q[V_{i}] for every i, 1 ≤ i ≤ q;

(c) a subtransversal C of Ω is a circuit of Q if and only if C is a circuit of Q[V_{i}] for some i, 1 ≤ i ≤ q.

Proof. This readily follows from the definitions. ⊓ ⊔

Construction 4.2 Let M_{1}, M_{2}, ⋯, M_{q} be pairwise orthogonal matroids on the set V, with rank functions ρ_{1}, ρ_{2}, ⋯, ρ_{q}, respectively. Set

V_{i} = {v_{i} : v ∈ V }, 1 ≤ i ≤ q,

U = ⋃_{1≤i≤q} V_{i},

Ω_{v} = {v_{i} : 1 ≤ i ≤ q}, v ∈ V,

Ω = {Ω_{v} : v ∈ V },

P_{i} = {v_{i} : v ∈ P } and r_{i}(P_{i}) = ρ_{i}(P), P ⊆ V, 1 ≤ i ≤ q,

r(S) = ∑_{1≤i≤q} r_{i}(S ∩ V_{i}), S ∈ S(Ω).

Proposition 4.3 The triple Q = (U, Ω, r) arising from Construction 4.2 is a free q-matroid and M_{i} is the projection of Q[V_{i}], for 1 ≤ i ≤ q.

Proof. We have to verify that r satisfies the axioms 2.1 to 2.4. Axiom 2.1 is obvious. Let us verify Axiom 2.4. (The verifications of the two remaining axioms are similar.) We have to prove that

r(S + v_{j}) − r(S) + r(S + v_{k}) − r(S) ≥ 1  (8)

holds for every subtransversal S of Ω and every skew pair {v_{j}, v_{k}} contained in a skew class Ω_{v} disjoint from S.

Figure 2: Verifying Axiom 1.1.4.

For 1 ≤ i ≤ q, let S(i) denote the subset of V that is equal to the projection of S ∩ V_{i} (see Fig. 2). By the construction of Q we have

r(S) = ∑_{1≤i≤q} ρ_{i}(S(i)),  (9)

The subsets S(j) and S(k) are disjoint and do not contain v, and M_{j} and M_{k} are orthogonal. Therefore

ρ_{j}(S(j) + v) − ρ_{j}(S(j)) + ρ_{k}(S(k) + v) − ρ_{k}(S(k)) ≥ 1

is satisfied by Proposition 3.1(b). The equality (9) implies

r(S + v_{j}) = r(S) − ρ_{j}(S(j)) + ρ_{j}(S(j) + v),
r(S + v_{k}) = r(S) − ρ_{k}(S(k)) + ρ_{k}(S(k) + v).

The three preceding relations imply the inequality (8). ⊓ ⊔

We denote by Q(M_{1}, M_{2}, ⋯, M_{q}) the multimatroid arising from Construction 4.2 and we call it the free sum of M_{1}, M_{2}, ⋯, M_{q}. According to Proposition 4.1, a subtransversal I of Ω is an independent set of Q if and only if I ∩V_{i} is an independent set of the submatroid Q[V_{i}], for 1 ≤ i ≤ q. If Q′ is another q-matroid defined on the same partitioned set (U, Ω) and indexed on the same set V, and such that Q′[V_{i}] = Q[V_{i}] for 1 ≤ i ≤ q, then every independent set I′ of Q′ is such that I′ ∩ V_{i} is an independent set of Q′[V_{i}] for 1 ≤ i ≤ q, and so I′ is also an independent set of Q. Hence Q is the ’most free’ q-matroid among all the q-matroids that admit (M_{1}, M_{2}, ⋯, M_{q}) as a sequence of projected submatroids.

If M_{1} and M_{2} are orthogonal matroids on the set V, then the set system D(M_{1}, M_{2}) = (V, F), where

F = {F : F ⊆ B_{1}, F ∩ B_{2} = ∅ for some B_{1} ∈ B(M_{1}) and B_{2} ∈ B(M_{2})}
= {F : F ∈ I(M_{1}), V \ F ∈ I(M_{2})}.

has been introduced by Tardos [17] under the name of generalized matroid. Clearly D(M_{2}, M_{1}) = D(M_{1}, M_{2})ΔV. We also note that D(M, M^{∗}) = M, for every matroid M.

Proposition 4.4 If M_{1} and M_{2} are orthogonal matroids on the set V, then D(M_{1}, M_{2}) is equal to the projection of Q(M_{1}, M_{2}) ∩ V_{1}.

Proof. Let Q = Q(M_{1}, M_{2}) = (U, Ω, r) and let D be the projection of Q ∩ V_{1}. A subset F of V is a feasible set of D if and only if F_{1} ∪ (V_{2} \ F_{2}) is a base of Q. According to Proposition 4.1 (b), this is equivalent to F_{1} and V_{2}\F_{2} being independent in Q[V_{1}] and Q[V_{2}], respectively. Since Q[V_{1}] and Q[V_{2}] are projected onto M_{1} and M_{2}, respectively, this is equivalent to F and V \ F being independent sets of M_{1} and M_{2}, respectively. ⊓ ⊔

Corollary 4.5 [2] Generalized matroids are delta-matroids.

Corollary 4.6 Let Q = Q(M, M^{∗}) = (U, Ω, r) be the free sum of two dual matroids on the set V. The submatroids Q[V_{1}] and Q[V_{2}] are projected onto M and M^{∗}, respectively. A transversal B of Ω is a base of Q if and only if B ∩ V_{i} is a base of Q[V_{i}], for i = 1, 2.

5 Minors

Consider a multimatroid Q = (U, Ω, r) and a subtransversal X of Ω. Set

Ω′ = {ω ∈ Ω : ω ∩ X = ∅},
U′ = ⋃_{ω∈Ω′} ω,
r′(S) = r(S + X) − r(X), S ∈ S(Ω′).

The triple (U′, Ω′, r′) is a multimatroid, which we denote by Q|X and call a minor of Q. If X and Y are disjoint compatible subtransversals, then Q|X|Y = Q|Y |X = Q|(X ∪ Y). The minor Q|X is proper if X ≠ ∅, elementary if |X| = 1. If |X| > 1, then Q|X = Q|x_{1}|x_{2}| ⋯ |x_{p}, where x_{1}, x_{2}, ⋯, x_{p} is any enumeration of the elements of X.

Proposition 5.1 Let Q(G_{U}) be an Eulerian multimatroid. For every allowed splitter X we have

Q(G_{U})|X = Q(G′_{U′}),  (10)

where G′ = G||X and U′ is the set of allowed local splitters incident to the vertices of G′.

Proof. The multimatroids Q_{1} = Q(G_{U})|X and Q_{2} = Q(G′_{U′}) are defined on the same partitioned set (U′, Ω′). Let r be the rank function of Q(G_{U}) and let r_{i} be the rank function of Q_{i}, for i = 1, 2. For every subtransversal S of Ω′ we have

r_{1}(S) = r(S + X) − r(X)
= |S + X| − k(G||(S + X)) + k(G) − |X| + k(G||X) − k(G)
= |S| − k((G||X)||S) + k(G||X)
= r_{2}(S).
⊓ ⊔

When G is a 4-regular graph, the graph G′ = G||X in the relation (10) has vertices of degree 2 that we may wish to erase in order to obtain another 4-regular graph. In general to erase a vertex w of degree 2 in a graph H is to delete w as well as the edges and half-edges incident to w then, if there remains two half-edges h_{1} and h_{2} that are no longer incident to an edge (which happens if w was not incident to a loop in H), to add a new edge and make it incident to h_{1} and h_{2}. To open X in G is to construct the detachment G||X, then to successively erase the vertices of degree 2. The new graph, denoted by G|X, is a 4-regular graph if G is 4-regular. We have k(G|X) = k(G||X) − k_{2}, where k_{2} is the number of components of G||X regular of degree 2, and Q(G||X) = Q(G|X). Set G_{U}|X = (G|X)_{U′}, where U′ is the set of allowed local splitters incident to the vertices of G|X. Then the relation (10) can be written

Q(G_{U})|X = Q(G_{U}|X).  (11)

For a matroid M on the set V and an element v of V, we denote by M \ v and M/v the matroids obtained by deleting v and by contracting v, respectively.

Proposition 5.2 Let Q = Q(M_{1}, M_{2}, ⋯, M_{q}) be a free sum of orthogonal matroids on a set V. For every v in V and every j in {1, 2, ⋯, q}, we have Q|v_{j} = Q(M′_{1}, M′_{2}, ⋯, M′_{q}) with

M′_{j} = M_{j}/v,
M′_{k} = M_{k} \ v, k ∈ {1, 2, ⋯, q} − j.

Proof. Set (U′, Ω′, r′) = Q|v_{j}. We may assume j = 1. For every subtransversal S of Ω′ we have

r′(S) = r(S + v_{1}) − r(v_{1})
= r_{1}(S_{1} + v_{1}) − r_{1}(v_{1}) + ∑_{2≤j≤q} r_{j}(S_{j})
= r′_{1}(S_{1}) + ∑_{2≤j≤q} r′_{j}(S_{j}),

where S_{j} is the projection of S ∩ V_{j}, r_{j} is the rank function of M_{j}, r′_{j} is the rank function of M_{j} \ v if j ≠ 1 and r′_{1} is the rank function of M_{1}/v. ⊓ ⊔

Corollary 5.3 Let M be a matroid on a set V and let Q = Q(M, M^{∗}). For every element v in V we have

Q|v_{1} = Q(M/v, M^{∗} \ v) = Q(M/v, (M/v)^{∗}),
Q|v_{2} = Q(M \ v, M^{∗}/v) = Q(M \ v, (M \ v)^{∗}).

An element x in U is singular if r(x) = 0. A skew class that contains a singular element is singular.

Proposition 5.4 A singular skew class contains precisely one singular element.

Proof. If there were distinct singular elements, x and y, in the same skew class of a multimatroid with rank function r, we should have

r(x) − r(∅) + r(y) − r(∅) = 0,

contradicting Axiom 2.4. ⊓ ⊔

Proposition 5.5 If a skew class ω of a multimatroid Q is singular, then the elementary minor Q|x does not depend from the choice of z in ω, namely Q|z = Q[U \ ω].

Proof. Let r be the rank function of Q and let x be the singular element of ω. For every subtransversal S, disjoint from ω, the submodularity inequality 2.3 implies

r(S + x) − r(S) ≤ r(x) − r(∅) = 0.

Since r(x) = 0, it follows

r(S + x) − r(x) = r(S).  (12)

For every element y in ω − x, Axiom 2.4 implies

r(S + y) − r(S) + r(S + x) − r(S) ≥ 1.

Since r(y) = 1, by Proposition 5.4, this implies

r(S + y) − r(y) = r(S).  (13)

The equations (12) and (13) imply Q|x = Q|y = Q[U \ ω]. ⊓ ⊔

Theorem 5.6 For every minor Q|X of a nondegenerate multimatroid Q there exists an independent set Y such that Q|Y = Q|X.

Proof. We use induction on |X|. The property is trivial if |X| = 0. Assume |X| > 0 and consider an element x in X. Set Q′ = Q|x and X′ = X − x. By induction there exists an independent set Y′ of Q′ such that Q′|Y′ = Q′|X′. This implies

Q|X = Q|x|X′ = Q|x|Y′ = Q|(Y′ + x).

If Y′ + x is an independent set of Q the proof is done. Assume Y′ + x is dependent and denote by r′ the rank function of Q′. We have

r(Y′ + x) ≤ |Y′|

and

|Y′| = r′(Y′) = r(Y′ + x) − r(x).

These relations imply r(x) = 0, and so the skew class ω that contains x is singular. Consider an element y in ω −x, which exists because Q is nondegenerate. Proposition 5.4 implies r(y) = 1, and Proposition 5.5 implies Q′ = Q|x = Q|y. Set Y = Y′ + y. We have

Q|X = Q|x|X′ = Q′|X′ = Q′|Y′ = Q|y|Y′ = Q|Y

and

r(Y) = r(Y′ + y) = r′(Y′) + r(y) = |Y′| + 1 = |Y |,

which completes the proof. ⊓ ⊔

The following result is often called the scum theorem [10]

Corollary 5.7 For every minor M′ of a matroid M there exists an independent set I of M and an independent set J of M^{∗}, such that I ∩ J = ∅ and M′ = M/I \ J.

Proof. Consider the free sums Q = Q(M, M^{∗}) and Q′ = Q(M′, M^{′∗}). Corollary 5.3 implies that Q′ is a minor of Q. Theorem 5.6 implies the existence of an independent set Y of Q such that Q′ = Q|Y. For i = 1, 2, the set Y ∩ V_{i} is an independent set of Q[V_{i}]. The projection I of Y ∩ V_{1} is an independent set of M, and the projection J of Y ∩ V_{2} is an independent set of M^{∗}. By using Corollary 5.3 again, we have

Q(M′, M^{′∗}) = Q|Y
= Q|(Y ∩ V_{1})|(Y ∩ V_{2})
= Q(M/I \ J, M^{∗} \ I/J),

and so M′ = M/I \ J. ⊓ ⊔

6 Separators

Let us recall that a separator of a matroid M on the set V, with rank function r, is a subset W of V such that

r(S) = r(S ∩ W) + r(S \ W)  (14)

is satisfied for every subset S of V. We similarly define a separator of the elements of a multimatroid Q = (U, Ω, r) as a subset W of U that is a union of skew classes and satisfies the equality (14) for every subtransversal S of Ω. If Q is indexed on a set V, we define a separator of the indices as a subset W of V such that ⋃_{v∈W} Ω_{v} is a separator of the elements. When using the term separator, without specifying the elements or the indices, we implicitly refer to a separator of the indices if Q is indexed, and to a separator of the elements if no indexing of Q is specified. The multimatroid Q is connected if it has no proper separator.

There is also a weaker notion of separator that has some interest: a subset W ⊆ U is a weak separator if the equality (14) holds for every subtransversal S of V (but W is not necessarily a union of skew classes). For example in a free sum Q(M_{1}, M_{2}, ⋯, M_{q}) of orthogonal matroids defined on a set V, the transversals V_{1}, V_{2}, ⋯, V_{q} are weak separators.

Proposition 6.1 The set of (weak) separators is closed under union, intersection, and complementation.

Proof. This readily follows from the definition and the submodularity of the rank function. ⊓ ⊔

We recall the following basic relation between the separators and the circuits of a matroid.

Theorem 6.2 A subset W of the elements of a matroid M is a separator if and only if every circuit of M is either included in W or disjoint from W.

Corollary 6.3 Let Q = (U, Ω, r) be a multimatroid and let X be a subset of U. The following properties are equivalent:

(a) X is a weak separator of Q; (b) X ∩ T is a separator of the submatroid Q[T] for every transversal T of Ω;

(c) every circuit of Q is either included in X or disjoint from X.

Proof. The equivalence of (a) and (b) readily follows from the definition. The equivalence of (b) and (c) is a simple consequence of Theorem 6.2. ⊓ ⊔

Although the class of connected matroids is clearly equal to the class of connected 1-matroids, many basic properties of connected matroids cannot be generalized to arbitrary multimatroids. For example a matroid is connected if and only if every pair of elements of that matroid belong to the same circuit. That property no longer holds for a 2-matroid Q = (U, Ω, r). Indeed let U = {a, a′, b, b′, c, c′, d, d′}, let Ω = {aa′, bb′, cc′, dd′}, and let the set of circuits be equal to {a′b′cd, a′bcd′, ab′c′d, abc′d′} (we omit the braces around the elements of a powerset). There exists no proper subset W of U such that every circuit is either included in W or disjoint from W. Accordingly Q is connected. However there is no circuit including {a′, c′}. In a subsequent paper [6] we show that some basic properties of connected matroids can be generalized to the subclass of tight multimatroids.

7 Cyclic splitters

The cyclic splitters are particular splitters associated to the cycles of an Eulerian graph G. We show that the circuits of Q(G) are the minimal nonempty cyclic splitters. We define a transformation of G that preserves the cyclic splitters and we prove the existence of a connected Eulerian graph G′ such that Q(G′) = Q(G).

Definitions and basic properties

Let Γ be a subset of edges of G. The set of half-edges incident to the edges in Γ is denoted by h(Γ). We recall that the set of half-edges incident to a vertex v is denoted by h(v). The set Γ is a cycle of G if |h(Γ) ∩ h(v)| is even for every vertex v. Set V (Γ) = {v ∈ V : ∅ ≠ h(Γ) ∩ h(v) ≠ h(v)} and S(Γ) = {S(Γ)_{v} : v ∈ V (Γ)}, where S(Γ)_{v} = {h(Γ) ∩ h(v), h(v) \ h(Γ)}. So Γ is a cycle if and only if S(Γ) is a splitter. Then we call S(Γ) a cyclic splitter. Figure 3 depicts a cycle Γ, drawn with thick edges, and the detachment G||S(Γ). The following property is a direct consequence of the definitions.

Proposition 7.1 If Γ is a cycle of an Eulerian graph G, then the edge-set of every component of G||S(Γ) is contained in Γ or disjoint from Γ.

A bicoloring of the half-edges, say in black and white, is compatible with a splitter S = {S_{v} : v ∈ W }, S_{v} = {S′_{v}, S′′_{v}}, if the three following conditions are satisfied :

7.2 two half-edges incident to a same edge have the same color;

Figure 3: Detachment of a cyclic splitter

7.3 two half-edges incident to a same vertex v in V − W have the same color;

7.4 two half-edges incident to a same vertex v in W have the same color if and only if both belong to either S′_{v} or S′′_{v}.

Proposition 7.5 A splitter S = {S_{v} : v ∈ W } is cyclic if and only if there is a bicoloring of the half-edges compatible with S.

Proof. If S = S(Γ), for some cycle Γ, then we obtain a compatible bicoloring by letting the half-edges in h(Γ) be black and the other half-edges be white. Conversely if there is a compatible bicoloring , then the subset Γ of the edges incident to the black half-edges is a cycle such that S = S(Γ). ⊓ ⊔

If H is a component of G||S, where S is a cyclic splitter, and if we consider a coloring of the half-edges compatible with S, then Proposition 7.1 implies that the half-edges incident to H have the same color, which we call the color of H.

Circuits of Q(G)

In view of the following properties we point out that a circuit of Q(G) is not to be confused with a circuit of G. The former is a splitter of G and the latter is a set of edges of G.

Proposition 7.6 Let G be an Eulerian graph. A nonempty cyclic splitter S of G is dependent in Q(G).

Proof. Set S = {S_{v} : v ∈ W }, S_{v} = {S′_{v}, S′′_{v}}. Consider a vertex v in W and the components X′ and X′′ of G||S that contain S′_{v} and S′′_{v}, respectively. In a bicoloring of the half-edges compatible with S, the half-edges in S′_{v} have not the same color as the half-edges in S′′_{v}, by the condition 7.4. Hence X′ and X′′ have distinct colors, and so X′ ≠ X′′. If we reconstruct G from G||S by identifying each pair of vertices of G||S corresponding to the same vertex of G, the components X′ and X′′ are merged into the same component. Accordingly k(G||S) > k(G), and so S is dependent in Q(G). ⊓ ⊔

Theorem 7.7 Let G be an Eulerian graph. The minimal nonempty cyclic splitters of G are the circuits of Q(G).

Proof. By the preceding proposition we know that every minimal nonempty cyclic splitter of G includes a circuit of Q(G). It remains to prove that every circuit C of Q(G) is a cyclic splitter.

Set C = {C_{v} : v ∈ W }, C_{v} = {C′_{v}, C′′_{v}}, and denote by v′ and v′′ the vertices of G||C such that h(v′) = C′_{v} and h(v′′) = C′′_{v}. Since C is a circuit of Q(G) we have k(G||C) − k(G) = 1 and k(G||C) = k(G||(C − C_{v})) + 1 for every v in W.

Claim. For every v in W, v′ and v′′ are in different components of G||C.

Proof. By identifying v′ and v′′ in G||C we obtain G||(C − C_{v}). No component of G||C is modified after this identification, except for the components X′ and X′′ containing v′ and v′′, respectively, which are merged together. If these components are equal, then the number of components is not modified by the identification, which contradicts the equality k(G||C) = k(G||(C − C_{v})) + 1. ⊓ ⊔

Let G^{1}, G^{2}, ⋯, G^{k} be the components of G and, for 1 ≤ j ≤ k, let C^{j} = {C_{v} : v ∈ W ∩ V (G^{j})}. The detachment G||C can be constructed by successively constructing each detachment G^{j}||C^{j}, for j = 1, 2, ⋯, k. Therefore

1 = k(G||C) − k(G) = ∑_{j=1}^{j=k}(k(G^{j}||C^{j}) − 1).

Accordingly we may assume G^{j}||C^{j} is connected, for 2 ≤ j ≤ k, and G^{1}||C^{1} has two components, say X′ and X′′.

Each subset C^{j}, 2 ≤ j ≤ k, is empty. Indeed if there was a local splitter C_{v} in C^{j}, then v′ and v′′ would be vertices of G^{j}||C^{j}, which is a component of G||C, contradicting the claim. So, for every v in W, the vertices v′ and v′′ belong to G^{1}||C^{1}. Moreover they do not belong to the same component of G||C according to the claim. Hence we may assume C′_{v} is a subset of half-edges of X′ and C′′_{v} is a subset of half-edges of X′′. Then, by coloring the half-edges of X′ in black and all the other half-edges in white, we obtain a bicoloring compatible with C. ⊓ ⊔ Corollary 7.8 If two Eulerian graphs G′ and G′′ have the same cyclic splitters, then Q(G′) = Q(G′′).

Breaking 2-cuts

Let {V^{1}, V^{2}} be a bipartition of the vertex-set of G. The set C of edges of G that have one end in V^{1} and one end in V^{2} is called a k-cut if |C| = k. Since G is Eulerian, k is even. To break a 2-cut {e_{1}, e_{2}} is to construct the graph depicted in Figure 4. Formally, denoting by h_{i}^{j} the half-edge incident to e_{i} and V^{j}, we replace e_{1} and e_{2} by two edges e^{1} and e^{2}, where e^{j} is incident to h_{1}^{j} and h_{2}^{j}, for j = 1, 2. So we split the component of G that contains e_{1} and e_{2} into a component that contains e^{1} and a component that contains e^{2}. The reverse operation, which consists in replacing {e^{1}, e^{2}} by {e_{1}, e_{2}}, is called glueing along {e^{1}, e^{2}}.

Figure 4: Breaking a 2-cut and glueing along a pair of non-connected edges

Proposition 7.9 If an Eulerian graph G′ is derived from another one G by either breaking a 2-cut or glueing a pair of nonconnected edges, then G and G′ have the same cyclic splitters.

Proof. Consider a cyclic splitter S of G and a bicoloring of the half-edges compatible with S. The same bicoloring, with respect to G′, still satisfies the conditions 7.3 and 7.4. If it also satisfies Condition 7.2, with respect to G′, then S is a cyclic splitter of G′, and the property is proved. In the other case we have to modify the bicoloring in order to prove the property. Let Γ be the cycle of G incident to the black edges.

Case 1: Breaking a 2-cut {e_{1}, e_{2}}. Since the intersection of a cut with a cycle has an even cardinality, {e_{1}, e_{2}} is either contained in Γ or disjoint from Γ. In both cases the four half-edges incident to e_{1} and e_{2} have the same color. These half-edges are also incident to e^{1} and e^{2} in G′. Therefore Condition 7.2 is satisfied.

Case 2: Glueing along a pair of nonconnected edges {e^{1}, e^{2}}. By Condition 7.2, with respect to G, the half edges incident to e^{1} have the same color χ_{1}, and the halfedges incident to e^{2} have the same color χ_{2}. If χ_{1} = χ_{2} Condition 7.2 still holds with respect to G′. If χ_{1} ≠ χ_{2} we exchange the colors black and white on the half-edges of the component of G that contain the edge e^{2}. We have still a bicoloring compatible with S, and χ_{1} = χ_{2}. ⊓ ⊔

Corollary 7.10 For every Eulerian graph there exists a connected Eulerian graph that admits the same splitter rank function.

Proof. Delete the vertices of null degree, which play no role in the cyclic splitters. Then make successive glueings until obtaining only one component. ⊓ ⊔

Figure 5: Switching a 4-cut, τ = (1 4) (2 3).

Switching a 4-cut

Let C = {e_{ii} : i ∈ I}, I = {1, 2, 3, 4}, be a 4-cut of G defined by the bipartition {V^{1}, V^{2}} of the vertex-set and let τ be a fixed point free involution on I. (Thus τ is a permutation of I such that τ(i) ≠ i and τ^{2}(i) = i hold for all i in I. We note that precisely three such involutions exist.) Denote by h_{i}^{j} the half-edge incident to e_{ii} and V^{j}, for all i in I and all j in {1, 2}. For each i in I, remove the edge e_{ii} and replace it by an edge e_{iτ(i)} incident to h_{i}^{1} and h_{τ(i)}^{2}. This transformation, called a switching, is illustrated in Figure 5. By performing again the same switching one regains the original graph.

Proposition 7.11 If an Eulerian graph G′ is derived from another one G by switching a 4-cut, then G and G′ have the same cyclic splitters.

Proof. The proof is similar to the preceding one and we use the same notation. The cut C contains an even number of edges of Γ, say p. If p = 0 or p = 4, the half-edges incident to C have the same color, and so the coloring is still compatible in G′. If p = 2 and C ∩ Γ = {e_{ii}, e_{τ(i)τ(i)}}, for some i in I, again the coloring is compatible in G′. In the remaining case we may assume without loss of generality τ = (1 4) (2 3), the half-edges incident to e_{11} and e_{22} are colored in black, the half-edges incident to e_{33} and e_{44} are colored in white. The coloring of the half-edges, with respect to G′, is illustrated in Figure 6. We obtain a coloring compatible in G′ by exchanging the colors black and white on the half-edges incident to V^{2}. ⊓ ⊔

Question. Given two connected Eulerian graphs G and G′ without 2-cut and such that Q(G) = Q(G′), is it true that G′ can be derived from G by a succession of 4-cut switchings? This has been proved when G and G′ are 4-regular by Ghier [13].

Figure 6: Exchanging the colors of the half-edges incident to V^{2}.

References

[1] L. Allys, Extended submodularity inequality. Submitted.

[2] A. Bouchet, Greedy algorithm and symmetric matroids, Math. Programming, 38 (1987), pp. 147–159.

[3] , Maps and Δ-matroids, Discrete Math., 78 (1989), pp. 59–71.

[4] , Compatible Euler tours and supplementary Eulerian vectors, Europ. J. Combin., 514 (1993), pp. 513–520.

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

[6] , Multimatroids III. Tightness and fundamental graphs. Submitted, 1997.

[7] , Multimatroids IV. Chain-group representations. To appear in Linear Algebra and its Applications., 1997.

[8] A. Bouchet and W. H. Cunningham, Delta–matroids. jump systems, and bisubmodular polyhedra, SIAM J. Discrete Math., 8 (1995), pp. 17–32.

[9] R. Chandrasekaran and S. N. Kabadi, Pseudomatroids, Discrete Math., 71 (1988), pp. 205–217.

[10] H. H. Crapo and G. C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, The M.I.T. Press, Cambridge, Massachussets, 1970.

[11] A. Dress and T. Havel, Some combinatorial properties of discriminants in metric vector spaces, Advances in Mathematics, 62 (1986), pp. 285–312.

[12] J. Edmonds, Lehman’s switching game and a theorem of Tutte and Nash-Williams, J. Res. Bur. Standards Sect. B, 69B (1965), pp. 73–77.

[13] L. Ghier, Double occurence words with the same alternance graph, Ars Combinatoria, 36 (1993), pp. 57–64.

[14] B. Jackson, A characterization of graphs having three pairwise compatible Euler tours, J. Combin. Theory Ser. B, 53 (1991), pp. 80–92.

[15] , Supplementary Eulerian vectors in isotropic systems, J. Combin. Theory Ser. B, 53 (1991), pp. 93–105.

[16] S. N. Kabadi and R. Chandrasekaran, On totally dual integral systems, Discrete Applied Math., 26 (1990), pp. 87–104.

[17] E. Tardos, Generalized matroids and supermodular colourings, Colloquia Societatis Janos Bolyai, 40 (1982), pp. 359–381.

[18] D. Welsh, Matroid Theory, Academic Press, 1976.