NONINTERSECTING PATHS, PFAFFIANS, AND DELTA-MATROIDS

In this paper, we study Delta-matroids induced by nonintersecting path s in a directed graph. The association between nonintersecting paths a nd Delta-matroids is derived from Pfaffians. On the one hand, certain numbers of k-tuples of nonintersecting paths may (often) be expressed as a Pfaffian, while, on the other hand, representability problems for Delta-matroids may be studied in terms of Pfaffians. It is shown that Delta-matroids induced by nonintersecting paths are representable ove r fields of any characteristic and that weightings defined on the edge set and with values in some linearly ordered abelian group give rise to valuated Delta-matroids. (C) 1997 Academic Press.