\input amstex
\documentstyle{amsppt}
\magnification1200

%\input graph
\UseAMSsymbols
\loadeufm
\loadeusm
\def\script{\eusm}
%\input comdia.tex
%\input german
%\baselineskip=18pt
\font\BF=cmbx12
\font\klein=cmr8
\def\litem{\par\noindent
                \hangindent=\parindent\ltextindent}
\def\litemitem{\par\noindent
                \hangindent=2\parindent\ltextindent}
\def\ltextindent#1{\hbox to \hangindent{#1\hss}\ignorespaces}
\NoBlackBoxes
\parindent=0pt

\centerline{\bf $\Delta$-matroids and Pfaffian Forms}
\medskip
\centerline{Walter Wenzel, Bielefeld}
\medskip 
In analogy to the fact that representable matroids may be defined in terms
of Grassmann-Pl\"ucker maps we want to describe representability of
$\Delta$-matroids by skew-symmetric matrices in terms of Pfaffian forms. In
the sequel we assume $n\in \Bbb N,S:=\{ 1,\hdots,n\} $, and $K$ denotes
some commutative field.
\smallskip
{\bf Definition 1 (cf. [B1, \S 6] or [B2, \S 1]):} \newline
Assume $\Cal F\subseteq \Cal P(S)$. The pair $(S,\Cal F)$ is a {\bf
$\Delta$-matroid}, if $\Cal F$ satisfies
$$
\aligned & \text {For } F_1,F_2\in \Cal F \text { and } e\in F_1\Delta F_2 \text { there
exists some} \\
& f\in F_1\Delta F_2 \text { with } F_1\Delta \{ e,f\} \in \Cal
F. \endaligned \tag SEA
$$
For $\Cal F\subseteq \Cal P(S)$ and $T\subseteq S$ we put $\Cal F\Delta
T:=\{ F\Delta T\ |\ F\in \Cal F\} $.
\smallskip
{\bf Definition 2 (cf. [B2, \S 4]):} \newline
A $\Delta$-matroid $(S,\Cal F)$ is representable over $K$ by a
skew-symmetric matrix \linebreak
$A=(a_{ij})_{i,j\in S}$, if for some $T\subseteq S$ we have
$$
\Cal F\Delta T=\Cal F(A):=\{ S'\subseteq S\ |\ A':=(a_{ij})_{i,j\in S'}
\text { is nonsingular}\} ,
$$
where $(a_{ij})_{i,j\in \emptyset}$ is considered to be nonsingular. $A$ is
then called a {\bf presentation} of $(S,\Cal F)$.
\smallskip
{\bf Theorem 3:} A $\Delta$-matroid $(S,\Cal F)$ is representable over $K$
by a skew-symmetric matrix if and only if there exists some map $P:\Cal
P(S)\rightarrow K$ and some $T\in \Cal F$ such that

\parindent=1truecm
\item{(P0)} For $I\subseteq S$ we have $P(I)\ne 0$ if and only if $I\Delta
T\in \Cal F$.
\item{(P1)} If $I\subseteq S$ and $\# I\equiv 1$ mod $2$, then $P(I)=0$.
\item{(P2)} If $I_1,I_2\subseteq S$ and $I_1\Delta I_2=\{ i_1,\hdots,i_k\}
$ with $i_j<i_{j+1}$ for $1\le j\le k-1$, then
$$
\sum \limits ^k_{j=1}(-1)^j\cdot P(I_1\Delta \{ i_j\} )\cdot P(I_2\Delta \{
i_j\} )=0.
$$

\parindent=0pt
\smallskip
If $(S,\Cal F)$ is representable by $A=(a_{ij})_{i,j\in S}$, then $P$ may
be choosen to \linebreak
be the corresponding Pfaffian form, which may be defined by
$P(I):=0$ for \linebreak
$\# I\equiv 1$ mod $2$, $P(\emptyset ):=1$, $P(\{ i,j\}
):=a_{ij}$ for $1\le i<j\le n$, and
$$
\align P(\{ i_1,\hdots,i_{2m}\} ) & :=\sum \limits ^{2m}_{j=2}(-1)^j\cdot
P(\{ i_1,i_j\} )\cdot P(\{ i_2,\hdots,i_{2m}\} \setminus \{ i_j\} ) \\
& \text {for } 2\le m\le \frac {n} {2} \text { and } i_j<i_{j+1} \text {
for } 1\le j\le 2m-1. \endalign
$$
\vfill \eject

Vice versa, if $P$ satisfies (P0), (P1), (P2), then $(S,\Cal F)$ is
representable by the matrix $A=(a_{ij})_{i,j\in S}$ given by $a_{ii}:=0$
for $1\le i\le n$, $a_{ij}=-a_{ji}=P(\{ i,j\} )$ for $1\le i<j\le n$.
\smallskip
{\bf Corollary:} A $\Delta$-matroid $(S,\Cal F)$, representable by some
skew-symmetric matrix, satisfies the following strong exchange property:
$$
\align & \text {For } F_1,F_2\in \Cal F \text { and } e\in F_1\Delta F_2
\text { there exists some} \\
& f\in (F_1\Delta F_2)\setminus \{ e\} \text { with } F_1\Delta \{ e,f\}
\in \Cal F \text { and } F_2\Delta \{ e,f \} \in \Cal F. \endalign
$$
Furthermore, Theorem 3 suggests
\smallskip
{\bf Definition 4:} Assume $F\subseteq \Cal P(S)$.

\parindent=1truecm
\item{i)} $(S,\Cal F)$ is an {\bf orientable $\Delta$-matroid}, if there
exists some $T\in \Cal F$ and some map $P:\Cal P(S)\rightarrow \{ 0,1,-1\}
$ satisfying
\itemitem{(OP0)} For $I\subseteq S$ we have $P(I)\in \{ 1,-1\} $ if and
only if $I\Delta T\in \Cal F$.
\itemitem{(OP1)} For $I\subseteq S$ with $\# I\equiv 1$ mod $2$ we have
$P(I)=0$.
\itemitem{(OP2)} If $I_1,I_2\subseteq S$, $I_1\Delta I_2=\{ i_1,\hdots,
i_k\} $ with $i_j<i_{j+1}$ for $1\le j\le k-1$, and if for some $w\in \{
1,-1\} $ we have $\kappa _j:=w\cdot (-1)^j\cdot P(I_1\Delta \{ i_j\} )\cdot
P(I_2\Delta \{ i_j\} )\ge 0$ for $1\le j\le k$, then $\kappa _j=0$ for
every $j$.
\item{ii)} Assume $P:\Cal P(S)\rightarrow \Bbb R^+\overset{.}\to \cup \{
0\} $ is some map. $(S,\Cal F,P)$ is a {\bf valuated $\Delta$-matroid}, if
for some $T\in \Cal F$ we have
\itemitem{(VP0)} For $I\subseteq S$ we have $P(I)>0$ if and only if
$I\Delta T\in \Cal F$.
\itemitem{(VP1)} For $I\subseteq S$ with $\# I\equiv 1$ mod $2$ we have
$P(I)=0$.
\itemitem{(VP2)} If $I_1,I_2\subseteq S$ with $\# I_1\equiv \# I_2\equiv 0$
mod $2$, then for every $i\in I_1\Delta I_2$ there exists some $j\in
(I_1\Delta I_2)\setminus \{ i\} $ with
$$
P(I_1)\cdot P(I_2)\le P(I_1\Delta \{ i,j\} )\cdot P(I_2\Delta \{ i,j\} ).
$$

\parindent=0pt
{\klein
\centerline{\bf References}
\smallskip

\parindent=1truecm
\item{[B1]} A. Bouchet: Greedy algorithm and symmetric matroids,
Mathematical Programming 38 (1987), 147-159.
\item{[B2]} A. Bouchet: Representability of $\Delta$-matroids, Colloquia
Mathematica Societatis J\'anos Bolyai 52. Combinatorics, Eger (Hungary),
1987, 167-182.
\item{[DW]} A.W.M. Dress and W. Wenzel: Grassmann-Pl\"ucker relations and
matroids with coefficients, to appear in Advances in Mathematics.
\item{[K]} G. Kowalewski: Determinantentheorie, Chelsea Publishing Company,
New York, 1948.
\item{[S]} J.R. Stembridge: Nonintersecting Paths, Pfaffians, and Plane
Partitions, Advances in Mathematics 83 (1990), 96-131.
\item{[W]} W. Wenzel: Pfaffian Forms and $\Delta$-Matroids, in preparation.}
\vfill \eject

\parindent=0pt

\bye
