Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 37 (1996), No. 1, 161-198.

A Unified Treatment of the Theories of Matroids with Coefficients and of Δ-Matroids with Coefficients

Walter Wenzel*

University of Kiel, Mathematisches Seminar Ludewig-Meyn-Straße 4, D-24098 Kiel, BRD

Abstract. The representation theory of matroids and that of even Δ-matroids have much in common. In this paper, a unified representation theory is developed which will also encompass the theory of matroids with coefficients and that of Δ-matroids with coefficients. This is established by identifying set systems with special cosets in Coxeter groups as was done by I.M.Gelfand and V.V.Serganova in their work concerning (W, P)-matroids; however, in order to extend the theory of matroids with coefficients it was necessary to study a slightly different concept, named a Combinatorial (W; P; U)-geometry which is defined for a Coxeter group W, a subset P of its generating involutions, and some subgroup U of W containing P. Keywords and phrases: Representation theory of matroids, matroids with coefficients, Grassmann-Plücker relations, Δ-matroids, skew-symmetric matrices, Pfaffian forms, the base graph of a matroid, antipodal graphs, convexity in graphs, Coxeter groups. MSC 1991: 05B25, 05B35, 20B25, 51D20 (Primary)

15A03, 15A15, 51D10, 51F15, 52A30, 68E10 (Secondary)

1. Introduction

In 1986, A. Dress introduced the concept of a matroid with coefficients in a fuzzy ring K in order to establish a framework for a unified theory of representable, orientable, valuated, etc. matroids ([6]). In [8], it was shown that matroids with coefficients can be defined in terms of Grassmann-Plücker maps, and in [9] we proved many representation theorems which demonstrate why representable and orientable matroids show very similar aspects.

* This work was done while the author stayed at the University of Augsburg.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1996 Heldermann Verlag, Berlin

162 W. Wenzel: A Unified Treatment of the Theories of Matroids …

In 1987, A. Bouchet introduced the concept of a Δ-matroid obtained by weakening the structure of a matroid ([3]). Representability problems for Δ-matroids are studied in [4] and [5], and it turned out (cf. [4, §4]) that for every field K a matroid M is representable over K if and only if it is representable over K as a Δ-matroid by some skew-symmetric matrix. This result suggested the existence of an identity concerning skew-symmetric matrices which should be quite similar to the Grassmann-Plücker identity. Indeed, by studying the Pfaffians of skew-symmetric matrices it turned out (cf. [22, Theorem 2.2]) that for any n ∈ N, E := {1, ..., n}, and for any field K there is a canonical one-to-one correspondence between the skew-symmetric n × n-matrices A = −A^{T} with coefficients in K and maps p : P(E) → K satisfying p(∅) = 1 and the following two axioms:

(P1) For any I ⊆ E with odd cardinality #I one has p(I) = 0.

(P2) For I_{1}, I_{2} ⊆ E and I_{1}ΔI_{2} := (I_{1} ∪ I_{2}) \ (I_{1} ∩ I_{2}) = {i_{1}, ...i_{ℓ}} with i_{j} < i_{j+1} for 1 ≤ j ≤ ℓ − 1 one has

∑_{j=1}^{ℓ} (−1)^{j} · p (I_{1}Δ {i_{j}}) · p (I_{2}Δ {i_{j}}) = 0.

Such maps are called Pfaffian maps. For a skew-symmetric matrix A = (a_{ij})_{i,j∈E} the

associated map p is defined in terms of its Pfaffian Pf ; that is, p (I) = Pf ((a_{ij})_{i,j∈I}). This result proved to be essentially a consequence of the fact that the map p induced by some skew-symmetric matrix A via its Pfaffian form satisfies (P2) – an identity unknown before except in the particular case #I_{1} = 1 or #I_{2} = 1. The significance of this identity lies in the fact that it has allowed to establish a theory of Δ-matroids with coefficients in any fuzzy ring K (cf. [23]) such that in the special case of K being a field the Δ-matroids with coefficients in K are the Δ-matroids representable by a skew-symmetric matrix.

The conspicuous similarity between the well-known Grassmann-Plücker identities and the relations (P2) suggests the existence of a unified representation theory which should encompass the theory of matroids with coefficients and that of Δ-matroids with coefficients; the present paper is devoted to this subject. As in the work of I.M.Gelfand and V.V. Serganova concerning (W, P)-matroids which unify – among other combinatorial structures – matroids, Δ-matroids and a large class of greedoids (cf. [14], [15]), set systems are identified with special cosets in Coxeter groups. In order to extend the theory of matroids with coefficients and that of representable Δ-matroids, it was necessary to introduce the slightly different concept of a combinatorial (W; P; U)-geometry; however, as it turned out in [25, §4], for many important classes of W and P we consider the same structures. While I.M.Gelfand and V.V.Serganova reformulated the exchange condition for bases in matroids into some “minimality condition” which is related to word problems in Coxeter groups and to the Greedy Algorithm, I have tried to generalize the strong exchange condition for bases in matroids. This approach is built up mainly graph theoretically; more precisely, the strong exchange axiom is reformulated in the framework of antipodal graphs. While the combinatorial framework is already established in [25], the present paper concerns the representation theory of combinatorial (W; P; U)-geometries.

Technically, this paper is organized as follows:

In Section 2, we recall the fundamental concepts of matroids with coefficients, of Δ-matroids with coefficients and of antipodal graphs.

In Section 3, we provide the technical tools to establish the theory of (W; P; U)- matroids with coefficients for any Coxeter group W, any subset P of its generating involutions and specified subgroups U of W containing P. The axioms are chosen so that, on the one hand, at least the matroids with coefficients and the Δ-matroids with coefficients are included (cf. 5.), and that, on the other hand, many results concerning matroids with coefficients remain true in this more general framework.

Section 4 is devoted to the study of equivalent representations of a given combinatorial (W; P; U)-geometry, that is, those which induce the same (W; P; U)-matroid with coefficients. To this end, we shall make use of the extension of Maurer’s homotopy theorem for ordinary matroids as developed in [19] to combinatorial (W; P; U)-geometries as established in [25, §5].

Finally, in Section 5, we study examples. In particular, it is shown that matroids with coefficients as well as Δ-matroids with coefficients fit into the theory developed in the present paper.

In a forthcoming paper (cf. [27]), I shall study the geometric algebra of a combinatorial (W; P; U)-geometry by generalizing the concept of the Tutte group of an ordinary matroid as introduced in [11]. A second, equivalent definition of (W; P; U)-matroids with coefficients will then be derived.

Acknowledgement: I would like to thank Andreas Dress for kindly suggesting to me the idea of connecting the theories of matroids with coefficients, of Δ-matroids and of (W, P)-matroids.

2. Preliminaries

In this section, we recall some basic definitions and results concerning matroids with coefficients, Δ-matroids with coefficients and antipodal graphs. We first state the definition of fuzzy rings which serve as coefficient domains for matroids and Δ-matroids.

Definition 2.1. A fuzzy ring K = (K; + ; ·; ε; K_{0}) consists of a set K together with two compositions:

\begin{matrix}+ : & K × K → K : (κ, λ) ↦ κ + λ and \\ · : & K × K → K : (κ, λ) ↦ κ · λ, \end{matrix}

a specified element ε ∈ K and a specified subset K_{0} ⊆ K such that the following axioms hold: (FR0) (K, +) and (K, ·) are abelian semigroups with neutral elements 0 and 1, respectively; (FR1) 0 · κ = 0 for all κ ∈ K; (FR2) α · (κ_{1} + κ_{2}) = α · κ_{1} + α · κ_{2} for all κ_{1}, κ_{2} ∈ K and α ∈ K^{∗} := {β ∈ K | 1 ∈ β · K},

the group of units in K; (FR3) ε^{2} = 1; (FR4) K_{0} + K_{0} ⊆ K_{0} , K · K_{0} ⊆ K_{0} ; 0 ∈ K_{0} ; 1 ∉ K_{0} ; (FR5) for α ∈ K^{∗} one has 1 + α ∈ K_{0} if and only if α = ε; (FR6) κ_{1}, κ_{2}, λ_{1}, λ_{2} ∈ K and κ_{1} + λ_{1}, κ_{2} + λ_{2} ∈ K_{0} implies κ_{1} · κ_{2} + ε · λ_{1} · λ_{2} ∈ K_{0}; (FR7) κ, λ, κ_{1}, κ_{2} ∈ K and κ + λ · (κ_{1} + κ_{2}) ∈ K_{0} implies κ + λ · κ_{1} + λ · κ_{2} ∈ K_{0}.

Remarks:

i) (FR4), (FR5) and (FR7) imply κ + ε · κ ∈ K_{0} for all κ ∈ K. ii) (FR4) yields directly K^{∗} ∩ K_{0} = ∅. iii) (FR2), (FR4) and (FR5) imply

(FR5’) For α, β ∈ K^{∗} one has α + β ∈ K_{0} if and only if β = ε · α. iv) (FR7) implies: If λ_{1}, ..., λ_{n}, κ_{11}, ..., κ_{1m}, κ_{21}, ..., κ_{2m}, ..., κ_{n1}, ..., κ_{nm} ∈ K and

∑_{i=1}^{n} λ_{i} · (∑_{j=1}^{m} κ_{ij}) ∈ K_{0}, then

(FR7’)  ∑_{i=1}^{n} ∑_{j=1}^{m} λ_{i} · κ_{ij} ∈ K_{0}.

Examples:

i) The commutative rings R = (R; + ; ·) with 1 ∈ R are (in a canonical correspondence to) exactly those fuzzy rings (K; + ; ·; ε; K_{0}) for which K_{0} = {0}. In this case we have necessarily ε = −1.

ii) Let R^{+} and R^{−} denote the positive and negative units in R, respectively, and put R//R^{+} := {{0} , R^{+}, R^{−}, R}. By adding and multiplying the elements of R//R^{+} as complexes one gets the following tables:

+ 0  R^{+} R^{−} R
0 0 R^{+} R^{−} R
R^{+} R^{+} R^{+} R R
R^{−} R^{−} R R^{−} R
R R R R R

·  0 R^{+} R^{−} R
0 0 0 0 0
R^{+} 0 R^{+} R^{−} R
R^{−} 0 R^{−} R^{+} R
R 0 R R R

Then K := R//R^{+} is a fuzzy ring with K_{0} = {{0} , R}, K^{∗} = {R^{+}, R^{−}} and ε = R^{−}. In [8, §6] it is shown that R//R^{+} is an appropriate domain of coefficients for oriented matroid theory. These and some further examples of fuzzy rings are considered in more detail in

[6, (1.3)] and [23, §1].

Now we want to define matroids with coefficients of finite rank in terms of their Grassmann-Plücker maps (cf. [8]).

Definition 2.2. Assume E is some – possibly infinite – set and K = (K; + ; ·; ε; K_{0}) is a fuzzy ring. For m ∈ N_{0} a map b : E^{m} → K^{∗} ˙∪ {0} is called a Grassmann-Plücker map of degree m, if the following axioms hold:

(GP0) There exist e_{1}, ..., e_{m} ∈ E with b (e_{1}, ..., e_{m}) ≠ 0. (GP1) b ist ε-alternating; this means, for e_{1}, ..., e_{m} ∈ E and every odd permutation τ ∈ S_{m}

one has

b (e_{τ(1)}, ..., e_{τ(m)}) = ε · b (e_{1}, ..., e_{m}) ,

and in case # {e_{1}, ..., e_{m}} < m one has b (e_{1}, ..., e_{m}) = 0. (GP2) For all e_{0}, ..., e_{m}, f_{2}, ..., f_{m} ∈ E one has^{1}

∑_{i=0}^{m} ε^{i} · b (e_{0}, ..., ê_{i}, ..., e_{m}) · b (e_{i}, f_{2}, ..., f_{m}) ∈ K_{0}.  (1)

The relations (1) are called the Grassmann-Plücker relations.

Two Grassmann-Plücker maps b_{1}, b_{2} : E^{m} → K^{∗} ˙∪ {0} are equivalent if there exists some κ ∈ K^{∗} such that for all e_{1}, ..., e_{m} ∈ E one has

b_{1} (e_{1}, ..., e_{m}) = κ · b_{2} (e_{1}, ..., e_{m}) .

In case m = 0, a Grassmann-Plücker map is defined on a singleton set taking its value in K^{∗}.

Example. Assume K is a field and E ⊆ K^{m} is a spanning subset of the vector space K^{m}. View the elements of E as columns. Then b : E^{m} → K defined by

b (e_{1}, ..., e_{m}) = det (e_{1}, ..., e_{m})

is a Grassmann-Plücker map; the relations (1) state nothing but the well-known identity of Grassmann.

Now, we come to the following basic

Definition 2.3. Assume E is some set, K = (K; + ; ·; ε; K_{0}) is a fuzzy ring, and suppose m ∈ N_{0}. A matroid M of rank m defined on E and with coefficients in K consists of an equivalence class of Grassmann-Plücker maps b : E^{m} → K^{∗} ˙∪ {0}. We write M = M_{b} for any Grassmann-Plücker map b defining M.

A subset B = {e_{1}, ..., e_{m}} of E is called a base of the matroid M, if b (e_{1}, ..., e_{m}) ≠ 0 for one and thus for all Grassmann-Plücker maps b with M_{b} = M.

Remarks:

i) By definition, for two Grassmann-Plücker maps b, b′ we have M_{b} = M_{b′} if and only if b and b′ are equivalent.

ii) If M is a matroid with coefficients defined on E with B as its set of bases, then (GP2) yields directly that the pair \underline{M} := (E, B) defines a matroid in the classical sense. \underline{M} is called the underlying combinatorial geometry of M.

1 As usual, (e_{o}, ..., ê_{i}, ..., e_{m}) denotes the m-tuple (e_{0}, ..., e_{i−1}, e_{i+1,}...., e_{m}).

Examples:

i) If K is a field, then the matroids of rank m defined on E and with coefficients in K are in a canonical one-to-one correspondence to the equivalence classes of vector representations φ : E → K^{m} of the underlying combinatorial geometries, where two such representations φ_{1}, φ_{2} : E → K^{m} are called equivalent if and only if there exists some regular m × m-matrix A with coefficients in K such that for all e ∈ E one has φ_{2} (e) = A · φ_{1} (e). More precisely, if φ : E → K^{m} is a vector representation of some combinatorial geometry over the field K, then b : E^{m} → K defined by

b (e_{1}, ..., e_{m}) := det (φ (e_{1}) , ..., φ (e_{m}))

is a corresponding Grassmann-Plücker map.

ii) Put K_{c} := R/R^{∗} := {{0} , R^{∗}, R} . Complex addition and multiplication yield the following tables:

+ 0 R^{∗} R
0  0 R^{∗} R
R^{∗} R^{∗} R R
R R R R

· 0 R^{∗} R
0  0 0 0
R^{∗} 0 R^{∗} R
R 0 R R

K = K_{c} is a fuzzy ring with K_{0} = {{0} , R} , K^{∗} = {R^{∗}} and 1 = ε = R^{∗}. In particular, any Grassmann-Plücker map b : E^{m} → K^{∗} ˙∪ {0} is of the form

b (e_{1}, ..., e_{m}) = \{ \begin{matrix}1, & if \{e_{1}, ..., e_{m}\} is a base of M_{b} \\ 0 & otherwise. \end{matrix}

Since 1+...+1 ∈ K_{0} whenever the sum contains at least two summands, (GP2) states nothing but the strong exchange condition for bases in matroids:

If B_{1}, B_{2} are bases of some matroid M and e ∈ B_{1} \ B_{2}, then there exists some f ∈ B_{2} \ B_{1} such that (B_{1} \ {e}) ∪ {f} and (B_{2} \ {f}) ∪ {e} are bases of M.

This means that K = K_{c} is an appropriate domain for classical matroid theory (see also [10, (4.7)]).

iii) As already remarked above, R//R^{+} is an appropriate domain for oriented matroids; indeed, it is trivially verified that matroids with coefficients in R//R^{+} are in canonical one-to-one correspondence to chirotopes as considered in [7], see also [2], [17] and [18].

Next we recall the concept of a Δ-matroid.

Definition 2.4. (cf. [3], [4]) Assume E is some finite set and ∅ ≠ F ⊆ P (E).

i) The pair (E, F) is a Δ-matroid if F satisfies the following symmetric exchange axiom:

(SEA) For F_{1}, F_{2} ∈ F and e ∈ F_{1}ΔF_{2} := (F_{1} ∪ F_{2}) \ (F_{1} ∩ F_{2}) there exists
some f ∈ F_{1}ΔF_{2} such that F_{1}Δ {e, f} ∈ F.

ii) A Δ-matroid (E, F) is even if for all F_{1}, F_{2} ∈ F one has #F_{1} ≡ #F_{2} mod 2.

Note that the ordinary matroids (E, F) with base set F are exactly the Δ-matroids defined on E with equicardinal feasible sets. For F ⊆ P (E) and I ⊆ E put

FΔI := {F ΔI | F ∈ F} .  (2)

Trivially, (E, F) is a Δ-matroid if and only if (E, FΔI) is a Δ-matroid.

Definition 2.5. (cf. [4, §4]) Assume K is a field and (E, F) is a Δ-matroid. (E, F) is representable over K by some skew-symmetric matrix A = (a_{ij})_{i,j∈E} if there exists some I ⊆ E such that

FΔI = F (A) := {F ⊆ E | A′ := (a_{ij})_{i,j∈F} is nonsingular} ,  (3)

where (a_{ij})_{i,j∈∅} is considered to be nonsingular. The matrix A is then called a representation of (E, F) relative to I.

Now, we are also able to recall the concept of a Δ-matroid with coefficients as introduced in [23].

Definition 2.6. Assume K = (K; + ; ·; ε; K_{0}) is a fuzzy ring and E = {1, ..., n} , n ∈ N.

i) A map p : P(E)→K^{∗} ˙∪ {0} is a twisted Pfaffian map if the following axioms hold:

(TP0) There exists some I_{0} ⊆ E with p (I_{0}) ≠ 0.
(TP1) For all I_{1}, I_{2} ⊆ E with p (I_{1}) ≠ 0 and p (I_{2}) ≠ 0 one has

#I_{1} ≡ #I_{2} mod 2.

(TP2) If I_{1}, I_{2} ⊆ E and I_{1}ΔI_{2} = {i_{1}, ..., i_{ℓ}} with i_{j} < i_{j+1} for 1 ≤ j ≤ ℓ − 1,

then one has

∑_{j=1}^{ℓ} ε^{j} · p (I_{1}Δ {i_{j}}) · p (I_{2}Δ {i_{j}}) ∈ K_{0}.

Two twisted Pfaffian maps p_{1}, p_{2} : P (E) → K^{∗} ˙∪ {0} are called equivalent if there exists some κ ∈ K^{∗} such that for all I ⊆ E one has p_{1} (I) = κ · p_{2} (I).

ii) A Δ-matroid M defined on E and with coefficients in K consists of an equivalence class of twisted Pfaffian maps p : P (E) → K^{∗} ˙∪ {0}. We write also M = M_{p} for any twisted Pfaffian map p defining M. A subset F ⊆ E is called free or feasible in M if p (F) ≠ 0 for one and thus for all twisted Pfaffian maps p with M_{p} = M.

Remarks:

i) If F is the set of feasible subsets of a Δ-matroid M = M_{p} with coefficients in some fuzzy ring K, then (TP2) yields at once that F satisfies the following strong symmetric exchange condition:

(SSEA) For F_{1}, F_{2} ∈ F and e ∈ F_{1}ΔF_{2} there exists some f ∈ (F_{1}ΔF_{2}) \ {e}
with F_{1}Δ {e, f} ∈ F and F_{2}Δ {e, f} ∈ F,

which obviously strengthens (SEA). We call \underline{M} := (E, p^{−1} (K^{∗})) the underlying Δmatroid of M = M_{p}.

ii) For K = K_{c} as in Example ii) following Definition 2.3, axiom (TP2) is clearly equivalent to the strong symmetric exchange condition. In [24], it is shown that a Δ-matroid is even if and only if it satisfies (SSEA). Therefore, K_{c} is an appropriate coefficient domain for even Δ-matroids; that is, every even Δ-matroid may be interpreted as a Δ-matroid with coefficients in K_{c}.

iii) Assume K is a fuzzy ring, α ∈ K^{∗}, I_{0} ⊆ E = {1, ..., n}, and p, p′ : P (E) → K^{∗} ˙∪ {0} are two maps related by the formula

p′ (I) = α · p (IΔI_{0}) for all I ⊆ E.

Then p is a twisted Pfaffian map if and only if p′ is a twisted Pfaffian map. Note that for I_{1}, I_{2} ⊆ E one has (I_{1}ΔI_{0}) Δ (I_{2}ΔI_{0}) = I_{1}ΔI_{2}.

iv) If K is a field, then by [23, Theorem 2.9] a Δ-matroid (E, F) is representable over K by some skew-symmetric matrix if and only if (E, F) is the underlying Δ-matroid of M_{p} for some twisted Pfaffian map p : P (E) → K. The correspondence is as follows: If FΔI_{0} = F (A) for some I ⊆ E and some skew-symmetric matrix A = (a_{ij})_{1≤i,j≤n}, then – according to the last remark – we may assume I_{0} = ∅, and a corresponding twisted Pfaffian map p = p_{A} is then given in terms of the Pfaffian form Pf ; namely p (I) := Pf ((a_{ij})_{i,j∈I}) for I ⊆ E. Vice versa, if p : P (E) → K is a twisted Pfaffian map with p (∅) = 1, then it is easily verified that the matrix A_{p} = A = (a_{ij})_{1≤i,j≤n} given by

\begin{matrix}a_{ii} := 0 for 1 ≤ i ≤ n, \\ a_{ij} = −a_{ji} = p (\{i, j\}) for 1 ≤ i < j ≤ n \end{matrix}

is a representation of \underline{M_{p}} .

For more details see [22, §2] and [12], where it is also shown that for any skewsymmetric matrix A = (a_{ij})_{1≤i,j≤n} the corresponding twisted Pfaffian map p = p_{A} satisfies (TP2).

v) In [23, Proposition 2.15], it is verified that for a given even Δ-matroid (E, F) and a given fuzzy ring K the existence of some twisted Pfaffian map p : P (E) → K^{∗} ˙∪ {0} with p^{−1} (K^{∗}) = F does not depend on the natural order on the set E = {1, ..., n}.

In the rest of this section, we are concerned with the concept of an antipodal graph as established in [1], [16], [20]. First, we state the following

Definition 2.7. Assume Γ = (V, K) is a graph.

i) The map d_{Γ} : V × V → N_{0} ∪ {∞}, induced by Γ, is given by

d_{Γ} (v, v′) := \begin{cases}∞ if v and v′ lie in distinct connected components of Γ \\ min \{ℓ ∈ N_{0}| & there exist v_{0}, ..., v_{ℓ} ∈ V with v_{0} = v, v_{ℓ} = v′ \\ and \{v_{i−1}, v_{i}\} ∈ K for 1 ≤ i ≤ ℓ\} otherwise. \end{cases} (4)

ii) For v, v′ ∈ V with d_{Γ} (v, v′) < ∞ the hull ⟨v, v′⟩_{Γ} is defined by

⟨v, v′⟩_{Γ} := {v′′ ∈ V | d_{Γ} (v, v′) = d_{Γ} (v, v′′) + d_{Γ} (v′′, v′)} .

iii) If Γ is connected, then the diameter diamΓ of Γ is given by

diamΓ := sup {d_{Γ} (v, w) | v, w ∈ V } .

Definition 2.8. Assume Γ = (V, K) is a connected graph.

i) Γ is even, if for every v ∈ V there exists a unique v^{⌢}∈ V with d_{Γ} (v, v^{⌢}) = diamΓ.

ii) An even graph Γ is antipodal, if for all v ∈ V and v^{⌢} as in i) one has ⟨v, v^{⌢}⟩_{Γ} = V.

In this case, for v ∈ V the vertex v^{⌢} given in i) is called the antipode of v.

Remarks:

i) By definition, the diameter of an antipodal graph is finite. ii) If Γ = (V, K) is an antipodal graph, then it is easily verified that the map α : V → V

given by α (v) := v^{⌢} is an automorphism of Γ, which satisfies α^{2} = id_{V}. However, in [16, Figure 2] there are listed some even graphs for which the map α is not an automorphism.

By unifying the concepts of matroids with coefficients and of Δ-matroids with coefficients, we shall be concerned with antipodal subgraphs of certain graphs of finite diameter.

Definition 2.9. A connected graph Γ = (V, K) is convex-antipodal if for all v_{1}, v_{2} ∈ V the induced subgraph Γ_{⟨v_{1},v_{2}⟩} of Γ on the vertex set ⟨v_{1}, v_{2}⟩ := ⟨v_{1}, v_{2}⟩_{Γ} is finite and antipodal. In this case the antipode of v ∈ ⟨v_{1}, v_{2}⟩ in Γ_{⟨v_{1},v_{2}⟩} is denoted by ap_{⟨v_{1},v_{2}⟩} (v).

Remark. Assume the graph Γ = (V, K) is convex-antipodal, and suppose v_{1}, v_{2} ∈ V. Then it is easily verified that for v ∈ ⟨v_{1}, v_{2}⟩ one has ⟨v_{1}, v_{2}⟩ = ⟨v, ap_{⟨v_{1},v_{2}⟩} (v)⟩ and that ⟨v_{1}, v_{2}⟩ is a convex set in the metric space (V, d_{Γ}); that means, for v, v′ ∈ ⟨v_{1}, v_{2}⟩ one has ⟨v, v′⟩ ⊆ ⟨v_{1}, v_{2}⟩. (See also [25, Lemma 3.9] for more details.)

Examples:

i) Assume m ∈ N_{0} and E is some – possibly infinite – set with at least m elements. Let Γ_{1} = (V (Γ_{1}) , K (Γ_{1})) denote the graph with V (Γ_{1}) = \binom{E}{m} and

K (Γ_{1}) := \{\{A, B\} ⊆ \binom{E}{m} | # (A ∩ B) = m − 1\} .  (5)

Then Γ_{1} is convex-antipodal. For A, B ∈ \binom{E}{m} one has

⟨A, B⟩ := ⟨A, B⟩_{Γ_{1}} = \{C ∈ \binom{E}{m} | A ∩ B ⊆ C ⊆ A ∪ B\} ,

and for C ∈ ⟨A, B⟩ the antipode ap_{⟨A,B⟩} (C) is given by

ap_{⟨A,B⟩} (C) = (A ∪ B) \ (C \ (A ∩ B)) = AΔBΔC.

We shall be concerned with the graph Γ_{1} when studying matroids with coefficients defined on E and of rank m.

ii) Assume E is some finite set, and let Γ_{2} = (V (Γ_{2}) , K (Γ_{2})) denote the bipartite graph with V (Γ_{2}) = P (E) and

K (Γ_{2}) := {{A, B} ⊆ P (E) | # (AΔB) = 1} .  (6)

Moreover, for ν ∈ {1, 2} let G_{ν} = (V (G_{ν}) , K (G_{ν})) denote the graph with V (G_{ν}) = {A ⊆ E | #A ≡ ν mod 2} and

K (G_{ν}) := {{A, B} ⊆ V (G_{ν}) | # (AΔB) = 2} .  (7)

Then the graphs Γ_{2}, G_{1} and G_{2} are convex-antipodal. For A, B ∈ P (E) one has

⟨A, B⟩ := ⟨A, B⟩_{Γ_{2}} = {C ⊆ E | A ∩ B ⊆ C ⊆ A ∪ B} ,

and for C ∈ ⟨A, B⟩ one has, similarly as in Example i)

ap_{⟨A,B⟩} (C) = (A ∪ B) \ (C \ (A ∩ B)) = AΔBΔC.

If, moreover, A, B ∈ V (G_{ν}) for one and the same ν ∈ {1, 2}, then one has

⟨A, B⟩_{G_{ν}} = ⟨A, B⟩_{Γ_{2}} ∩ V (G_{ν})

and

ap_{⟨A,B⟩_{Gν}} (C) = ap_{⟨A,B⟩_{Γ_{2}}} (C) for C ∈ ⟨A, B⟩_{G_{ν}} .

We shall have to study the graphs Γ_{2}, G_{1} and G_{2} in the case of Δ-matroids with coefficients defined on E.

Throughout the rest of this paper assume that the graphs Γ_{1}, Γ_{2}, G_{1} and G_{2} are as in the last examples, where m and E are fixed. At the end of this section, we recall the concepts of the base graph of a matroid and of the base graph of an even Δ-matroid.

Definition 2.10:

i) Assume M is a matroid (with or without coefficients) defined on E and of rank m and with B as its set of bases. The base graph of M is the graph Γ_{M} = (B, K) with B as its set of vertices and

K := {{B_{1}, B_{2}} | B_{1}, B_{2} ∈ B, # (B_{1} ∩ B_{2}) = m − 1}

as its set of edges; that is, Γ_{M} is the induced subgraph of Γ_{1} on the base set B. ii) Assume M = (E, F) is an even Δ-matroid. The base graph of M is the graph Γ_{M} =

(F,K̃) with F as its set of vertices and

K̃ := {{F_{1}, F_{2}} | F_{1}, F_{2} ∈ F, # (F_{1}ΔF_{2}) = 2}

as its set of edges.

Note that Definition 2.10 i) is a special case of Definition 2.10 ii) and that the base graph of an even Δ-matroid (E, F) is an induced subgraph either of G_{1} or of G_{2}.

3. The Basic Concept of a (W; P; U)-Matroid with Coefficients

In order to unify the concepts of matroids with coefficients and of Δ-matroids with coefficients in a graph theoretical framework, we shall study graphs arising from Coxeter groups.

In the sequel, let W denote a Coxeter group, say

W = ⟨R | (rs)^{m(r,s)} = 1, r, s, ∈ R⟩

for some R ⊆ W, the set of generators of W, and 1 ≤ m (r, s) = m (s, r) ≤ ∞ for all r, s ∈ R, where m (r, s) = 1 if and only if r = s.

For P ⊆ R let

W_{P} := ⟨P ⟩  (8)

denote the parabolic subgroup of W generated by P, and let

W^{P} := W/W_{P} = {w · W_{P} | w ∈ W }  (9)

denote the set of left cosets, regarded as subsets of W.

Definition 3.1. Assume W, P are as above and put

\begin{aligned}K := \{\{w_{1} · W_{P} , w_{2} · W_{P} \} ∈ \binom{W^{P}}{2} | & W_{P} · w_{1}^{−1} · w_{2} · W_{P} = \\ & W_{P} · r · W_{P} for some r ∈ R \ P \}. \end{aligned}  (10)

i) The (W; P)-graph Γ := (W^{P} , K) has W^{P} as its set of vertices and K as its set of edges. For ∅ ≠ L ⊆ W^{P} let Γ_{L} denote the induced subgraph of Γ on the set L of vertices.

ii) Assume U is a – not necessarily parabolic – subgroup of W with W_{P} ≤ U. Write \overline{w} := w · W_{P} for w ∈ W and put

\begin{matrix}\overline{U} := U^{P} := U/W_{P} = \{\overline{u} | u ∈ U\} , \\ \overline{w · U} := w · U^{P} = \{\overline{w · u} | u ∈ U\} for w ∈ W. \end{matrix}

For k ≥ 1 the triple (W; P; U) is called k-regular if the following axiom holds:

(U_{k}) For u_{1}, u_{2} ∈ U with \overline{u_{1}} ≠ \overline{u_{2}} one has
⟨\overline{u_{1}}, \overline{u_{2}}⟩_{Γ} ∩ U^{P} =\{\overline{w} ∈ ⟨\overline{u_{1}}, \overline{u_{2}}⟩_{Γ} | d_{Γ} (\overline{u_{1}}, \overline{w}) ≡ d_{Γ} (\overline{u_{2}}, \overline{w}) ≡ 0 mod k\}.

iii) Assume w ∈ W and the triple (W; P; U) is k-regular. Put

K\overline{w·U} := \{ \{\overline{w · u_{1}}, \overline{w · u_{2}}\} | u_{1}, u_{2} ∈ U, d_{Γ} (\overline{w · u_{1}}, \overline{w · u_{2}}) = d_{Γ} (ū_{1}, ū_{2}) = k \} . (11)

Then the (W; P; w · U)-graph Γ\overline{w·U} := (\overline{w · U}, K\overline{w·U}) has \overline{w · U} as its set of vertices and K\overline{w·U} as its set of edges. For ∅ ≠ L ⊆ w · U^{P} let Γ_{\overline{w·U,}L} denote the induced subgraph of Γ\overline{w·U} on the set L of vertices.

In the sequel, Γ\overline{U} will – of course – mean the graph Γ\overline{1·U}.

Remarks:

i) Since any w ∈ W is a finite product of elements in R, the (W; P)-graph Γ is trivially connected.

ii) If the triple (W; P; U) is k-regular, then one has d_{Γ} (\overline{u_{1}}, \overline{u_{2}}) ≡ 0 mod k for all u_{1}, u_{2} ∈U;

this follows directly from axiom (U_{k}). iii) If U = W_{P}, then by definition the triple (W; P; U) is k-regular for every k ∈ N. In

this case, for any w ∈ W the (W; P; w · U)-graph has only one vertex. However, if W_{P} ⫋ U, then the triple (W; P; U) is k-regular for at most one k ∈ N. The triple (W; P; W) is certainly 1-regular, and one has Γ\overline{W} = Γ.

iv) For w_{1} , w_{2} , w ∈ W one has { w · w_{1} · W_{P} , w · w_{2} · W_{P} } ∈ K if and only if {w_{1} · W_{P} , w_{2} · W_{P} } ∈ K. Therefore, any w ∈ W induces an automorphism of Γ in the obvious way. Moreover, for a k-regular triple (W; P; U) every w ∈ W induces an isomorphism from Γ\overline{U} onto Γ\overline{w·U}. If w, w′ ∈ W, then Γ\overline{w·U} = Γ\overline{w′·U} implies d_{Γ} (\overline{w}, \overline{w′}) ≡ 0 mod k. In case W_{P} ⫋ U this means in particular that [W : U] ≥ k because there exists a path (\overline{w_{0}}, ..., \overline{w_{k}}) in Γ with \overline{w_{0}} ≠ \overline{w_{k}} but w_{0} · U = w_{k} · U, and the k cosets w_{1} · U, ..., w_{k} · U of U in W are pairwise distinct. It should be remarked that one has not necessarily [W : U] = k even if U ≠ W_{P}; see, for instance, [25, Proposition 3.6].

We have the following

Lemma 3.2. Assume the triple (W; P; U) is k-regular for some k ≥ 1, suppose w ∈ W, and put Γ′ := Γ\overline{w·U}. Then, for all w_{1}, w_{2} ∈ w · U one has

k · d_{Γ′} (\overline{w_{1}}, \overline{w_{2}}) = d_{Γ} (\overline{w_{1}}, \overline{w_{2}}) ,  (12)
⟨\overline{w_{1}}, \overline{w_{2}}⟩_{Γ′} = ⟨\overline{w_{1}}, \overline{w_{2}}⟩_{Γ} ∩ \overline{w · U}.  (13)

In particular, Γ′ is connected.

Proof. This is [25, Lemma 3.4].

The following result provides a rather large class of 2-regular triples (W; P; U) and will also encompass the important class of Δ-matroids with coefficients.

Proposition 3.3. Assume W_{P} ≠ W and the (W; P)-graph Γ is bipartite. Let W^{P} = V_{1} ˙∪V_{2} denote the unique partition of W^{P} with \overline{1} ∈ V_{1} and d_{Γ} (\overline{w_{i}}, \overline{w_{j}}) ≡ i−j mod 2 for i, j ∈ \{1, 2\}, \overline{w_{i}} ∈ V_{i}, \overline{w_{j}} ∈ V_{j}. Then the set

U := \{u ∈ W | \overline{u} ∈ V_{1}\} = \{u ∈ W | d_{Γ} (\overline{1}, \overline{u}) ≡ 0 mod 2\}  (14)

is a subgroup of W of index 2, and the triple (W; P; U) is 2-regular.

Proof. This is [25, Proposition 3.5].

Examples:

i) Assume n ∈ N, let W = W_{1} = S_{n} denote the group of permutations of E = I_{n} := {1, ..., n}, R = R_{1} the set of transpositions (i i + 1) for 1 ≤ i ≤ n − 1, choose some fixed m with 0 < m < n, and put

P = P_{1} := P_{(m,n)} := R_{1} \ {(m m + 1)} .

Then one has

W_{P} = {w ∈ W | w (I_{m}) = I_{m}} .

Therefore, we have a bijection χ : W_{1}^{P_{1}} → \binom{E}{m} from the set of left cosets of ⟨P_{(m,n)}⟩ in S_{n} onto the m-subsets of E, given by

χ (w · W_{P}) := w (I_{m}) .

For A ∈ \binom{E}{m} one has # (A ∩ I_{m}) = m−1 if and only if A = w_{0} ((I_{m} \ \{m\}) ∪ \{m + 1\}) for some w_{0} ∈ W_{P}. Thus for B_{1}, B_{2} ∈ \binom{E}{m} one has # (B_{1} ∩ B_{2}) = m − 1 if and only if there exist w ∈ W and w_{0} ∈ W_{P} with B_{1} = w (I_{m}) and B_{2} = (w ∘w_{0} ∘(m m + 1)) (I_{m}). By Definition 3.1 this means, in view of the identification of W_{1}^{P_{1}} with \binom{E}{m} via the bijection χ that the (W_{1}; P_{1})-graph is nothing but the graph Γ_{1} considered in Example i) following Definition 2.9. Moreover, for an ordinary matroid M defined on E and of rank m with B as its set of bases the graph Γ_{L} for L := χ^{−1} (B) is just the base graph of M.

ii) Assume again n ∈ N, E = I_{n} := {1, ..., n}, and

Ẽ := {1, ..., n} ˙∪ {1^{∗}, ..., n^{∗}};

thus Ẽ consists of E together with a disjoint copy of E. For k ∈ E put (k^{∗})^{∗} := k; then one has (k^{∗})^{∗} = k for every k ∈ Ẽ. A transversal in Ẽ is any subset T ⊆ Ẽ with # ({k, k^{∗}} ∩ T) = 1 for all k ∈ E.

Let W = W_{2} denote the group of permutations of Ẽ which map transversals onto transversals, or, equivalently, with w (k^{∗}) = (w (k))^{∗} for every k ∈ Ẽ. Then W is a Coxeter group with

R = R_{2} := {(i i + 1) ∘ (i^{∗} (i + 1)^{∗}) | 1 ≤ i ≤ n − 1} ˙∪ {(n n^{∗})}

as an appropriate set of generators. Put

P = P_{2} := R \ {(n n^{∗})} .

Then one has

W_{P} = {w ∈ W | w (E) = E} ,

and thus we have bijections χ′ : W_{2}^{P_{2}} → T , χ′′ : W_{2}^{P_{2}} → P (E) onto the set T of transversals in Ẽ or the power set of E, respectively, given by

\begin{matrix}χ′ (w · W_{P}) := w (E) , \\ χ′′ (w · W_{P}) := w (E) ∩ E. \end{matrix}

We show that the edge set K of the (W; P)-graph satisfies

K = {{χ^{′−1} (T_{1}) , χ^{′−1} (T_{2})} | T_{1}, T_{2} ∈ T , # (T_{1} △ T_{2}) = 2} ,  (15)
K = {{χ^{′′−1} (A) , χ^{′′−1} (B)} | A, B ⊆ E, # (A △ B) = 1} .  (16)

It suffices to verify (15), because (15) and (16) are trivially equivalent. Assume first that T_{1}, T_{2} ∈ T satisfy # (T_{1} △ T_{2}) = 2, and choose some w ∈ W with T_{1} = w (E). Then there exists some e ∈ E with T_{2} = w (E △ {e, e^{∗}}). Choose some w_{0} ∈ W_{P} with w_{0} (n) = e and w_{0} (n^{∗}) = e^{∗}. Then one has T_{2} = (w ∘ w_{0} ∘ (n n^{∗})) (E) and thus {χ^{′−1} (T_{1}) , χ^{′−1} (T_{2})} ∈ K. If vice versa T_{1}, T_{2} ∈ T correspond to neighbours in the (W; P)-graph Γ, choose some w ∈ W and some w_{0} ∈ W_{P} with w (E) = T_{1} and (w ∘ w_{0} ∘ (n n^{∗})) (E) = T_{2}. Then one has

# (E △ w_{0} ((E \ {n}) ∪ {n^{∗}})) = # ({w_{0} (n) , w_{0} (n^{∗})}) = 2

and thus also # (T_{1} △ T_{2}) = 2. Now (16) shows that the (W_{2}; P_{2})-graph is – via the bijection χ′′ – nothing but the graph Γ_{2} studied in Example ii) following Definition 2.9. Moreover, it is trivial that Γ_{2} is a bipartite graph and that with the notations in the example just mentioned any \{\overline{w_{1}}, \overline{w_{2}}\} ∈ K satisfies χ′′ (\overline{w_{1}}) ∈ V (G_{i}), χ′′ (\overline{w_{2}}) ∈ V (G_{j}), where \{i, j\} = \{1, 2\}. If we thus put

\begin{aligned}U_{Δ} : & = \{w ∈ W | # (E \ w (E)) ≡ 0 mod 2\} \\ & = \{w ∈ W | # (w (E) ∩ E) ≡ #E mod 2\} , \end{aligned}  (17)

then Proposition 3.3 shows that the triple (W_{2}; P_{2}; U_{Δ}) is 2-regular. It is now also clear that for U := U_{Δ} the distinct graphs Γ\overline{w·U} , w ∈ W, are precisely the graphs G_{1} and G_{2} and that for an even Δ-matroid M = (E, F) the base graph Γ_{M} is the graph Γ_{\overline{w·U,}L}, where L:=χ^{′′−1} (F) and w ∈ W satisfies L ⊆ \overline{w · U.}

For further examples which arise also from combinatorial geometry, but which are not closely related to classical matroid theory, see [25, §3].

I would like to establish a theory in which Maurer’s homotopy theory as developed for ordinary matroids in [19, §5] will also hold. To this end, I propose the following

Definition 3.4. Assume G = (V (G) , K (G)) is a graph.

i) If V′ ⊆ V (G) and K′ ⊆ K (G) ∩ \binom{V′}{2}, then the graph G′ := (V′, K′) is isometric in G, if for all v_{1}, v_{2} ∈ V′ one has d_{G′} (v_{1}, v_{2}) = d_{G} (v_{1}, v_{2}).

ii) A reentrant^{2} path (v_{0}, ..., v_{ℓ}) is called isometric in G, if v_{i} = v_{j} only for i ≡ j mod ℓ and the cycle G′ = (V′, K′) with V′ := {v_{0}, ..., v_{ℓ}}, K′ := {{v_{i}, v_{j}} | i ≡ j + 1 mod ℓ} is isometric in G.

iii) The graph G satisfies the Maurer Condition if for any two isometric reentrant paths (v_{0}, ..., v_{ℓ}), (v′_{0}, ..., v′_{ℓ}) in G of length ℓ ≥ 5 with v_{i} = v′_{i} for 0 ≤ i ≤ ℓ − 2 one has either v′_{ℓ−1} = v_{ℓ−1} or d_{G} (v_{ℓ−1}, v′_{ℓ−1}) = 1.

We have

Proposition 3.5. Assume G = (V (G) , K (G)) is a graph.

i) If G satisfies the Maurer Condition and H is an isometric subgraph in G, then H satisfies the Maurer Condition, too.

ii) Suppose the connected components of G are convex-antipodal. Then G satisfies the Maurer Condition if for every \underline{odd} ℓ ≥ 5 and any two isometric reentrant paths (v_{0}, ..., v_{ℓ}) , (v′_{0}, ..., v′_{ℓ}) in G of length ℓ with v_{i} = v′_{i} for 0 ≤ i ≤ ℓ − 2 one has either v′_{ℓ−1} = v_{ℓ−1} or d_{G} (v_{ℓ−1}, v′_{ℓ−1}) = 1. In particular, every convex-antipodal graph in which each cycle has an even length satisfies the Maurer Condition.

Proof. This is [25, Proposition 4.2]. i) follows easily from the fact that every reentrant path which is isometric in H is isometric in G, too. ii) holds, because for two isometric reentrant paths (v_{0}, ..., v_{ℓ}), (v′_{0}, ..., v′_{ℓ}) in G of even length ℓ = 2h ≥ 6 with v_{i} = v′_{i} for 0 ≤ i ≤ ℓ − 2 one gets:

v_{ℓ−1} = ap_{⟨v_{0},v_{h}⟩} (v_{h−1}) = v′_{ℓ−1}.

The next result shows that the base graphs of matroids and – more generally – of even Δ-matroids satisfy the Maurer Condition.

Proposition 3.6:

i) Let Γ̃_{2} denote the graph whose connected components are G_{1} and G_{2}. Then Γ̃_{2} satisfies the Maurer Condition.

2 “Reentrant” means that v_{0} = v_{ℓ}. ii) The base graph of an even Δ-matroid satisfies the Maurer Condition. iii) The graph Γ_{1} as well as all base graphs of ordinary matroids satisfy the Maurer Con-

dition.

Proof:

i) is [25, Proposition 4.3]. ii) As it follows directly from the strong symmetric exchange condition, the base graph of

an even Δ-matroid is isometric in Γ̃_{2}. Thus ii) follows from i) and Proposition 3.5 i). iii) is a special case of ii).

In the sequel, assume k ≥ 1 and (W; P; U) is a k-regular triple where W = ⟨R⟩ as above, and let Γ̃ = Γ^{U} denote the graph with vertex set W^{P} whose connected components are precisely the distinct graphs Γ\overline{w·U} ; this means that Γ̃ has the same vertex set as the (W; P)- graph Γ but [W : U] connected components. For w_{1}, w_{2} ∈ W with d_{Γ} (\overline{w_{1}}, \overline{w_{2}}) < ∞ one has of course

⟨\overline{w_{1}}, \overline{w_{2}}⟩_{Γ} = ⟨\overline{w_{1}}, \overline{w_{2}}⟩_{Γ\overline{w_{1}·U}} .

Moreover, Lemma 3.2 implies trivially the following

Lemma 3.7. Assume the (W; P)-graph Γ is convex-antipodal. Then the connected components of Γ̃ are also convex-antipodal, and for w ∈ W and w_{1}, w_{2} ∈ w·U with \overline{w} ∈ ⟨\overline{w_{1}}, \overline{w_{2}}⟩_{Γ} one has

ap⟨\overline{w_{1}},\overline{w_{2}}⟩ ; _{Γ} (\overline{w}) = ap_{⟨\overline{w_{1}},\overline{w_{2}}⟩_{Γ}} (\overline{w}) .

With the intent to unify the Grassmann-Plücker relations and the relations (TP2) for twisted Pfaffian maps, I propose the following

Definition 3.8. Assume A_{0}, ..., A_{ℓ} are vertices in Γ̃ with d_{Γ} (A_{i}, A_{j}) = 1 for 0 ≤ i < j ≤ ℓ, and put N := {A_{0}, ..., A_{ℓ}}.

i) Let k_{0} ∈ {0, 1} denote the unique integer satisfying k_{0} ≡ k mod 2. The set N is called star-shaped in Γ if there exist vertices A′_{0}, ..., A′_{ℓ} ∈ W^{P} with d_{Γ} (A_{i}, A′_{i}) = [\frac{k}{2} ] = \frac{1}{2} · (k − k_{0}) for 0 ≤ i ≤ ℓ and d_{Γ} (A′_{i}, A′_{j}) = k_{0} for 0 ≤ i < j ≤ ℓ.

ii) Assume B ∈ W^{P} satisfies d_{Γ} (A_{0}, B) < ∞. Then N is called a fundamental neighbourhood of A_{0} in ⟨A_{0}, B⟩_{Γ} relative to Γ if N is – with respect to inclusion – a maximal star-shaped subset of ⟨A_{0}, B⟩_{Γ}.

In case k = 1 any subset N = {A_{0}, ..., A_{ℓ}} ⊆ W^{P} with d_{Γ} (A_{i}, A_{j}) = 1 for 0 ≤ i < j ≤ ℓ is star-shaped in Γ, one just has to put A′_{i} := A_{i} for 0 ≤ i ≤ ℓ. In this case we shall also omit the term relative to Γ by speaking about fundamental neighbourhoods, because for k = 1 and A, B ∈ W^{P} with d_{Γ} (A, B) < ∞ one has ⟨A, B⟩_{Γ} = ⟨A, B⟩_{Γ} by axiom (U_{1}). (See Definition 3.1 ii).)

If k ≡ 0 mod 2, then Definition 3.8 i) means of course that A′_{i} = A′_{j} for 0 ≤ i < j ≤ ℓ. Any subset {A_{0}, A_{1}} ⊆ W^{P} with d_{Γ} (A_{0}, A_{1}) = 1 is certainly star-shaped in Γ.

The following figures illustrate star-shaped sets {A_{0}, A_{1}, A_{2}} in the cases k = 2 and k = 3.

•  _{•}_{•}_{•} A_{2}  A_{1} A_{0}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} Figure 1  _{•}  _{•}_{•}  _{•}_{•}_{•} A_{2}  A_{1} A′_{2}  A′_{1} A′_{0} A_{0}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} Figure 2

As a last technical preparation we have to consider partitions of the set of triangles in the graph Γ̃. Recall that W operates canonically on Γ as well as on Γ̃.

Definition 3.9. Assume that the connected components of Γ̃ = Γ^{U} are convex-antipodal, put d_{0} := d_{Γ}, let K( Γ̃ ) denote the set of edges of Γ̃ and

D := {{A_{1}, A_{2}, A_{3}} ⊆ W^{P} | d_{0} (A_{i}, A_{j}) = 1 for 1 ≤ i < j ≤ 3} , (18)

V := \left\{{\{A_{1}, A_{2}, A_{3}, A_{4}\} ⊆ W^{P} | d_{0} (A_{i}, A_{i+1}) = 1 for i mod 4, \atop d_{0} (A_{1}, A_{3}) = d_{0} (A_{2}, A_{4}) = 2}\right\} (19)

the set of triangles or pure^{3} quadrangles in Γ̃, respectively.

i) A map η : K( Γ̃ ) → {1, −1} is called four-balanced if for all {A_{1}, A_{2}, A_{3}, A_{4}} as in (19) one has

η ({A_{1}, A_{2}}) · η ({A_{2}, A_{3}}) · η ({A_{3}, A_{4}}) · η ({A_{4}, A_{1}}) = 1.

ii) Assume D = D_{1} ˙∪D_{2} is a partition of D and put

sign_{(D_{1},D_{2})} (\{A_{1}, A_{2}, A_{3}\}) := \{ \begin{matrix}1 & for \{A_{1}, A_{2}, A_{3}\} ∈ D_{1} \\ −1 & for \{A_{1}, A_{2}, A_{3}\} ∈ D_{2} \end{matrix} .

The partition D = D_{1} ˙∪D_{2} is called matroidal if the following three axioms hold:

3 Pure means that the diagonals are no edges.

(D1) There exists some four-balanced map η : K( Γ̃ ) → {1, −1} such that for all {A_{1}, A_{2}, A_{3}} ∈ D one has

sign_{(D_{1},D_{2})} ({A_{1}, A_{2}, A_{3}}) = η ({A_{1}, A_{2}}) · η ({A_{2}, A_{3}}) · η ({A_{3}, A_{1}}) .

(D2) If A, B ∈ W^{P} satisfy d_{0} (A, B) < ∞ and if A_{1}, A_{2}, A_{3} ∈ ⟨A, B⟩ := ⟨A, B⟩_{Γ} are

the vertices of a triangle in D and A_{i}^{⌢}:= ap_{⟨A,B⟩} (A_{i}) for 1 ≤ i ≤ 3, then one has

sign_{(D_{1},D_{2})} ({A_{1}^{⌢}, A_{2}^{⌢}, A_{3}^{⌢}}) = −sign_{(D_{1},D_{2})} ({A_{1}, A_{2}, A_{3}}) .

(D3) Assume r ∈ R is some involution and {A_{1}, A_{2}, A_{3}} ∈ D. If for all i, j with 1 ≤ i < j ≤ 3 one has {A_{i}, A_{j}} ≠ {rA_{i}, rA_{j}}, then

sign_{(D_{1},D_{2})} ({rA_{1}, rA_{2}, rA_{3}}) = sign_{(D_{1},D_{2})} ({A_{1}, A_{2}, A_{3}}) .

If otherwise {i, j, h} = {1, 2, 3} and {A_{i}, A_{j}} = {rA_{i}, rA_{j}}, but rA_{h} ≠ A_{h}, and r_{0} : ⟨A_{i}, A_{j}⟩_{Γ} \ {A_{i}, A_{j}} → ⟨A_{i}, A_{j}⟩_{Γ} \ {A_{i}, A_{j}} denotes the permutation given by the restriction of r on ⟨A_{i}, A_{j}⟩_{Γ} \ {A_{i}, A_{j}}, then one has

sign_{(D_{1},D_{2})} ({rA_{1}, rA_{2}, rA_{3}}) = sign r_{0} · sign_{(D_{1},D_{2})} ({A_{1}, A_{2}, A_{3}}) .

Remarks:

i) Whether a partition D = D_{1} ˙∪D_{2} is matroidal or not does, of course, not depend on the order of D_{1} and D_{2}. By definition, one has sign_{(D_{1},D_{2})} ({A_{1}, A_{2}, A_{3}}) = −sign_{(D_{2},D_{1})} ({A_{1}, A_{2}, A_{3}}) for all {A_{1}, A_{2}, A_{3}} ∈ D. Thus, by exchanging the rôles of D_{1} and D_{2} one may replace the map η in (D1) by the map −η.

ii) Clearly, in case D = ∅ the empty partition is matroidal. In (D1) we can choose the constant map η ≡ 1. If #D = 1, then the fact that W operates transitively on W^{P} implies trivially that [W : W_{P}] = 3, and thus Γ as well as Γ̃ is the cycle of length 3. The partitions D = D ˙∪∅ and D = ∅ ˙∪D are certainly matroidal in this case.

iii) If the triple (W; P; U) is 1-regular, then any map r_{0} as in (D3) is the “unique permutation of the empty set” and satisfies sign r_{0} = 1.

As a direct consequence of axiom (D3), the last Remark, and the fact that R generates W we get the following

Lemma 3.10. Assume the partition D = D_{1} ˙∪D_{2} is matroidal.

i) If the triple (W; P; U) is 1-regular, then for all {A_{1}, A_{2}, A_{3}} ∈ D and all w ∈ W one

has

sign_{(D_{1},D_{2})} ({wA_{1}, wA_{2}, wA_{3}}) = sign_{(D_{1},D_{2})} ({A_{1}, A_{2}, A_{3}}) ;

that is, D_{1} and D_{2} are unions of W -orbits under the canonical operation of W on D. ii) If W operates transitively on D, then D = D_{1} ˙∪D_{2} and D = D_{2} ˙∪D_{1} are the only

matroidal partitions of D.

Definition 3.11. Assume the partition D = D_{1} ˙∪D_{2} is matroidal.

i) A map η : K( Γ̃ ) → {1, −1} fits for the pair (D_{1}, D_{2}), if η is four-balanced and satisfies axiom (D1) in Definition 3.9.

ii) Assume K=(K; + ; ·; ε; K_{0}) is a fuzzy ring, and η : K( Γ̃) → {1, −1} fits for (D_{1}, D_{2}). Then we define \overline{η} = \overline{η_{K}} : K( Γ̃ ) → \{1, ε\} ⊆ K^{∗} by

\overline{η} (\{A, B\}) = \overline{η_{K}} (\{A, B\}) := \{ \begin{matrix}1 & if η (\{A, B\}) = 1 \\ ε & if η (\{A, B\}) = −1. \end{matrix}  (20)

Now, we are ready to state the following basic

Definition 3.12. Suppose the triple (W; P; U) is k-regular for some k ≥ 1, and assume the graph Γ̃ = Γ^{U} satisfies the Maurer Condition. Suppose the connected components of Γ̃ are convex-antipodal, and for any A, B ∈ W^{P} with d_{Γ} (A, B) < ∞ the map ap⟨A,B⟩ ; _{Γ} : ⟨A, B⟩_{Γ} → ⟨A, B⟩_{Γ} can be extended to an automorphism α_{A,B} of the induced subgraph of Γ on the vertex set ⟨A, B⟩_{Γ}. Let D = D_{1} ˙∪D_{2} denote a matroidal partition of the set of triangles in Γ̃ and put

Q := (W; P; U; (D_{1}, D_{2})) .

Assume B is some non-empty subset of W^{P} contained in some connected component of Γ̃. Finally, suppose that K = (K; + ; ·; ε; K_{0}) is a fuzzy ring.

i) Assume η : K( Γ̃ ) → {1, −1} fits for (D_{1}, D_{2}), and f : W^{P} → K^{∗} ˙∪ {0} is a map. Then the pair (η, f) defines a (W; P; U)-matroid M with coefficients in K with B as its set of bases if the following two axioms hold: (M1) For A ∈ W^{P} one has f (A) ≠ 0 if and only if A ∈ B. (M2) If A, B ∈ W^{P} satisfy 0 < d_{Γ} (A, B) < ∞ and N is a fundamental neighbour-

hood of A in ⟨A, B⟩_{Γ} relative to Γ, then one has

\begin{matrix}κ_{η,f}(A, B; N) := ε · f(A) · f(B) + \\ ∑_{C∈N \\{A\}} \overline{η}(\{C, A\}) · \overline{η}(\{ap_{⟨A,B⟩_{Γ}}(C), B\}) · f(C) · f(ap_{⟨A,B⟩_{Γ}}(C)) ∈ K_{0}. \end{matrix} (21)

ii) Two pairs (η, f), (η′, f′) as in i) where both η and η′ fit for (D_{1}, D_{2}), define the same (W; P; U)-matroid with coefficients in K and base set B if for all A ∈ W^{P} and B ∈ B with {A, B} ∈ K( Γ̃ ) one has

f (A) · f (B)^{−1} · \overline{η} (\{A, B\}) = f′ (A) · f′ (B)^{−1} · \overline{η′} (\{A, B\}) .  (22)

iii) \underline{M} := (W; P; U; (D_{1}, D_{2}); B) = (Q; B) is called a combinatorial (W; P; U)-geometry

with B as its set of bases if the following strong exchange axiom holds:

For all A, B ∈ B with A ≠ B and any fundamental neighbourhood N of A in ⟨A, B⟩_{Γ} relative to Γ there exists some C ∈ N \ {A} with C ∈ B and ap⟨A,B⟩ ; _{Γ} (C) ∈ B.

Remarks:

i) In [26, Definition 3.15], (W; P; U)-matroids (or, in short, (W; P)-matroids) with coefficients in a fuzzy ring K are defined in terms of some map

g : {(A, B) ∈ W^{P} × B | {A, B} ∈ K( Γ̃ )} → K^{∗} ˙∪ {0}

satisfying certain axioms. It then turns out (cf. [26, Theorem 5.22]) that Definition 3.12 is equivalent to [26, Definition 3.15]. More precisely, a map g as in the definition just cited corresponds to a pair (η, f) as in Definition 3.12 if and only if for all A ∈ W^{P} and B ∈ B with {A, B} ∈ K( Γ̃ ) one has

g (A, B) = f (A) · f (B)^{−1} · η̄({A, B}) ,

thereby motivating Definition 3.12 ii). ii) By Definition 2.9, any fundamental neighbourhood N as in axiom (M2) is finite; thus

the sum in (21) is well-defined in any case. The existence of the automorphisms α_{A,B} for d_{Γ} (A, B) < ∞ as required implies that for a fundamental neighbourhood {A_{0}, ..., A_{ℓ}} of A = A_{0} in ⟨A, B⟩_{Γ} relative to Γ the

set {ap⟨A,B⟩ ; _{Γ} (A_{0}) , ..., ap⟨A,B⟩ ; _{Γ} (A_{ℓ})} is a fundamental neighbourhood of B in ⟨A, B⟩_{Γ} relative to Γ. Therefore, axiom (M2) is symmetric in A and B. A sufficient condition for the existence of the automorphisms α_{A,B} is of course that the (W; P)-graph Γ is convex-antipodal. Then, by Lemma 3.7 one just may put α_{A,B} (C) := ap_{⟨A,B⟩_{Γ}} (C) for C ∈ ⟨A, B⟩_{Γ} . Consider, however, the following example (see Figure 3): Let W := ⟨r, s | (rs)^{4} = r^{2} = s^{2} = 1⟩ denote the Dieder group of order 8, and let U denote the subgroup generated by r · s. Then the triple (W; ∅; U) is 2-regular because axiom (U_{2}) is trivially fulfilled. The (W; ∅)-graph Γ is the cycle of length 8 and thus not \underline{convex}-antipodal, but Γ̃ consists of two cycles of length 4 which are certainly convex-antipodal. The graph Γ̃ satisfies all the assumptions in Definition 3.12. For two vertices A, B of Γ with d_{Γ} (A, B) = 2 there exists a unique vertex C of Γ with ⟨A, B⟩_{Γ} = {A, B, C}, and the map α = α_{A,B} : ⟨A, B⟩_{Γ} → ⟨A, B⟩_{Γ}, defined by α (A) := B, α (B) := A, α (C) := C satisfies what we want.

iii) One might probably ask for a connection between the concept of a (W, P)-matroid as introduced by I.M.Gelfand and V.V.Serganova in [14], [15] and the above Definition 3.12. In [25, §4] it is verified that for many important classes of Coxeter groups W = ⟨R⟩ and P ⊆ R we consider the same structures. Nevertheless, it is also shown that there are (W, P)-matroids in the sense of [14], [15] which do not give rise to

• r · s · r · s  ^{•} r · s · r_{•} r · s_{•} r_{•} 1_{•} s_{•} s · r  ^{•} s · r · s  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} Figure 3

combinatorial (W; P; U)-geometries, and vice versa. The condition for the graphs Γ\overline{w·U} to be convex-antipodal is a rather strong one, but I was led to require this condition in view of the formulas (GP2) and (TP2) for Grassmann-Plücker maps and twisted Pfaffian maps, respectively.

iv) For a combinatorial (W; P; U)-geometry (W; P; U; (D_{1}, D_{2}) ; B) it seems superfluous to consider the matroidal partition D = D_{1} ˙∪D_{2}. However, this partition will be of great significance when studying the concept of the Tutte group of a combinatorial (W; P; U)-geometry (cf. the forthcoming paper [27]). Note that the pair (D_{1}, D_{2}) is uniquely determined by any map η : K( Γ̃ ) → {1, −1} which satisfies axiom (D1); indeed, for {A_{1}, A_{2}, A_{3}} ∈ D one has

\{A_{1}, A_{2}, A_{3}\} ∈ \{ \begin{matrix}D_{1}, & if η (\{A_{1}, A_{2}\}) · η (\{A_{2}, A_{3}\}) · η (\{A_{3}, A_{1}\}) = 1 \\ D_{2}, & if η (\{A_{1}, A_{2}\}) · η (\{A_{2}, A_{3}\}) · η (\{A_{3}, A_{1}\}) = −1. \end{matrix}

The following first result connects (W; P; U)-matroids with coefficients and combinatorial (W; P; U)-geometries.

Proposition 3.13:

i) Assume the pair (η, f) defines a (W; P; U)-matroid M with coefficients in some fuzzy ring K with B as its set of bases, and η fits for (D_{1}, D_{2}). Then \underline{M} := (W; P; U; (D_{1}, D_{2}) ; B) is a combinatorial (W; P; U)-geometry.

ii) The combinatorial (W; P; U)-geometries are in a canonical one-to-one correspondence to the (W; P; U)-matroids with coefficients in the fuzzy ring K_{c} = R/R^{∗}.

Proof:

i) follows trivially from the axioms (M1) and (M2), because for all A, B ∈ B with A ≠ B one has d_{Γ} (A, B) < ∞ and ε · f (A) · f (B) ∉ K_{0}.

ii) For K = K_{c} one has K^{∗} = {1}. Since 1 + ... + 1 ∈ K_{0} whenever the sum contains at least two summands, it is trivial that a non-empty subset B of W^{P}, which is contained in some connected component of Γ̃, satisfies the strong exchange axiom if and only if the maps \overline{η} ≡ 1 and f : W^{P} → K^{∗} ˙∪ \{0\} defined by

f (A) := \{ \begin{matrix}1 & for A ∈ B \\ 0 & for A ∉ B \end{matrix}

satisfy axiom (M2). (Note that for any two maps η, η′ : K( Γ̃ ) → {1, −1}, which fit for one and the same matroidal partition (D_{1}, D_{2}), the pairs (η, f) and (η′, f) define the same (W; P; U)-matroid with coefficients in K_{c}, because one has \overline{η} ≡ \overline{η′} ≡ 1.)

If M and \underline{M} are as in Proposition 3.13 i), then \underline{M} is called the underlying combinatorial (W; P; U)-geometry of M.

If Q = (W; P; U; (D_{1}, D_{2})) for some k-regular triple (W; P; U) and some matroidal partition D = D_{1} ˙∪D_{2}, then we put

Q^{∗} := (W; P; U; (D_{2}, D_{1})) .

We have the following, almost trivial, but basic

Proposition 3.14. Assume K is a fuzzy ring, and the pair (η, f) defines a (W; P; U)- matroid M with coefficients in K and B as its set of bases. Then one has

i) The pair (−η, f) defines a (W; P; U)-matroid M^{∗} with coefficients in K and the same base set B.

ii) One has M^{∗∗} = M. iii) If \underline{M} = (Q; B), then one has \underline{M^{∗}} = (Q^{∗}; B).

Proof:

i) follows directly from the axioms (M1) and (M2). ii) is trivial. iii) If η fits for (D_{1}, D_{2}), then −η fits for (D_{2}, D_{1}).

Definition 3.15. If M and M^{∗} are as in Proposition 3.14, then M^{∗} is called the dual of M. The combinatorial (W; P; U)-geometry \underline{M}^{∗} is called the dual of \underline{M}.

At this point, it is not obvious that the definition of the dual of a combinatorial (W; P; U)- geometry covers the classical concept of the dual of a matroid. However, as in Example i) following Proposition 3.3, it is shown in [25, Theorem 4.8] that for W = W_{1} and P = P_{1} the combinatorial (W_{1}; P_{1}; W_{1})-geometries are precisely the ordinary matroids and that dualizing in the classical sense amounts to change the rôles of D_{1} and D_{2}; one just has to identify the cosets w · ⟨P_{1}⟩ for w ∈ W_{1} with E \ w (I_{m}) instead of w (I_{m}) by studying \underline{M}^{∗}.

4. Equivalent Representations of Combinatorial (W; P; U)-Geometries

Throughout this section assume that \underline{M} = (W; P; U; (D_{1}, D_{2}) ; B) is a combinatorial (W; P; U)-geometry. We want to study more thoroughly when two pairs (η, f) , (η′, f′) as in Definition 3.12 give rise to the same (W; P; U)-matroid with coefficients in some fixed fuzzy ring K.

Definition 4.1.

i) Suppose the pair (η, f) defines a (W; P; U)-matroid M_{1} with coefficients in the fuzzy ring K. Then (η, f) is a representation of \underline{M} over K if η fits for (D_{1}, D_{2}) and B = f^{−1} (K^{∗}), that is, \underline{M} is the underlying combinatorial (W; P; U)-geometry of M_{1}.

ii) Two representations (η, f) and (η′, f′) of \underline{M} are equivalent if they define one and the same (W; P; U)-matroid with coefficients in K, that is, equation (22) holds for all A ∈ W^{P} and B ∈ B with {A, B} ∈ K( Γ̃ ).

Note that by the definitions the pair (η, f) can be a representation of \underline{M} = (W; P; U; (D_{1}, D_{2}) ; B) only if η fits for (D_{1}, D_{2}) even in case ε = 1.

In order to compare equivalent representations of \underline{M} we shall now introduce the concept of the base graph.

Definition 4.2. The base graph Γ\underline{M} = Γ_{B} of \underline{M} is the induced subgraph Γ_{\overline{w·U},B} of Γ̃ (or of Γ\overline{w·U}) on the set B of vertices, where w ∈ W satisfies B ⊆ \overline{w · U}. If M_{1} is a (W; P; U)- matroid with coefficients in K, then the base graph Γ_{M_{1}} of M_{1} is the base graph Γ\underline{M_{1}} of its underlying combinatorial (W; P; U)-geometry.

The Examples i), ii) following Proposition 3.3 show that Definition 4.2 recovers the concepts of the base graph of a matroid and of an even Δ-matroid.

We have the following

Proposition 4.3. The base graph Γ_{B} of \underline{M} is an isometric subgraph of the connected graph Γ\overline{w·U}, where w ∈ W satisfies B ⊆ \overline{w · U}. In particular, Γ_{B} is also connected.

Proof. This is [25, Proposition 5.2]. The strong exchange axiom implies easily that for Γ′ := Γ\overline{w·U} and A, B ∈ B one has d_{Γ′} (A, B) = d_{Γ_{B}} (A, B); actually, one only has to make use of the existence of some C ∈ ⟨A, B⟩_{Γ′} ∩ B with d_{Γ′} (A, C) = 1, and then one continues by induction.

Convention. For simplicity, the metric d_{Γ_{B}} : B × B → N_{0} is from now on denoted by d_{B}. Thus, for A, B ∈ B one has

d_{B} (A, B) = d_{Γ_{B}} (A, B) = d_{Γ} (A, B) .

In the sequel, let Γ′ = Γ\overline{w·U} denote the uniquely determined connected component of the graph Γ̃ = Γ^{U} which contains the base graph Γ_{B}, and let V (Γ′) denote the vertex set of Γ′. Remember that the graph Γ′ is convex-antipodal. Finally, for A, B ∈ V (Γ′) we put

⟨A, B⟩ := ⟨A, B⟩_{Γ′} .  (23)

We have the following, quite useful

Lemma 4.4. Assume K = (K; + ; ·; ε; K_{0}) is a fuzzy ring, let η : K( Γ̃ ) → {1, −1} denote a map which fits for (D_{1}, D_{2}), and suppose that the map f : W^{P} → K^{∗} ˙∪ {0} satisfies axiom (M1) in Definition 3.12. Assume A_{0}, B_{0} ∈ V (Γ′) are distinct, and let N denote a fundamental neighbourhood of A_{0} in ⟨A_{0}, B_{0}⟩ relative to Γ. Moreover, suppose A_{1} ∈ N \ {A_{0}} and put B_{1} := ap_{⟨A_{0},B_{0}⟩} (A_{1}). Then one has

κ_{η,f} (A_{1}, B_{1}; N) = ε · \overline{η} (\{A_{0}, A_{1}\}) · \overline{η} (\{B_{0}, B_{1}\}) · κ_{η,f} (A_{0}, B_{0}; N) .  (24)

Thus, the relation κ_{η,f} (A_{1}, B_{1}; N) ∈ K_{0} holds if and only if κ_{η,f} (A_{0}, B_{0}; N) ∈ K_{0}. In particular, the pair (η, f) defines a (W; P; U)-matroid with coefficients in K if axiom (M2) holds at least for all A, B ∈ B with A ≠ B.

Proof. The second assertion is a trivial consequence of the first one. The last assertion follows from the second one, because one has κ_{η,f} (A_{0}, B_{0}; N) = 0 if there does not exist any A ∈ N with A ∈ B and ap_{⟨A_{0},B_{0}⟩} (A) ∈ B. It remains to verify (24).

Axiom (D2) of Definition 3.9 implies for any C ∈ N \ {A_{0}, A_{1}}:

sign_{(D_{1},D_{2})} ({A_{0}, A_{1}, C}) = −sign_{(D_{1},D_{2})} ({B_{0}, B_{1}, ap_{⟨A_{0},B_{0}⟩} (C)}) .

Since η fits for (D_{1}, D_{2}), this means

\begin{matrix}\overline{η} (\{A_{0}, A_{1}\}) · \overline{η} (\{A_{1}, C\}) · \overline{η} (\{C, A_{0}\}) \\ = ε · \overline{η} (\{B_{0}, B_{1}\}) · \overline{η} (\{B_{1}, ap_{⟨A_{0},B_{0}⟩} (C)\}) · \overline{η} (\{ap_{⟨A_{0},B_{0}⟩} (C) , B_{0}\}) . \end{matrix}

Together with axiom (FR2) in Definition 2.1 and the Remark following Definition 2.9 we get κ_{η,f} (A_{1}, B_{1}; N) = ε · f (A_{1}) · f (B_{1}) + \overline{η} (\{A_{0}, A_{1}\}) · \overline{η} (\{B_{0}, B_{1}\}) · f (A_{0}) · f (B_{0})

+ ∑_{C∈N \\{A_{0},A_{1}\}} \overline{η} (\{C, A_{1}\}) · \overline{η} (\{ap_{⟨A_{0},B_{0}⟩} (C) , B_{1}\}) · f (C) · f (ap_{⟨A_{0},B_{0}⟩} (C))

= ε · \overline{η} (\{A_{0}, A_{1}\}) · \overline{η} (\{B_{0}, B_{1}\})

· (\overline{η} (\{A_{1}, A_{0}\}) · \overline{η} (\{B_{1}, B_{0}\}) · f (A_{1}) · f (B_{1}) + ε · f (A_{0}) · f (B_{0})

+ ∑_{C∈N \\{A_{0},A_{1}\}} \overline{η} (\{C, A_{0}\}) · \overline{η} (\{ap_{⟨A_{0},B_{0}⟩} (C) , B_{0}\}) · f (C) · f (ap_{⟨A_{0},B_{0}⟩} (C)))

= ε · \overline{η} (\{A_{0}, A_{1}\}) · \overline{η} (\{B_{0}, B_{1}\}) · κ_{η,f} (A_{0}, B_{0}; N) .

We show now

Proposition 4.5. Assume K is a fuzzy ring, let f, f′ : W^{P} → K^{∗} ˙∪ {0} denote maps with f^{−1} (K^{∗}) = f^{′−1} (K^{∗}) = B, and suppose that the maps η, η′ : K( Γ̃ ) → {1, −1} fit for (D_{1}, D_{2}). Moreover, assume that equation (22) holds for all A ∈ W^{P} and B ∈ B with {A, B} ∈ K( Γ̃ ). Then, for A, B ∈ B with A ≠ B and any fundamental neighbourhood N of A in ⟨A, B⟩ relative to Γ one has

κ_{η′,f′} (A, B; N) = f′ (A) · f′ (B) · f (A)^{−1} · f (B)^{−1} · κ_{η,f} (A, B; N) .  (25)

In particular, (η′, f′) is a representation of \underline{M} if and only if (η, f) is.

Proof. By applying the last assertion in Lemma 4.4 to (η, f) and (η′, f′), we see that it suffices to verify (25). By (22) one gets for all C ∈ N \ {A}:

f (A) · f′ (C) · \overline{η′} (\{A, C\}) = f′ (A) · f (C) · \overline{η} (\{A, C\}) ,  (26)
\begin{aligned}f (B) · f′ (ap_{⟨A,B⟩} (C)) & · \overline{η′} (\{B, ap_{⟨A,B⟩} (C)\}) \\ & = f′ (B) · f (ap_{⟨A,B⟩} (C)) · \overline{η} (\{B, ap_{⟨A,B⟩} (C)\}) . \end{aligned}  (27)

Thus, we get by axiom (FR2) in view of f (A) , f (B) , f′ (A) , f′ (B) ∈ K^{∗}:

f (A) · f (B) · κ_{η′,f′} (A, B; N)
= ε · f (A) · f (B) · f′ (A) · f′ (B)
+ ∑_{C∈N \\{A\}} f (A) · f′ (C) · \overline{η′} (\{A, C\}) · f (B) · f′ (ap_{⟨A,B⟩} (C)) · \overline{η′} (\{ap_{⟨A,B⟩} (C) , B\})

= ε · f′ (A) · f′ (B) · f (A) · f (B)
+ ∑_{C∈N \\{A\}} f′ (A) · f (C) · \overline{η} (\{A, C\}) · f′ (B) · f (ap_{⟨A,B⟩} (C)) · \overline{η} (\{ap_{⟨A,B⟩} (C) , B\})

= f′ (A) · f′ (B) · κ_{η,f} (A, B; N) ,

and (25) follows.

The next result answers the question when two representations (η, f) and (η, f_{1}) of \underline{M}, which coincide in the first component, are equivalent.

Proposition 4.6. Suppose (η, f) is a representation of \underline{M} over the fuzzy ring K; moreover, let f_{1} : W^{P} → K^{∗} ˙∪ \{0\} denote some map. Then (η, f_{1}) is a representation of \underline{M} and equivalent to (η, f) if and only if there exists some c ∈ K^{∗} with f_{1} (A) = c · f (A) for all A ∈ W^{P}.

Proof. If there exists some c ∈ K^{∗} such that f_{1} (A) = c · f (A) holds for all A ∈ W^{P}, then by Definition 3.12 i,ii) it is trivial that (η, f_{1}) is a representation of \underline{M} which is equivalent to (η, f).

Now, assume that, vice versa, (η, f_{1}) is a representation of \underline{M} such that (22) holds for all A ∈ W^{P} and B ∈ B with {A, B} ∈ K( Γ̃ ). Then axiom (M1) implies f_{1}^{−1} (K^{∗}) = B and f_{1}^{−1} ({0}) = W^{P} \ B. Moreover, (22) implies for all A, B ∈ B with {A, B} ∈ K( Γ̃ ):

f_{1} (A) · f (A)^{−1} = f_{1} (B) · f (B)^{−1} .  (28)

Since the base graph Γ_{B} is connected, it follows that equation (28) holds for all A, B ∈ B as claimed.

Now, we want to prove the following, more general

Proposition 4.7. Suppose (η, f) is a representation of \underline{M} over the fuzzy ring K and η′ : K( Γ̃ ) → {1, −1} fits for (D_{1}, D_{2}). Then there exists some map f′ : W^{P} → K^{∗} ˙∪ {0} such that (η′, f′) is also a representation of \underline{M} which is equivalent to (η, f). The map f′ is uniquely determined up to a scalar factor.

Proof. The last assertion follows from Proposition 4.6. To show the first one, we define for any path Z = (B_{0}, ..., B_{ℓ}) in the base graph Γ_{B} the value κ (Z) = κ (B_{0}, ..., B_{ℓ}) ∈ K^{∗} by

\begin{aligned}κ (Z) & = ∏_{i=1}^{ℓ} (f (B_{i}) · f (B_{i−1})^{−1} · \overline{η} (\{B_{i−1}, B_{i}\}) · \overline{η′} (\{B_{i−1}, B_{i}\})) \\ & = f (B_{ℓ}) · f (B_{0})^{−1} · ∏_{i=1}^{ℓ} (\overline{η} (\{B_{i−1}, B_{i}\}) · \overline{η′} (\{B_{i−1}, B_{i}\})) . \end{aligned}  (29)

Clearly, for A, B ∈ B with {A, B} ∈ K( Γ̃ ) one has κ (A, B) = κ (B, A)^{−1}, and for any path Z = (B_{0}, ..., B_{ℓ}) in Γ_{B} we have

κ (Z) = ∏_{i=1}^{ℓ} κ (B_{i−1}, B_{i}) .

We want to show that for any path Z = (B_{0}, ..., B_{ℓ}) in Γ_{B} the value κ (Z) depends only on the bases B_{0} and B_{ℓ}. This amounts to prove that for any reentrant path Z in Γ_{B} one has κ (Z) = 1. By [25, Theorem 5.7], which generalizes Maurer’s homotopy theorem for ordinary matroids, we have only to verify the following two claims: (I) If Z = (A_{0}, A_{1}, A_{2}, A_{0}) is a reentrant path in Γ_{B} of length 3, then one has κ (Z) = 1. (II) If Z = (A_{0}, A_{1}, A_{2}, A_{3}, A_{0}) is an isometric reentrant path in Γ_{B} of length 4, then one

has κ (Z) = 1. Note that (29) implies for any reentrant path Z = (B_{0}, ..., B_{ℓ}) in Γ_{B} the equation

κ (Z) = ∏_{i=1}^{ℓ} (\overline{η} (\{B_{i−1}, B_{i}\}) · \overline{η′} (\{B_{i−1}, B_{i}\})) .

Thus, (I) follows from the identity (sign_{(D_{1},D_{2})} ({A_{0}, A_{1}, A_{2}}))^{2} = 1, because both η and η′ fit for (D_{1}, D_{2}). (II) follows from the fact that η and η′ are four-balanced (cf. Definitions 3.9 i) and 3.11 i)). Now, by what we have already proved we may define f′ : W^{P} → K^{∗} ˙∪ {0} as follows:

Choose some fixed B_{0} ∈ B, put f′ (B_{0}) = 1, and for any B ∈ B choose some path Z = (B_{0}, ..., B_{ℓ}) in Γ_{B} with B_{ℓ} = B and put f′ (B) := κ (Z). Furthermore, of course, we put f′ (A) := 0 for A ∈ W^{P} \ B. By (29) and the definition of f′ it is trivial that (22) is fulfilled for all A ∈ W^{P} and B ∈ B with {A, B} ∈ K( Γ̃ ). Thus Proposition 4.5 implies that (η′, f′) is also a representation of \underline{M}, which, in view of (22), is equivalent to (η, f).

In the forthcoming paper [27], we shall use the extension of Maurer’s homotopy theory and the concept of the Tutte group of a combinatorial (W; P; U)-geometry in order to derive a second equivalent definition of (W; P; U)-matroids with coefficients (cf. also [26, Definition 3.15]). While Definition 3.12 will be used in the next section when studying examples of (W; P; U)-matroids with coefficients, the alternative definition is more convenient for many theoretical considerations.

5. Examples of (W; P; U)-Matroids with Coefficients in a Fuzzy Ring

In this section, we want to show that with the notations as in the Examples i), ii) following Proposition 3.3 the ordinary matroids with coefficients are precisely the (W_{1}; P_{1}; W_{1})- matroids with coefficients and that the Δ-matroids with coefficients are the (W_{2}; P_{2}; U_{Δ})- matroids with coefficients.

In the sequel, assume that m, n are fixed integers with 0 ≤ m ≤ n, put E := {1, ..., n}, and identify W_{1}^{P_{1}} via χ with \binom{E}{m} in the Example i) just mentioned, and as above let Γ_{1} denote the (W_{1}; P_{1})-graph. Furthermore, put

D_{0} := \{\{A_{1}, A_{2}, A_{3}\} ⊆ \binom{E}{m} | d_{Γ_{1}} (A_{i}, A_{j}) = 1 for 1 ≤ i < j ≤ 3 \},  (30)

D_{0,1} := \{\{A ∪ \{a_{1}\} , A ∪ \{a_{2}\} , A ∪ \{a_{3}\}\} | A ∈ \binom{E}{m−1}, a_{i} ∈ E \ A ; and a_{i} ≠ a_{j} for i ≠ j \},  (31)

D_{0,2} := \{\{A \ \{a_{1}\} , A \ \{a_{2}\} , A \ \{a_{3}\}\} | A ∈ \binom{E}{m+1}, a_{i} ∈ A ; and a_{i} ≠ a_{j} for i ≠ j \}.  (32)

Clearly, D_{0} is the set of triangles in Γ_{1}, and we have D_{0} = D_{0,1} ˙∪D_{0,2}. Now, we recall the following combinatorial result.

Proposition 5.1.

i) Assume A_{0} and B are distinct vertices of the graph Γ_{1}. Then a subset N ⊆ ⟨A_{0}, B⟩_{Γ_{1}} is a fundamental neighbourhood of A_{0} in ⟨A_{0}, B⟩_{Γ_{1}} if and only if there exists some a_{0} ∈ A_{0} \ B with

N = {A_{0}} ∪ {(A_{0} \ {a_{0}}) ∪ {b} | b ∈ B \ A_{0}}  (33)

or some b_{0} ∈ B \ A_{0} with

N = {A_{0}} ∪ {(A_{0} \ {a}) ∪ {b_{0}} | a ∈ A_{0} \ B} .  (34)

ii) The partition D_{0} = D_{0,1} ˙∪D_{0,2} is matroidal, and this partition is – apart from the order – the only matroidal partition of D_{0}. Moreover, the map η_{1} : K (Γ_{1}) → {1, −1} defined by

η_{1} ({D ∪ {e} , D ∪ {f}}) := (−1)^{#{d∈D|e<d<f}}
for D ∪ {e, f} ⊆ E with # (D ∪ {e, f}) = #D + 2 = m + 1 and e < f

(35)

fits for (D_{0,1}, D_{0,2}). iii) The ordinary matroids defined on E and of rank m are in a canonical one-to-one corre-

spondence to the combinatorial (W_{1}; P_{1}; W_{1})-geometries (W_{1}; P_{1}; W_{1}; (D_{0,1}, D_{0,2}) ; B), where only B is varying, and any combinatorial (W_{1}; P_{1}; W_{1})-geometry or its dual is of this type.

Proof.

i) is [25, Proposition 4.1i)], ii) is [25, Proposition 4.7], and iii) is [25, Theorem 4.8i)].

Assume σ ∈ W_{1} = S_{n}. Since for i ∈ {1, 2} and any {A_{1}, A_{2}, A_{3}} ∈ D_{0,i} one has also {σ (A_{1}) , σ (A_{2}) , σ (A_{3})} ∈ D_{0,i}, it follows trivially that the map η_{σ} : K (Γ_{1}) → {1, −1}, defined by

η_{σ} ({A, B}) := η_{1} ({σ (A) , σ (B)})  (36)

fits for (D_{0,1}, D_{0,2}), too.

In order to relate ordinary matroids with coefficients to (W_{1}; P_{1}; W_{1})-matroids with coefficients, we prove the following

Lemma 5.2. Assume K = (K; + ; ·; ε; K_{0}) is a fuzzy ring, suppose σ ∈ W_{1}, and let b̃, b̃_{σ} : \binom{E}{m} → K^{∗} ˙∪ \{0\} and b : E^{m} → K^{∗} ˙∪ \{0\} denote maps which are related by the formulas

b̃({a_{1}, ..., a_{m}}) =b (a_{1}, ..., a_{m}) whenever a_{i} < a_{j} for 1 ≤ i < j ≤ m,  (37)
b̃_{σ} ({a_{1}, ..., a_{m}}) =b (a_{1}, ..., a_{m}) whenever σ (a_{i}) < σ (a_{j}) for 1 ≤ i < j ≤ m. (38)

Moreover, suppose b satisfies axiom (GP1) in Definition 2.2. Then the following statements hold:

i) Assume a_{1}, ..., a_{m−1}, e, f ∈ E are pairwise distinct, put D := {a_{1}, ..., a_{m−1}}, A := D ∪ {e}, B := D ∪ {f}, and suppose b̃(B) ≠ 0. Then one has

\begin{matrix}b̃(A) · b̃(B)^{−1} · \overline{η_{1}} (\{A, B\}) = & b (a_{1}, ..., a_{m−1}, e) · b (a_{1}, ..., a_{m−1}, f)^{−1} \\ = & b̃_{σ} (A) · b̃_{σ} (B)^{−1} · \overline{η}_{σ} (\{A, B\}) . \end{matrix}

ii) Assume 1 ≤ ℓ ≤ m, and e_{0}, ..., e_{m}, f_{2}, ..., f_{m} ∈ E satisfying e_{i} = f_{i} for ℓ + 1 ≤ i ≤ m, but e_{0}, ..., e_{m}, f_{2}, ..., f_{ℓ} are pairwise distinct. Suppose A_{0}, B_{0} ∈ \binom{E}{m} satisfy

A_{0} = {e_{1}, ..., e_{m}} , B_{0} = {e_{0}, f_{2}, ..., f_{m}} .

Then N := {(A_{0} \ {e_{i}}) ∪ {e_{0}} | 1 ≤ i ≤ ℓ} ˙∪ {A_{0}} is a fundamental neighbourhood of A_{0} in ⟨A_{0}, B_{0}⟩ := ⟨A_{0}, B_{0}⟩_{Γ_{1}}. If σ satisfies σ (e_{i_{1}}) < σ (e_{i_{2}}) < σ (f_{i_{3}}) ≤ σ (f_{i_{4}}) for all i_{1}, i_{2}, i_{3}, i_{4} with 0 ≤ i_{1} < i_{2} ≤ ℓ and 2 ≤ i_{3} ≤ i_{4} ≤ m, then one has

∑_{i=0}^{ℓ} ε^{i} · b (e_{0}, ..., ê_{i}, ..., e_{m}) · b (e_{i}, f_{2}, ..., f_{m}) = ε · κ_{η_{σ},_{b_{σ}}} (A_{0}, B_{0}; N) .  (39)

Proof:

i) Suppose D = {d_{1}, ..., d_{m−1}} = {d′_{1}, ..., d′_{m−1}}, where d_{i} < d_{j} and σ (d′_{i}) < σ (d′_{j}) for 1 ≤ i < j ≤ m − 1. Furthermore, put

\begin{matrix}r_{1} := # \{d ∈ D | e < d\} & , & r_{2} := # \{d ∈ D | f < d\} , \\ r_{3} := # \{d ∈ D | σ(e) < σ (d)\} & , & r_{4} := # \{d ∈ D | σ(f) < σ (d)\} . \end{matrix}

Then, we get by (37), (38) and a repeated application of axiom (GP1):

b̃(D ∪ \{e\}) · b̃(D ∪ \{f\})^{−1} · \overline{η}_{1} (\{D ∪ \{e\} , D ∪ \{f\}\})
= (b (d_{1}, ..., d_{m−1}, e) · ε^{r_{1}}) · (b (d_{1}, ..., d_{m−1}, f) · ε^{r_{2}})^{−1} · ε^{r_{2}−r_{1}}
= b (a_{1}, ..., a_{m−1}, e) · b (a_{1}, ..., a_{m−1}, f)^{−1}
= b (d′_{1}, ..., d′_{m−1}, e) · b (d′_{1}, ..., d′_{m−1}, f)^{−1}
= (b̃_{σ} (D ∪ {e}) · ε^{r_{3}}) · (b̃_{σ} (D ∪ {f}) · ε^{r_{4}})^{−1}
= b̃_{σ} (D ∪ \{e\}) · b̃_{σ} (D ∪ \{f\})^{−1} · \overline{η}_{σ} (\{D ∪ \{e\} , D ∪ \{f\}\}) .

ii) By Proposition 5.1 i) we already know that N is a fundamental neighbourhood of A_{0} in ⟨A_{0}, B_{0}⟩. By (38) and our assumption concerning σ and the elements e_{0}, ..., e_{m}, f_{2}, ..., f_{m}, we have

b (e_{0}, ..., ê_{i}, ..., e_{m}) = b̃_{σ} ((A_{0} ∪ {e_{0}}) \ {e_{i}}) for 0 ≤ i ≤ ℓ,
b (e_{i}, f_{2}, ..., f_{m}) = b̃_{σ} ((B_{0} \ {e_{0}}) ∪ {e_{i}})  for 0 ≤ i ≤ ℓ,
\overline{η}_{σ} (\{(A_{0} \ \{e_{i}\}) ∪ \{e_{0}\} , A_{0}\}) = ε^{i−1}  for 1 ≤ i ≤ ℓ,
\overline{η}_{σ} (\{(B_{0} \ \{e_{0}\}) ∪ \{e_{i}\} , B_{0}\}) = 1  for 1 ≤ i ≤ ℓ.

Thus, we obtain

∑_{i=0}^{ℓ} ε^{i} · b (e_{0}, ..., ê_{i}, ..., e_{m}) · b (e_{i}, f_{2}, ..., f_{m})

= b̃_{σ} (A_{0}) · b̃_{σ} (B_{0}) + ∑_{i=1}^{ℓ} ε^{i} · b̃_{σ} ((A_{0} \ {e_{i}}) ∪ {e_{0}}) · b̃_{σ} ((B_{0} \ {e_{0}}) ∪ {e_{i}})

= b̃_{σ} (A_{0}) · b̃_{σ} (B_{0})

+ ∑_{C∈N \\{A_{0}\}} ε · \overline{η}_{σ} (\{C, A_{0}\}) · \overline{η}_{σ} (\{ap_{⟨A_{0},B_{0}⟩} (C) , B_{0}\}) · b̃_{σ} (C) · b̃_{σ} (ap_{⟨A_{0},B_{0}⟩} (C))

= ε · κ_{η_{σ},_{b_{σ}}} (A_{0}, B_{0}; N) .

If K = (K; + ; ·; ε; K_{0}) is a fuzzy ring, then as a technical notation we put for any permutation τ of some finite set

sign_{ε}τ := \{ \begin{matrix}ε & if τ is odd, \\ 1 & if τ is even, \end{matrix}

and for pairwise distinct e_{1}, ..., e_{m} ∈ E let τ = τ (e_{1}, ..., e_{m}) denote the unique permutation of {e_{1}, ..., e_{m}} with τ (e_{i}) < τ (e_{j}) for 1 ≤ i < j ≤ m.

Now, we are able to state and to prove the following

Theorem 5.3. Assume K = (K; + ; ·; ε; K_{0}) is a fuzzy ring. Then there is a canonical one-to-one correspondence between the ordinary matroids with coefficients in K, defined on E and of rank m, and the (W_{1}; P_{1}; W_{1})-matroids with coefficients in K endowed with the ordered matroidal partition D_{0} = D_{0,1} ˙∪D_{0,2}. The correspondence is as follows:

If B is the set of bases of a (W_{1}; P_{1}; W_{1})-matroid with coefficients in K and b̃: \binom{E}{m} → K^{∗} ˙∪ \{0\} is a map such that (η_{1}, b̃) is a representation of (W_{1}; P_{1}; W_{1}; (D_{0,1}, D_{0,2}) ; B), then the map b : E^{m} → K^{∗} ˙∪ {0} defined by

b (e_{1}, ..., e_{m}) := \{ \begin{matrix}sign_{ε}τ (e_{1}, ..., e_{m}) · b̃(\{e_{1}, ..., e_{m}\}) & if e_{1}, ..., e_{m} ∈ E \\ & are pairwise distinct \\ 0 & otherwise \end{matrix}  (40)

is a corresponding Grassmann-Plücker map.

Vice versa, if b : E^{m} → K^{∗} ˙∪ \{0\} is a Grassmann-Plücker map and b̃: \binom{E}{m} → K^{∗} ˙∪ \{0\} is defined by

b̃({e_{1}, ..., e_{m}}) := b (e_{1}, ..., e_{m}) whenever e_{i} < e_{j} for 1 ≤ i < j ≤ m,  (41)

then (η_{1}, b̃) is a corresponding representation.

Proof. Assume first that (η_{1}, b̃) defines a (W_{1}; P_{1}; W_{1})-matroid M with coefficients in K and B as its set of bases. Then the map b : E^{m} → K^{∗} ˙∪ {0} as defined in (40) satisfies trivially axiom (GP1) while axiom (GP0) follows from axiom (M1) and B ≠ ∅. We still have to verify axiom (GP2).

Assume e_{0}, ..., e_{m}, f_{2}, ..., f_{m} ∈ E and put

κ_{0} := ∑_{i=0}^{m} ε^{i} · b (e_{0}, ..., ê_{i}, ..., e_{m}) · b (e_{i}, f_{2}, ..., f_{m}) .

We must show that κ_{0} ∈ K_{0}.

If there exist i_{1}, i_{2} with 2 ≤ i_{1} < i_{2} ≤ m and f_{i_{1}} = f_{i_{2}}, then one has trivially κ_{0} = 0. Moreover, if e_{i_{1}} = e_{i_{2}} for some i_{1}, i_{2} with 0 ≤ i_{1} < i_{2} ≤ m, then one gets

κ_{0} = b (e_{0}, ..., ê_{i_{2}}, ..., e_{m}) · b (e_{i_{2}}, f_{2}, ..., f_{m}) · (ε^{i_{1}} · ε^{i_{2}−i_{1}−1} + ε^{i_{2}}) ∈ K_{0}.

Thus, from now on we assume that # {e_{0}, ..., e_{m}} = m + 1 and # {f_{2}, ..., f_{m}} = m − 1. Suppose i_{0}, j_{0} are such that 0 ≤ i_{0} ≤ m − 1 and 2 ≤ j_{0} ≤ m − 1, and put e′_{i_{0}} := e_{i_{0}+1}, e′_{i_{0}+1} := e_{i_{0}}, e′_{i} := e_{i} for i ∈ {0, ..., m} \ {i_{0} , i_{0} + 1} and f′_{j_{0}} := f_{j_{0}+1}, f′_{j_{0}+1} := f_{j_{0}}, f′_{i} := f_{i} for i ∈ {2, ..., m} \ {j_{0} , j_{0} + 1}. Then one has

\begin{aligned}κ_{0} & = ε · ∑_{i=0}^{m} ε^{i} · b (e_{0}, ..., ê_{i}, ..., e_{m}) · b (e_{i}, f′_{2}, ..., f′_{m}) \\ & = ε · ∑_{i=0}^{m} ε^{i} · b (e′_{0}, ..., ê′_{i} , ..., e′_{m}) · b (e′_{i}, f_{2}, ..., f_{m}) . \end{aligned}

Thus, we may also assume that there exists some ℓ with 1 ≤ ℓ ≤ m and e_{i} = f_{i} for ℓ+1 ≤ i ≤ m but that e_{0}, ..., e_{m}, f_{2}, ..., f_{ℓ} are pairwise distinct. Let σ : E → E denote some bijection with σ (e_{i_{1}}) < σ (e_{i_{2}}) < σ (f_{i_{3}}) ≤ σ (f_{i_{4}}) for all i_{1}, i_{2}, i_{3}, i_{4} with 0 ≤ i_{1} < i_{2} ≤ ℓ and 2 ≤ i_{3} ≤ i_{4} ≤ m, and let b̃_{σ} : \binom{E}{m} → K^{∗} ˙∪ \{0\} denote the unique map satisfying (38). Now, by Lemma 5.2 i) and Proposition 4.5 we conclude that (η_{σ}, b̃_{σ}) is also a representation of M. Thus, Lemma 5.2 ii) yields that κ_{0} ∈ K_{0}.

Now, assume that vice versa b : E^{m} → K^{∗} ˙∪ {0} is a Grassmann-Plücker map. Then, by Proposition 5.1 iii), we know already that the set B of bases of M_{b} defines a combinatorial (W_{1}; P_{1}; W_{1})-geometry. Moreover, the map b̃: \binom{E}{m} → K^{∗} ˙∪ \{0\} as defined in (41) satisfies axiom (M1) by definition. To verify that b̃ also satisfies (M2), assume that A_{0}, B_{0} ∈ \binom{E}{m} are distinct and N is a fundamental neighbourhood of A_{0} in ⟨A_{0}, B_{0}⟩. We must prove that

κ_{η_{1},_{b}}(A_{0}, B_{0}; N) ∈ K_{0}.

By Lemma 4.4, we may assume that A_{0}, B_{0} ∈ B. Furthermore, by Proposition 5.1 i)

and the trivial equation κ_{η_{1},_{b}}(A_{0}, B_{0}; N) = κ_{η_{1},_{b}}(B_{0}, A_{0}; N′) for N′ := {ap_{⟨A_{0},B_{0}⟩} (C) |

C ∈ N } we may suppose that there exists some e_{0} ∈ B_{0} \ A_{0} such that

N = {A_{0}} ∪ {(A_{0} \ {e}) ∪ {e_{0}} | e ∈ A_{0} \ B_{0}} .

Put ℓ := # (B_{0} \ A_{0}), and assume A_{0} = {e_{1}, ..., e_{m}}, B_{0} = {e_{0}, f_{2}, ..., f_{m}}, where e_{i} = f_{i} for ℓ + 1 ≤ i ≤ m. Then e_{0}, e_{1}, ..., e_{m}, f_{2}, ..., f_{ℓ} are pairwise distinct, and as above we may choose some bijection σ : E → E with σ (e_{i_{1}}) < σ (e_{i_{2}}) < σ (f_{i_{3}}) ≤ σ (f_{i_{4}}) for all i_{1}, i_{2}, i_{3}, i_{4} with 0 ≤ i_{1} < i_{2} ≤ ℓ and 2 ≤ i_{3} ≤ i_{4} ≤ m. Then for the unique map b̃_{σ} : \binom{E}{m} → K^{∗} ˙∪ \{0\} which satisfies (38) one has κ_{η_{σ},_{b_{σ}}} (A_{0}, B_{0}; N) ∈ K_{0} by Lemma 5.2 ii), because b satisfies axiom (GP2). Now, Lemma 5.2 i) and Proposition 4.5 imply also κ_{η_{1},_{b}}(A_{0}, B_{0}; N) ∈ K_{0}.

Proposition 4.6 implies that two Grassmann-Plücker maps b, b′ : E^{m} → K^{∗} ˙∪ {0} are equivalent if and only if the corresponding maps b̃, b̃′ : \binom{E}{m} → K^{∗} ˙∪ \{0\} give rise to equivalent representations (η_{1}, b̃) and (η_{1}, b̃′). Since by Proposition 4.7 any representation of a combinatorial (W_{1}; P_{1}; W_{1})-geometry is equivalent to some representation of the form (η_{1}, b̃), the proof is complete.

Now, we turn to Δ-matroids with coefficients. As in Example ii) following Proposition 3.3 identify W_{2}^{P_{2}} via χ′′ with P (E), and – as above – let Γ̃_{2} = Γ_{2}^{U_{Δ}} = (V ( Γ̃_{2}), K( Γ̃_{2}))

denote the graph with V ( Γ̃_{2}) = E and {A, B} ∈ K( Γ̃_{2}) if and only if # (AΔB) = 2. Furthermore, put

D̃_{0} := {{A_{1}, A_{2}, A_{3}} ⊆ P (E) | d_{Γ_{2}} (A_{i}, A_{j}) = 1 for 1 ≤ i < j ≤ 3} ,  (42)

\begin{aligned}D̃_{1} := \{\{AΔ \{a_{1}\} , AΔ \{a_{2}\} , AΔ \{a_{3}\}\} | & A ⊆ E, \\ & 1 ≤ a_{1} < a_{2} < a_{3} ≤ n, a_{2} ∉ A\}, \end{aligned}  (43)

\begin{aligned}D̃_{2} := \{\{AΔ \{a_{1}\} , AΔ \{a_{2}\} , AΔ \{a_{3}\}\} | & A ⊆ E, \\ & 1 ≤ a_{1} < a_{2} < a_{3} ≤ n, a_{2} ∈ A\}. \end{aligned}  (44)

It is easily verified that D̃_{0} = D̃_{1} ˙∪D̃_{2} (cf. also [25, Lemma 4.4]). Moreover, we have the following

Proposition 5.4.

i) Let A_{0}, B denote distinct vertices of the graph Γ̃_{2} with #A_{0} ≡ #B mod 2. Then a subset N ⊆ ⟨A_{0}, B⟩_{Γ_{2}} is a fundamental neighbourhood of A_{0} in ⟨A_{0}, B⟩_{Γ_{2}} relative to Γ_{2} if and only if there exists some c_{0} ∈ A_{0}ΔB such that

N = {A_{0}Δ {c_{0}} Δ {d} | d ∈ A_{0}ΔB} .  (45)

ii) The partition D̃_{0} = D̃_{1} ˙∪D̃_{2} is matroidal, and this partition is – apart from the order – the only matroidal partition of D̃_{0}. Moreover, the map η_{2} : K( Γ̃_{2}) → {1, −1} defined by

η_{2} ({AΔ {a} , AΔ {b}}) := (−1)^{#{i∈A|a<i<b}} for A ⊆ E, 1 ≤ a < b ≤ n  (46)

fits for (D̃_{1}, D̃_{2}).

iii) The even Δ-matroids defined on E are in a canonical one-to-one correspondence to the combinatorial (W_{2}; P_{2}; U_{Δ})-geometries (W_{2}; P_{2}; U_{Δ}; (D̃_{1}, D̃_{2}); B), where only B is varying, and any combinatorial (W_{2}; P_{2}; U_{Δ})-geometry or its dual is of this type.

Proof.

i) is [25, Proposition 4.1ii)], ii) is [25, Proposition 4.5], and iii) is [25, Theorem 4.8ii)].

We shall now prove the following

Theorem 5.5. Assume K = (K; + ; ·; ε; K_{0}) is a fuzzy ring. Then there is a canonical oneto-one correspondence between the Δ-matroids with coefficients in K, defined on E, and the (W_{2}; P_{2}; U_{Δ})-matroids with coefficients in K endowed with the ordered matroidal partition D̃_{0} = D̃_{1} ˙∪D̃_{2}. More precisely, for an even Δ-matroid (E, B) a map p : P (E) → K^{∗} ˙∪ {0} with p^{−1} (K^{∗}) = B is a twisted Pfaffian map if and only if (η_{2}, p) is a representation of (W_{2}; P_{2}; U_{Δ}; (D̃_{1}, D̃_{2}); B).

Proof. Assume that (E, B) is an even Δ-matroid and p : P (E) → K^{∗} ˙∪ {0} is a map with B = p^{−1} (K^{∗}). Then one has B ≠ ∅ and #B_{1} ≡ #B_{2} mod 2 for all B_{1}, B_{2} ∈ B. Thus, it is trivial that p satisfies the axioms (TP0), (TP1) and (M1). It remains to show that (TP2) and (M2) are equivalent. Assume A, B ⊆ E and AΔB = {i_{1}, ..., i_{ℓ}} with ℓ ≥ 2, ℓ ≡ 0 mod2, i_{j} < i_{j+1} for 1 ≤ j ≤ ℓ − 1, and for some fixed ν with 1 ≤ ν ≤ ℓ put A′ := AΔ {i_{ν}}, B′ := BΔ {i_{ν}} and N := {A′Δ {i_{j}} | 1 ≤ j ≤ ℓ}. By Proposition 5.4 i) the equivalence of the axioms (TP2) and (M2) follows once it is shown that

κ_{η_{2},p} (A, B; N) = ε^{ν−1} · ∑_{j=1}^{ℓ} ε^{j} · p (A′Δ {i_{j}}) · p (B′Δ {i_{j}}) .  (47)

We get

\begin{matrix}κ_{η_{2} ,p} (A, B; N) \\ = ε · p (A) · p (B) + ∑_{C∈N \\{A\}} \overline{η}_{2} (\{C, A\}) · \overline{η}_{2} (\{AΔBΔC, B\}) · p (C) · p (AΔBΔC) = \end{matrix}

= ε · p (A′Δ {i_{ν}}) · p (B′Δ {i_{ν}})

+ ∑_{j=1,j≠ν}^{ℓ} \overline{η}_{2} (\{A′Δ \{i_{j}\} , A′Δ \{i_{ν}\}\}) · \overline{η}_{2} (\{B′Δ \{i_{j}\} , B′Δ \{i_{ν}\}\}) · p (A′Δ \{i_{j}\}) · p (B′Δ \{i_{j}\})

= ε · p (A′Δ {i_{ν}}) · p (B′Δ {i_{ν}})

+ ∑_{j=1}^{ν−1} ε^{#{e∈A′|i_{j}<e<i_{ν}}+#{e∈B′|i_{j}<e<i_{ν}}} · p (A′Δ {i_{j}}) · p (B′Δ {i_{j}})

+ ∑_{j=ν+1}^{ℓ}ε^{#{e∈A′ΔB′|i_{ν}<e<i_{j}}} · p (A′Δ {i_{j}}) · p (B′Δ {i_{j}})

= ε · p (A′Δ {i_{ν}}) · p (B′Δ {i_{ν}}) + ∑_{j=1,j≠ν}^{ℓ}ε^{j−ν−1} · p (A′Δ {i_{j}}) · p (B′Δ {i_{j}})

= ε^{ν−1} · ∑_{j=1}^{ℓ} ε^{j} · p (A′Δ {i_{j}}) · p (B′Δ {i_{j}}) ,

and (47) is proved.

Finally, Propositions 4.6 and 4.7 show that the equivalence classes of twisted Pfaffian maps are in a one-to-one correspondence to the equivalence classes of representations of combinatorial (W_{2}; P_{2}; U_{Δ})-geometries.

Remark. If p : P (E) → K^{∗} ˙∪ {0} is a twisted Pfaffian map, then by [23, Definition 3.4] a twisted Pfaffian map p^{∗} : P (E) → K^{∗} ˙∪ {0} of the dual of M_{p} is given by

p^{∗} (F) := ε^{Σ^{e∈F} e} · p (E \ F) .  (48)

Assume A ⊆ E and e, f ∈ E such that e ≠ f and p^{∗} (AΔ {f}) ≠ 0. Then we get

p^{∗} (AΔ \{e\}) · p^{∗} (AΔ \{f\})^{−1} · \overline{η}_{2} (\{AΔ \{e\} , AΔ \{f\}\})
= ε^{f−e} · p (E \ (AΔ {e})) · p (E \ (AΔ {f}))^{−1}
· ε^{f−e−1} · \overline{η}_{2} (\{E \ (AΔ \{e\}) , E \ (AΔ \{f\})\})
= p (E \ (AΔ \{e\})) · p (E \ (AΔ \{f\}))^{−1} · (ε · \overline{η}_{2} (\{E \ (AΔ \{e\}) , E \ (AΔ \{f\})\})) .

Thus – if we identify the cosets w · ⟨P_{2}⟩ for w ∈ W_{2} with E \ w (E) instead of E ∩ w (E) when studying M_{p∗} – we see that Definition 3.15 recovers the definition of the dual of a Δ-matroid with coefficients. Similarly, it follows that Definition 3.15 is consistent with the definition of the dual of a matroid with coefficients (cf. also [8, §5], [26, §6]), but this is now also a consequence of [23, §4], where it is shown that the matroids with coefficients are precisely the Δ-matroids with coefficients and equicardinal feasible sets and that for a matroid M with coefficients its dual M^{∗} means the same in matroid theory as in Δ-matroid theory.

At the end of this paper, we want to study (W; P; W)-matroids with coefficients, where W = ⟨R⟩ is an \underline{abelian} Coxeter group, that is, an F_{2}-vector space with a distinguished base. For any w ∈ W let R (w) denote the uniquely determined subset of R with

w = ∏_{r∈R(w)}r.  (49)

Let Γ denote the (W; P)-graph. It is obvious that Γ is convex-antipodal; for w_{1}, w_{2} ∈ W and w · W_{P} ∈ ⟨\overline{w}_{1}, \overline{w}_{2}⟩ := ⟨w_{1} · W_{P} , w_{2} · W_{P} ⟩_{Γ} one has

ap_{⟨\overline{w}_{1},\overline{w}_{2}⟩} (w · W_{P}) = w_{1} · w_{2} · w · W_{P} .

Moreover, for w_{0}, w_{1}, w_{2} ∈ W and r ∈ R\P one has r.w_{1}.w_{0}.W_{P} ∈ ⟨w_{1}.w_{0}.W_{P} , w_{2}.w_{0}.W_{P} ⟩_{Γ} if and only if r.W_{P} ∈ ⟨W_{P} , w_{1}.w_{2}.W_{P} ⟩_{Γ} if and only if r ∈ (R \ P) ∩ R (w_{1}.w_{2}).

Let η_{0} : K (Γ) → {1, −1} denote the constant map given by

η_{0} ({r · w · W_{P} , w · W_{P} }) := 1 for all w ∈ W and r ∈ R \ P.  (50)

In the (W; P)-graph Γ the length of any reentrant path is trivially even, and thus Γ does not contain any triangle. This means in particular that the map η_{0} fits for (∅, ∅).

Now, we have the following

Proposition 5.6. Assume W = ⟨R⟩ is an abelian Coxeter group, P ⊆ R, B ⊆ W^{P}, and let K denote a fuzzy ring. Then one has

i) The following four conditions are equivalent: (a) The tuple \underline{M} := (W; P; W; (∅, ∅) ; B) is a combinatorial (W; P; W)-geometry.

(b) The triple (W, P, B) is a (W, P)-matroid in the sense of [14], [15].

(c) B is a non-empty convex subset of (W^{P} , d_{Γ}).

(d) There exists some w_{0} ∈ W and some parabolic subgroup W′ = ⟨P′⟩ of W with

P ⊆ P′ ⊆ R and

W′ = {w ∈ W | w · w_{0} · W_{P} ∈ B} .  (51)

ii) Assume B satisfies the four equivalent conditions in i), and suppose in particular that w_{0} and W′ = ⟨P′⟩ are as in i)(d). Then for a map f : W^{P} → K^{∗} ˙∪ {0} the pair (η_{0}, f) is a representation of \underline{M} if and only if there exists some κ ∈ K^{∗} and some map ψ : P′ \ P → K^{∗} such that for w ∈ ⟨R \ P ⟩ one has

f (w · w_{0} · W_{P}) = \{ \begin{matrix}κ · ∏_{r∈R(w)}ψ (r) & if w ∈ ⟨P′ \ P ⟩ \\ 0 & if w ∈ W \ W′. \end{matrix}  (52)

In particular, for every fuzzy ring K there exists at least one (W; P; W)-matroid with coefficients in K and B as its set of bases.

Proof:

i) is [25, Proposition 4.10]. ii) Assume first that f is as in (52). Then by (51) we have

f^{−1} (K^{∗}) = {w · w_{0} · W_{P} | w ∈ W′} = B;

thus axiom (M1) holds. To verify (M2) assume – in view of Lemma 4.4 – that A, B ∈ B are distinct, and N is a fundamental neighbourhood of A in ⟨A, B⟩ := ⟨A, B⟩_{Γ}. Since Γ does not contain any triangles, we have N = {A, C} for some C ∈ W^{P} with 1 = d_{Γ} (A, C) = d_{Γ} (A, B) − d_{Γ} (C, B). By (51) there exist w_{1}, w_{2} ∈ W′ with A = w_{1} · w_{0} · W_{P} and B = w_{2} · w_{0} · W_{P}, and we have C = r · w_{1} · w_{0} · W_{P} for some r ∈ (P′ \ P) ∩ R (w_{1} · w_{2}). Then we get ap_{⟨A,B⟩} (C) = r · w_{2} · w_{0} · W_{P} and either {r} = R (r · w_{1}) \ R (w_{1}) = R (w_{2}) \ R (r · w_{2}) or {r} = R (r · w_{2}) \ R (w_{2}) = R (w_{1}) \ R (r · w_{1}). By (52) this means in any case

κ_{η_{0,f}} (A, B; N)

= ε · f (w_{1} · w_{0} · W_{P}) · f (w_{2} · w_{0} · W_{P}) + f (r · w_{1} · w_{0} · W_{P}) · f (r · w_{2} · w_{0} · W_{P})

= f (w_{1} · w_{0} · W_{P}) · f (w_{2} · w_{0} · W_{P}) · (ε + ψ (r) · ψ (r)^{−1}) ∈ K_{0}.

Now suppose that vice versa (η_{0}, f) is a representation of \underline{M}. We prove that for w_{1}, w_{2} ∈ W′ and r ∈ P′ \ P with R (r · w_{i}) = R (w_{i}) ˙∪ {r} for i ∈ {1, 2} one has

\begin{matrix}f (r · w_{1} · w_{0} · W_{P}) · f (w_{1} · w_{0} · W_{P})^{−1} \\ = f (r · w_{2} · w_{0} · W_{P}) · f (w_{2} · w_{0} · W_{P})^{−1} . \end{matrix}  (53)

Put A := w_{1} · w_{0} · W_{P}, B := r · w_{2} · w_{0} · W_{P}, C := r · w_{1} · w_{0} · W_{P}. The relation r ∉ R (w_{1}) ∪ R (w_{2}) implies C ∈ ⟨A, B⟩ and ap_{⟨A,B⟩} (C) = w_{2} · w_{0} · W_{P}. Since {A, C} is a fundamental neighbourhood of A in ⟨A, B⟩, axiom (M2) implies

ε · f (A) · f (B) + f (C) · f (ap_{⟨A,B⟩} (C)) ∈ K_{0},

and thus (53) follows from (FR5’). By what we have just shown we get a well-defined map ψ : P′ \ P → K^{∗} by

ψ (r) := f (r · w · w_{0} · W_{P}) · f (w · w_{0} · W_{P})^{−1} for w ∈ W′ with r ∉ R (w) .

Thus (52) follows for κ := f (w_{0} · W_{P}).

So far, we have considered examples of (W; P; U)-matroids with coefficients for fixed kregular triples (W; P; U). In forthcoming papers we shall also study (W; P; U)-matroids with coefficients in a fixed fuzzy ring K thereby using the theory of the Tutte group of a combinatorial (W; P; U)-geometry which will be developed in [27].

References

[1] Berman, A.; Kotzig, A.: Cross-Clonning and Antipodal Graphs. Discrete Mathematics 69 (1988), 107–114.

[2] Bland, R. G.; Las Vergnas, M.: Orientability of Matroids. Journal of Combinatorial Theory B 24 (1978), 94–123.

[3] Bouchet, A.: Greedy Algorithm and Symmetric Matroids. Mathematical Programming 38 (1987), 147–159.

[4] Bouchet, A.: Representability of Δ-Matroids. Colloquia Mathematica Societatis Jànos Bolyai 52, Combinatorics, Eger (Hungary), 1987, 167–182.

[5] Bouchet, A.; Duchamp, A.: Representability of Δ-Matroids over GF(2). Linear Algebra and its Applications 146 (1991), 67–78.

[6] Dress, A. W. M.: Duality Theory for Finite and Infinite Matroids with Coefficients. Advances in Mathematics 59 (1986), 97–123.

[7] Dress, A. W. M.: Chirotopes and Oriented Matroids. Bayreuther Mathematische Schriften 21, Tagungsbericht 2. Sommerschule Diskrete Strukturen, Bayreuth 1985, 14–68.

[8] Dress, A. W. M.; Wenzel, W.: Grassmann-Plücker Relations and Matroids with Coefficients. Advances in Mathematics 86 (1991), 68–110.

[9] Dress, A. W. M.; Wenzel, W.: Perfect Matroids. Advances in Mathematics 91 (1992), 158–208.

[10] Dress, A. W. M.; Wenzel, W.: Endliche Matroide mit Koeffizienten. Bayreuther Mathematische Schriften 26 (1988), 37–98.

[11] Dress, A. W. M.; Wenzel, W.: Geometric Algebra for Combinatorial Geometries. Advances in Mathematics 77 (1989), 1–36.

[12] Dress, A. W. M.; Wenzel, W.: A simple Proof of an Identity Concerning Pfaffians of Skew Symmetric Matrices. Advances in Mathematics 112 (1995), 120–134.

[13] Dress, A. W. M.; Wenzel, W.: Valuated Matroids. Advances in Mathematics 93 (1992), 214–250.

[14] Gelfand, I. M.; Serganova, V. V.: On the General Definition of a Matroid and a Greedoid. Soviet Math. Dokl. 35 (1987), No. 1, 6–10.

[15] Gelfand, I. M.; Serganova, V. V.: Combinatorial Geometries and Torus Strata on Homogeneous Compact Manifolds. Russian Mathematical Surveys 42,2 (1987), 133–168.

[16] Göbel, F.; Veldman, H. J.: Even Graphs. Journal of Graph Theory 10 (1986), 225–239.

[17] Gutierrez Novoa, L.: On n-ordered Sets and Order Completeness. Pacific Journal of Mathematics 15 (1965), 1337–1345.

[18] Lawrence, J.: Oriented Matroids and Multiply Ordered Sets. Linear Algebra and its Applications 48 (1982), 1–12.

[19] Maurer, S. B.: Matroid Basis Graphs I. Journal of Combinatorial Theory B 14 (1973), 216–240.

[20] Sabidussi, G.: The Structure of Antipodal Graphs. Resumés/Abstracts, Théorie des Graphes et Combinatoire, 4ème Colloque Internationale, Marseille, July 1990.

[21] Welsh, D. J. A.: Matroid Theory. Academic Press London, New York, San Francisco 1976.

[22] Wenzel, W.: Pfaffian Forms and Δ-Matroids. Discrete Mathematics 115 (1993), 253–266.

[23] Wenzel, W.: Pfaffian Forms and Δ-Matroids with Coefficients. Discrete Mathematics 148 (1996), 227–252.

[24] Wenzel, W.: Δ-Matroids with the Strong Exchange Condition. Applied Mathematics Letters 6, No. 5 (1993), 67–70.

[25] Wenzel, W.: Maurer’s Homotopy Theory for Even Δ-Matroids and Related Combinatorial Geometries. Journal of Combinatorial Theory A 71 (1995), 19–95.

[26] Wenzel, W.: Geometric Algebra of Δ-Matroids and Related Combinatorial Geometries. Habilitationsschrift, Bielefeld (1991).

[27] Wenzel, W.: A Unified Treatment of the Geometric Algebra of Matroids and of Even Δ-Matroids, in preparation.

Received: June 7, 1994, revised version September 29, 1995