Δ-matroids and Pfaffian Forms

Walter Wenzel, Bielefeld

In analogy to the fact that representable matroids may be defined in terms of Grassmann-Plücker maps we want to describe representability of Δ-matroids by skew-symmetric matrices in terms of Pfaffian forms. In the sequel we assume n ∈ ℕ, S := {1, …, n}, and K denotes some commutative field. Definition 1 (cf. [B1, §6] or [B2, §1]): Assume F ⊆ P(S). The pair (S, F) is a Δ-matroid, if F satisfies

(SEA)

For F_{1}, F_{2} ∈ F and e ∈ F_{1}ΔF_{2} there exists some
f ∈ F_{1}ΔF_{2} with F_{1}Δ{e, f} ∈ F.

For F ⊆ P(S) and T ⊆ S we put FΔT := {F ΔT | F ∈ F}. Definition 2 (cf. [B2, §4]): A Δ-matroid (S, F) is representable over K by a skew-symmetric matrix A = (a_{ij})_{i,j∈S}, if for some T ⊆ S we have

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

where (a_{ij})_{i,j∈∅} is considered to be nonsingular. A is then called a presentation of (S, F). Theorem 3: A Δ-matroid (S, F) is representable over K by a skew-symmetric matrix if and only if there exists some map P : P(S) → K and some T ∈ F such that (P0) For I ⊆ S we have P (I) ≠ 0 if and only if IΔT ∈ F. (P1) If I ⊆ S and #I ≡ 1 mod 2, then P (I) = 0. (P2) If I_{1}, I_{2} ⊆ S and I_{1}ΔI_{2} = {i_{1}, …, i_{k}} with i_{j} < i_{j+1} for 1 ≤ j ≤ k − 1, then

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

If (S, F) is representable by A = (a_{ij})_{i,j∈S}, then P may be choosen to be the corresponding Pfaffian form, which may be defined by P (I) := 0 for #I ≡ 1 mod 2, P (∅) := 1, P ({i, j}) := a_{ij} for 1 ≤ i < j ≤ n, and

P ({i_{1}, …, i_{2m}}) := ∑_{j=2}^{2m}(−1)^{j} · P ({i_{1}, i_{j}}) · P ({i_{2}, …, i_{2m}} \ {i_{j}})

for 2 ≤ m ≤ \frac{n}{2} and i_{j} < i_{j+1} for 1 ≤ j ≤ 2m − 1.

Vice versa, if P satisfies (P0), (P1), (P2), then (S, F) is representable by the matrix A = (a_{ij})_{i,j∈S} given by a_{ii} := 0 for 1 ≤ i ≤ n, a_{ij} = −a_{ji} = P ({i, j}) for 1 ≤ i < j ≤ n. Corollary: A Δ-matroid (S, F), representable by some skew-symmetric matrix, satisfies the following strong exchange property:

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.

Furthermore, Theorem 3 suggests Definition 4: Assume F ⊆ P(S).

i) (S, F) is an orientable Δ-matroid, if there exists some T ∈ F and some map P : P(S) → {0, 1, −1} satisfying

(OP0) For I ⊆ S we have P (I) ∈ {1, −1} if and only if IΔT ∈ F.

(OP1) For I ⊆ S with #I ≡ 1 mod 2 we have P (I) = 0.

(OP2) If I_{1}, I_{2} ⊆ S, I_{1}ΔI_{2} = {i_{1}, …, i_{k}} with i_{j} < i_{j+1} for 1 ≤ j ≤ k−1, and if for some w ∈ {1, −1} we have κ_{j} := w·(−1)^{j} ·P (I_{1}Δ{i_{j}})·P (I_{2}Δ{i_{j}}) ≥ 0 for 1 ≤ j ≤ k, then κ_{j} = 0 for every j.

ii) Assume P : P(S) → ℝ^{+} ∪^{.} {0} is some map. (S, F, P) is a valuated Δ-

matroid, if for some T ∈ F we have (VP0) For I ⊆ S we have P (I) > 0 if and only if IΔT ∈ F. (VP1) For I ⊆ S with #I ≡ 1 mod 2 we have P (I) = 0. (VP2) If I_{1}, I_{2} ⊆ S with #I_{1} ≡ #I_{2} ≡ 0 mod 2, then for every i ∈ I_{1}ΔI_{2} there

exists some j ∈ (I_{1}ΔI_{2}) \ {i} with

P (I_{1}) · P (I_{2}) ≤ P (I_{1}Δ{i, j}) · P (I_{2}Δ{i, j}).

References

[B1] A. Bouchet: Greedy algorithm and symmetric matroids, Mathematical Programming 38 (1987), 147-159.

[B2] A. Bouchet: Representability of Δ-matroids, Colloquia Mathematica Societatis János Bolyai 52. Combinatorics, Eger (Hungary), 1987, 167-182.

[DW] A.W.M. Dress and W. Wenzel: Grassmann-Plücker relations and matroids with coefficients,

to appear in Advances in Mathematics.

[K] G. Kowalewski: Determinantentheorie, Chelsea Publishing Company, New York, 1948.

[S] J.R. Stembridge: Nonintersecting Paths, Pfaffians, and Plane Partitions, Advances in Mathematics 83 (1990), 96-131.

[W] W. Wenzel: Pfaffian Forms and Δ-Matroids, in preparation.