%(2/1/18) this version final version after round 2 of refereeing \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.9}{25(1)}{2018} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \title{\bf The structure of delta-matroids with width one twists} \author{Carolyn Chun\\ \small United States Naval Academy, Annapolis, Maryland 21402, U.S.A.\\ \small \tt chun@usna.edu\\ \and Rhiannon Hall\\ \small Department of Mathematics, Brunel University, London\\[-0.8ex] \small Uxbridge, Middlesex, UB8 3PH, United Kingdom\\ \small \tt rhiannon.hall@brunel.ac.uk\\ \and Criel Merino\thanks{Investigaci\'on realizada gracias al Programa UNAM-DGAPA-PAPIIT IN102315}\\ \small Instituto de Matem\'aticas, Universidad nacional Aut\'onoma de M\'exico\\[-0.8ex] \small Ciudad de M\'exico, 04510, M\'exico\\ \small \tt merino@matem.unam.mx\\ \and Iain Moffatt\\ \small Department of Mathematics, Royal Holloway, University of London\\[-0.8ex] \small Egham, Surrey, TW20 0EX, United Kingdom\\ \small \tt iain.moffatt@rhul.ac.uk\\ \and Steven D. Noble\\ \small Department of Economics, Mathematics and Statistics, Birkbeck, University of London\\[-0.8ex] \small Malet Street, London, WC1E 7HX, United Kingdom\\ \small \tt s.noble@bbk.ac.uk} \date{\dateline{May 25, 2017}{Dec 28, 2017}{Jan 12, 2018}\\ \small Mathematics Subject Classifications: 05B35} \begin{document} \maketitle \begin{abstract} The width of a delta-matroid is the difference in size between a maximal and minimal feasible set. We give a Rough Structure Theorem for delta-matroids that admit a twist of width one. We apply this theorem to give an excluded-minor characterisation of delta-matroids that admit a twist of width at most one. \bigskip\noindent \textbf{Keywords:} delta-matroid; excluded minor; matroid; partial dual; twist; width \end{abstract} \section{Introduction, results and notation}\label{s1} Delta-matroids are a generalisation of matroids and were introduced by A. Bouchet in \cite{ab1}. Delta-matroid theory can be thought of as generalising topological graph theory in the same way that matroid theory can be thought of as generalising graph theory (see, e.g., \cite{CMNR1}). In delta-matroid theory, feasible sets fulfill the same role as bases do in matroid theory, but feasible sets are in general not all of the same size. Notions of deletion, contraction and minors exist for delta-matroids, so there is the possibility of characterising minor-closed families of delta-matroids by their excluded minors. One of the most fundamental operations in delta-matroid theory is the twist, and a basic integer invariant of a delta-matroid is its width. We show that delta-matroids with twists of width at most $k$ form a minor-closed family, of which we give an excluded-minor characterization in the case $k=1$. We also examine how the structure of a delta-matroid determines the width of the delta-matroids that are in its equivalence class under twists. Formally, a \emph{delta-matroid} $D=(E,\mathcal{F})$ consists of a finite set $E$ and a non-empty set $\mathcal{F}$ of subsets of $E$ that satisfies the \emph{Symmetric Exchange Axiom}: for all $X,Y\in \mathcal{F}$, if there is an element $u\in X\triangle Y$, then there is an element $v\in X\triangle Y$ such that $X\triangle \{u,v\}\in \mathcal{F}$. Here $X\triangle Y$ denotes the symmetric difference of sets $X$ and $Y$. Note that it may be the case that $u=v$ in the Symmetric Exchange Axiom. Elements of $\mathcal{F}$ are called \emph{feasible sets} and $E$ is the \emph{ground set}. We often use $\mathcal{F}(D)$ and $E(D)$ to denote the set of feasible sets and the ground set, respectively, of $D$. A \emph{matroid} is a delta-matroid whose feasible sets are all of the same size. In this case the feasible sets are called \emph{bases}. This definition of a matroid is a straightforward reformulation of the standard one in terms of bases. In general a delta-matroid has feasible sets of different sizes. The \emph{width} of a delta-matroid, defined by Bouchet in~\cite{ab2} and denoted by $w(D)$, is the difference between the sizes of its largest and smallest feasible sets: $ w(D):= \max\limits_{F\in \mathcal{F}} |F| - \min\limits_{F\in \mathcal{F}} |F|$. Twists, introduced by Bouchet in~\cite{ab1}, are one of the fundamental operations of delta-matroid theory. Given a delta-matroid $D=(E,{\mathcal{F}})$ and some subset $A\subseteq E$, the \emph{twist} of $D$ with respect to $A$, denoted by $D* A$, is the delta-matroid given by $(E,\{A\bigtriangleup F : F\in \mathcal{F}\})$. (At times we write $D\ast e$ for $D\ast \{e\}$.) Note that the ``empty twist'' is $D*\emptyset = D $. The \emph{dual} of $D$, written $D^*$, is equal to $D*E$. Moreover, in general, the twist can be thought of as a ``partial dual'' operation on delta-matroids. Forming the twist of a delta-matroid usually changes the sizes of its feasible sets and its width. Here we are interested in the problem of recognising when a delta-matroid has a twist of small width. Our results are a Rough Structure Theorem for delta-matroids that have a twist of width one, and an excluded-minor characterisation of delta-matroids that have a twist of width at most one. While in this paper we are interested in the smallest width among all twists of a delta-matroid, the largest width among all twists has been investigated in, e.g., \cite{GI}. To state the Rough Structure Theorem we need the following definitions. Let $D=(E,\mathcal{F})$ be a delta-matroid and let $\mathcal{F}_{\min}$ be the set of feasible sets of minimum size. Observe that $D_{\min}:=(E,\mathcal{F}_{\min})$ is a matroid. To see this suppose that $F_1$ and $F_2$ are feasible sets of minimum size, and $e$ is an element of $F_1-F_2$. Then $e\in F_1\triangle F_2$ and there exists $f\in F_1\triangle F_2$ such that $F_1 \triangle \{e,f\} \in \mathcal{F}$. Because $F_1$ and $F_2$ are feasible sets of minimum size, $f\in F_2-F_1$. Thus the feasible sets of minimum size obey the axioms defining the bases of a matroid. For a matroid $M$ with ground set $E$, a subset $A$ of $E$ is said to be a \emph{separator} of $M$ if $A$ is a union of components of $M$. Note that both $\emptyset$ and $E$ are always separators. In terms of the matroid rank function, where the rank $r(X)$ of a set $X\subseteq E$ is defined to be the size of the largest intersection of $X$ with a basis of $M$, the set $A$ is a separator if and only if $r(A) + r(E-A) = r(M)$. Throughout the paper we use $\overline{A}$ for the complement $E- A$ of $A$, and $D|X$ denotes the restriction of $D$ to $X\subseteq E$ (see the beginning of Section~\ref{s2} for its definition). We now state the first of our two main results: a Rough Structure Theorem for delta-matroids admitting a twist of width one. \begin{theorem}\label{tm1} Let $D=(E,\mathcal{F})$ be a delta-matroid. Then $D$ has a twist of width one if and only if there is some $A\subseteq E$ such that \begin{enumerate} \item $A$ is a separator of $D_{\min}$, \item $D|A$ is a matroid, and \item $D|\overline{A}$ is of width one. \end{enumerate} \end{theorem} We actually prove a result that is stronger than Theorem~\ref{tm1}. This stronger result appears below as Theorem~\ref{tt} and the present theorem follows immediately from it. As an application of Theorem~\ref{tm1}, we find an excluded-minor characterisation of the class of delta-matroids that have a twist of width one as our second main result, Theorem~\ref{t1}. This class of delta-matroids is shown to be minor closed in Proposition~\ref{p1}, and its set of excluded minors comprises the delta-matroids in the following definition together with their twists. \begin{definition}\label{d1} Let $D_1$ denote the delta-matroid on the elements $a,b$ with feasible sets \[\mathcal{F}(D_1)=\{ \emptyset, \{a\}, \{b\}, \{a,b\} \}.\] Let $D_2$ and $D_3$ denote the delta-matroids on the elements $a,b,c$ with feasible sets given by \begin{align*} \mathcal{F}(D_2)&=\{ \emptyset, \{a\}, \{b\}, \{c\},\{a,b,c\} \}, \\ \mathcal{F}(D_3)&=\{ \emptyset, \{a,b\}, \{b,c\}, \{a,c\} \}. %\mathcal{F}(D_4)&=\{ \emptyset, \{a,b\}, \{b,c\}, \{a,c\},\{a,b,c\} \}, \\ %\mathcal{F}(D_5)&=\{ \emptyset, \{a\}, \{a,b\}, \{b,c\}, \{a,c\} \}. \end{align*} Throughout this paper $D_1$, $D_2$ and $D_3$ refer exclusively to these delta-matroids. Let $\mathcal{D}_{[3]}$ be the set of all twists of these delta-matroids. Note that $D_i\in \mathcal{D}_{[3]}$ for all $i\in\{1,2,3\}$ via the empty twist. \end{definition} \begin{theorem}\label{t1} A delta-matroid has a twist of width at most one if and only if it has no minor isomorphic to a member of $\mathcal{D}_{[3]}$. \end{theorem} The proof of this theorem appears at the end of Section~\ref{s3}. A delta-matroid is \emph{even} if the difference in size between any two feasible sets is even. We note that the excluded minors of twists of matroids (i.e., twists of width zero delta-matroids) have been shown, to be $( \{a\}, \{ \emptyset, \{a\} \} ) $, $D_3$, and $D_3\ast \{a\}$ by A. Duchamp~\cite[Corollary~4.3]{adfund}. This result can be recovered from Theorem~\ref{t1} by noting that a delta-matroid has a twist of width zero if and only if it is both even and has a twist of width at most one, and that a delta-matroid is even if and only if it has no minor isomorphic to $( \{a\}, \{ \emptyset, \{a\} \} ) $. The latter result is easily recovered from Lemma~5.4 of~\cite{ab2}. \section{The proof of the Rough Structure Theorem}\label{s2} We recall some standard matroid and delta-matroid terminology. Given a delta-matroid $D=(E,\mathcal{F})$ and element $e\in E$, if $e$ is in every feasible set of $D$ then we say that $e$ is a \emph{coloop} of $D$. If $e$ is in no feasible set of $D$, then we say that $e$ is a \emph{loop} of $D$. If $e\in E$ is not a coloop, then $D$ \emph{delete} $e$, denoted by $D\setminus e$, is the delta-matroid $(E-e, \{F : F\in \mathcal{F}\text{ and } F\subseteq E-e\})$. If $e\in E$ is not a loop, then $D$ \emph{contract} $e$, denoted by $D/e$, is the delta-matroid $(E-e, \{F-e : F\in \mathcal{F}\text{ and } e\in F\})$. If $e\in E$ is a loop or coloop, then we define $D/e=D\setminus e$. Useful identities that we use frequently are $ D/e = (D\ast e) \setminus e $ and $ D\setminus e = (D\ast e) / e $. Note that deleting or contracting an element from a delta-matroid corresponds to taking a subset of its feasible sets and removing an element from either none of them or all of them, and consequently cannot increase the width. If $D'$ is a delta-matroid obtained from $D$ by a sequence of deletions and contractions, then $D'$ is independent of the order of the deletions and contractions used in its construction, so we can define $D\setminus X/Y$ for disjoint subsets $X$ and $Y$ of $E$, as the result of deleting each element in $X$ and contracting each element in $Y$ in some order. A \emph{minor} of $D$ is any delta-matroid that is obtained from $D$ by a (possibly empty) sequence of deletions and contractions. The \emph{restriction} of $D$ to a subset $A$ of $E$, written $D|A$, is equal to $D\setminus \overline{A}$. A delta-matroid is \emph{normal} exactly when the empty set is among its feasible sets. Note that if $D$ is a normal delta-matroid then $F$ is feasible in $D|A$ if and only if $F\subseteq A$ and $F\in \mathcal{F}(D)$. \medskip The \emph{connectivity function} $\lambda_M$ of a matroid $M$ on ground set $E$ with rank function $r$ is defined on all subsets $A$ of $E$ by $\lambda_M(A) = r(A) + r(\overline{A}) - r(E)$. %from Oxley p272 % Recall that $A$ is said to be a \emph{separator} of $M$ if $A$ is a (possibly empty) union of components of $M$. This happens if and only if $\lambda_M(A)=0$. Moreover, $A$ is a separator if and only if $\overline{A}$ is a separator. %from Oxley p128 We will use Bouchet's analogue of the rank function for delta-matroids from~\cite{abrep}. For a delta-matroid $D=(E,\mathcal{F})$, it is denoted by $\rho_D$ or simply $\rho$ when $D$ is clear from the context. Its value on a subset $A$ of $E$ is given by \[\rho(A):=|E|-\min\{|A\bigtriangleup F| : F\in \mathcal{F}\}.\] The following results give expressions for the width of a twist of a delta-matroid. \begin{lemma} Let $D=(E,\mathcal{F})$ be a delta-matroid and $A\subseteq E$. Then the width, $w(D*A)$, of the twist of $D$ by $A$ is given by $w(D*A)=\rho (\overline{A} )-|E|+\rho (A)$. \end{lemma} \begin{proof} A largest feasible set in $D*A$ has size $\max \{|F\bigtriangleup A|:F\in \mathcal{F} (D)\}$. Take $F'\in\mathcal{F}$ such that $|F'\bigtriangleup A|$ is maximal. Then $|F'\bigtriangleup \overline{A} |$ is minimal. As $\rho (\overline{A})=|E|-\min\{|F\bigtriangleup \overline{A} |:F\in\mathcal{F}\}$, we see that $\rho (\overline{A} )=|E|-|F'\bigtriangleup \overline{A} |=|F'\bigtriangleup A|$. Hence a largest feasible set in $D*A$ has size equal to $\rho (\overline{A} )$. Next, the size of a smallest feasible set in $D*A$ is $|E|$ minus the size of a largest feasible set in $(D*A)^*=D*\overline{A} $. By an application of the above, it follows that the size of a smallest feasible set in $D*A$ is $|E|-\rho (A)$. Hence $w(D*A)=\rho (\overline{A} )-|E|+\rho (A)$. \end{proof} \begin{theorem}\label{t2} Let $D=(E,\mathcal{F})$ be a delta-matroid and $A\subseteq E$. Then the width, $w(D*A)$, of the twist of $D$ by $A$ is given by \[w(D*A)=w(D|A)+w(D|\overline{A}) +2\,\lambda_{D_{\min}}(A).\] \end{theorem} \begin{proof} We let $r$ and $n$ be the rank and nullity functions, respectively, of $D_{\min}$. From \cite{CMNR1}, we know that $w(D|A)=\rho (A)-r(A)-n(E)+n(A)$. As $n(A)=|A|-r(A)$ and $n(E)=|E|-r(E)$, \begin{align*} w(D|A)&+w(D|\overline{A} ) \\ &=\rho (A)-r(A)-|E|+r(E)+|A|-r(A)\\ & \phantom{=} {} + \rho (\overline{A} )-r(\overline{A} )-|E|+r(E)+|\overline{A} |-r(\overline{A} )\\ &= \rho (\overline{A} )-|E|+\rho (A) -2(r(A)+r(\overline{A} )-r(E)) \\& =w(D*A)-2 (\lambda _{D_{\min}}(A)), \end{align*} where we have applied the previous lemma to obtain the last equality. \end{proof} The following two theorems are immediate consequences of Theorem~\ref{t2}. The Rough Structure Theorem, Theorem~\ref{tm1}, follows immediately from the second of them. \begin{theorem}[Chun et al \cite{CMNR2}]\label{tt2} Let $D=(E,\mathcal{F})$ be a delta-matroid and $A\subseteq E$. Then $D*A$ is a matroid if and only if $A$ is a separator of $D_{\min}$, and both $D|A$ and $D|\overline{A}$ are matroids. \end{theorem} \begin{theorem}\label{tt} Let $D=(E,\mathcal{F})$ be a delta-matroid and $A\subseteq E$. Then $D*A$ has width one if and only if $A$ is a separator of $D_{\min}$, and one of $D|A$ and $D|\overline{A}$ is a matroid and the other has width one. \end{theorem} For convenience, we write down the following straightforward corollary. It provides the form of the Rough Structure Theorem that we use to find excluded minors in the next section. \begin{corollary}\label{c2} Let $D=(E,\mathcal{F})$ be a normal delta-matroid. Then the following hold. \begin{enumerate} \item $D$ has a twist of width zero if and only if there exists $A\subseteq E$ such that $D|A$ and $D|\overline{A}$ are both matroids. \item $D$ has a twist of width one if and only if there exists $A\subseteq E$ such that $D|A$ is a matroid and $D|\overline{A}$ is of width one. \end{enumerate} \end{corollary} \begin{proof} This is a straightforward consequence of the fact that if $\emptyset$ is feasible in $D$, then $D_{\min}$ is the matroid on $E(D)$ where each element is a loop, thus every set $A\subseteq E$ is a separator of $D_{\min}$. \end{proof} \section{The proof of the excluded-minor characterisation}\label{s3} We begin this section by verifying that the class of delta-matroids in question is indeed minor-closed. \begin{proposition}\label{p1} For each $k\in \mathbb{N}_0$, the set of delta-matroids with a twist of width at most $k$ is minor-closed. \end{proposition} \begin{proof} Let $D=(E,\mathcal{F})$ and suppose $w(D\ast A) \leq k$ for some $A\subseteq E$. If $E$ is empty then $D$ has width zero and has no minors other than itself, so assume not and let $e\in E$. If $e\notin A$ then $(D\setminus e)\ast A = (D\ast A)\setminus e$, and $(D/e)*A=((D*e)\setminus e)*A= ((D*e)*A)\setminus e = ((D*A)\ast e) \setminus e = (D*A) / e $. Similarly, if $e\in A$ then $e\notin A-e$, so using and extending the previous argument, $(D/e)\ast (A-e)= (D*(A-e))/e = ((D*A)* e)/e = (D*A)\setminus e$, and $(D\setminus e) \ast (A-e) = (D\ast (A-e)) \setminus e = ((D\ast A)\ast e) \setminus e = (D\ast A)/e $. In each case we see that $D/e$ and $D\setminus e$ have a twist equal to either $(D\ast A)/e$ or $(D\ast A) \setminus e$. Since deletion and contraction never increase width it follows that $D/e$ and $D\setminus e$ have twists of width at most $w(D\ast A) \leq k$. The result follows. \end{proof} \begin{lemma}\label{l1} Let $D=(E,\mathcal{F})$ be a delta-matroid and $A\subseteq E$. Then \[\{ H : H \text{ is a minor of } D\ast A \} = \{ J\ast (A\cap E(J)) : J \text{ is a minor of } D \}. \] \end{lemma} \begin{proof} In the proof of Proposition~\ref{p1} it was shown that if $e\notin A$ then $(D*A) / e = (D/e)*A$ and $ (D\ast A)\setminus e = (D\setminus e)\ast A $, whereas if $e\in A$ then $(D*A)\setminus e = (D/e)\ast (A-e)$ and $(D\ast A)/e = (D\setminus e) \ast (A-e)$. The result follows immediately from this. \end{proof} Before stating the next lemma we define the delta-matroids $D_4$ and $D_5$ on elements $a,b,c$ with feasible sets given by \begin{align*} \mathcal{F}(D_4)&=\{ \emptyset, \{a,b\}, \{b,c\}, \{a,c\},\{a,b,c\} \}, \\ \mathcal{F}(D_5)&=\{ \emptyset, \{a\}, \{a,b\}, \{b,c\}, \{a,c\} \}. \end{align*} Both are twists of $D_2$. \begin{lemma}\label{l2} Let $D$ be a normal delta-matroid. Then $D$ has a twist of width at most 1, or contains a minor isomorphic to one of $D_1, \ldots,D_5$. \end{lemma} \begin{proof} For any normal delta-matroid $D$, set \[ L:= \{x\in E(D) : \{x\} \in \mathcal{F}(D)\} \quad \text{and} \quad \overline{L}=E(D)-L.\] (Technically we should record the fact that $L$ depends upon $D$ in the notation, however we avoid doing this for notational simplicity. This should cause no confusion.) Note that $L$ may be empty. Construct a (simple) graph $G_D$ as follows. Take one vertex $v_x$ for each element $x\in \overline{L}$, and add one other vertex $v_L$. The edges of $G_D$ arise from certain two-element feasible sets of $D$. Add an edge $v_xv_y$ to $G_D$ for each pair $x,y\in \overline{L}$ with $\{x,y\}\in \mathcal{F}(D)$; add an edge $v_xv_L$ to $G_D$ if $\{x,z\}\in \mathcal{F}(D)$ for some $z\in L$. We consider two cases: when $G_D$ is bipartite, and when it is not. We will show that if $G_D$ is bipartite then $D$ must have a twist of width at most one or a minor isomorphic to $D_1$ or $D_2$; if $G_D$ is not bipartite then it must have a minor isomorphic to $D_1$, $D_3$, $D_4$, or $D_5$. \medskip \noindent\textbf{\textit{Case 1.}} Suppose that $G_D$ is bipartite. Fix a 2-colouring of $G_D$. Let $A$ be the set of elements in $E(D)$ that correspond to the vertices in the colour class containing $v_L$, except $v_L$ itself, together with the elements in $L$, and let $\overline{A}\subseteq E(D)$ be the set of elements corresponding to the vertices in the colour class not containing $v_L$. We start by showing \begin{equation}\label{e1} D|\overline{A} \cong U_{0, |\overline{A}|}, \end{equation} where $U_{0, |\overline{A}|}$ denotes the uniform matroid with rank zero and $|\overline{A}|$ elements. To see why \eqref{e1} holds, note that $\mathcal{F}(D|\overline{A})=\{F : F\subseteq \overline{A}\text{ and } F\in \mathcal{F}(D)\}$. Since the elements in $\overline{A}$ correspond to vertices in $\overline{L}$, no feasible sets of $D|\overline{A}$ have size one. Furthermore, $\mathcal{F}(D|\overline{A})$ cannot contain any sets of size two since, by the construction of $G_D$, whenever $\{x,y\}\in \mathcal{F}(D)$ the corresponding vertices $v_x$ and $v_y$ are in different colour classes. Since $\emptyset \in \mathcal{F}(D|\overline{A})$, the Symmetric Exchange Axiom ensures that there are no other feasible sets. (If $F\in \mathcal{F}(D|\overline{A})$ with $F\neq \emptyset$, take $x\in \emptyset \bigtriangleup F$. Then by the Symmetric Exchange Axiom $\emptyset \bigtriangleup \{x, y\}$ must be in $\mathcal{F}(D|\overline{A})$ for some $y$, but there are no feasible sets of size one or two.) This completes the justification of \eqref{e1}. Next we examine the feasible sets in $D|A$. Trivially $\emptyset\in \mathcal{F}(D|A)$. The set of feasible sets of $D|A$ of size one is $\{ F\in \mathcal{F}(D|A) : |F|= 1\} =\{ F\in \mathcal{F}(D) : |F|= 1\} = \{ \{x\} : x\in L \}$. If $\mathcal{F}(D|A)$ contains a set $\{x,y\}$ of size two then $x,y\in L$ as otherwise there would be an edge $v_xv_y$ in $G_D$ whose ends are in the same colour class. It follows in this case that $D|\{x,y\}$ is a minor of $D$ isomorphic to $D_1$. Now assume that $\mathcal{F}(D|A)$ does not contain a set of size two. If $\mathcal{F}(D|A)$ has no sets of size one then, arguing via the Symmetric Exchange Axiom as in the justification of \eqref{e1}, we have $D|A \cong U_{0,|A|}$. Taken together with~\eqref{e1}, this implies that $A$ satisfies the conditions of the first part of Corollary~\ref{c2}, so $D$ has a twist of width zero. Suppose that $\mathcal{F}(D|A)$ does contain a set of size one. If it contains no sets of size greater than one then $D|A$ is of width one, and by combining this with~\eqref{e1}, it follows from Corollary~\ref{c2} that $D$ has a twist of width one ($D\ast A$ and $D\ast \overline{A}$ are such twists). On the other hand, if $\mathcal{F}(D|A)$ does contain a set of size greater than one, then, as it does not contain a set of size two, the Symmetric Exchange Axiom guarantees there is a set in $\mathcal{F}(D|A)$ of size exactly three. (If not, let $F$ be a minimum sized feasible set with $|F|>1$. Then $|F|>3$, and $F \setminus \{x,y\}$ is feasible and of size at least two for some $x,y\in \emptyset \bigtriangleup F$ contradicting the minimality of $|F|$.) Let $\{x,y,z\}\in \mathcal{F}(D|A)$. Then after possibly relabelling its elements, the collection of feasible sets of $D|\{x,y,z\}$ is one of \[ \{ \emptyset, \{x\}, \{y\}, \{z\}, \{x,y,z\} \}, \quad \{ \emptyset, \{x\}, \{y\}, \{x,y,z\} \}, \quad \{ \emptyset, \{x\}, \{x,y,z\} \}.\] Only the first of the three cases is possible as the Symmetric Exchange Axiom fails for the other two showing that neither is the collection of feasible sets of a delta-matroid. In fact, the second and third set systems are isomorphic to $T_2^*$ and $T_1^*$, respectively, which Bonin, Chun, and Noble~\cite{BCN} showed to be among the excluded minors for the class of delta-matroids. Hence, restricting $D$ to $\{x,y,z\}$ results in a minor isomorphic to $D_2$. Thus we have shown that if $G_D$ is bipartite then $D$ has a twist of width at most one or contains a minor isomorphic to $D_1$ or $D_2$. This completes the proof of Case 1. \medskip \noindent\textbf{\textit{Case 2.}} Suppose that $G_D$ is non-bipartite. We will show that $D$ contains a minor isomorphic to one of $D_1$, $D_3$, $D_4$ or $D_5$ by induction on the length of a shortest odd cycle in $G_D$. For the base of the induction suppose that $G_D$ has an odd cycle $C$ of length three. There are two sub-cases, when $v_L$ is not in $C$ and when it is. Note that the former sub-case includes the situation where $L=\emptyset$. \smallskip \noindent\textbf{\textit{Sub-case 2.1.}} Suppose that $v_L$ is not in $C$. Let $x,y,z\in E(D)$ be the elements corresponding to the three vertices of $C$. We have $x,y,z\in \overline{L}$, so $\{x\}, \{y\}, \{z\}\notin \mathcal{F}(D)$. From the three edges of $C$ we have $\{x,y\}, \{y,z\}, \{z,x\}\in \mathcal{F}(D)$. It follows that $D|\{x,y,z\}$ is isomorphic to either $D_3$ or $D_4$ giving the required minor. \smallskip \noindent\textbf{\textit{Sub-case 2.2.}} Suppose that $v_L$ is in $C$. Let $v_x, v_y, v_L$ be the vertices in $C$. The edges of $C$ give that $ \{x,y\} \in \mathcal{F}(D)$, and since $x,y\in \overline{L}$ we have $\{x\}, \{y\} \notin \mathcal{F}(D)$. We also know that there are elements $\alpha, \beta\in L$ such that $\{\alpha\}, \{\beta\}, \{x,\alpha\},\{y,\beta\} \in \mathcal{F}(D)$, where possibly $\alpha=\beta$. If $\alpha=\beta$ then $D|\{x,y,\alpha\}$ must have feasible sets \begin{equation}\label{e13} \{\emptyset, \{\alpha\}, \{x,\alpha\},\{y,\alpha\},\{x,y\}\} \quad\text{or}\quad \{\emptyset, \{\alpha\}, \{x,\alpha\},\{y,\alpha\},\{x,y\}, \{\alpha, x,y\}\}. \end{equation} The first case gives a minor of $D$ isomorphic to $D_5$; in the second case, $(D|\{x,y,\alpha\}) / \alpha$ is a minor of $D$ isomorphic to $D_1$. If $\alpha\neq \beta$ then the feasible sets of $D|\{x,y,\alpha,\beta\}$ of size zero or one are exactly $\emptyset$, $\{\alpha\}$, and $\{\beta\}$. From $G_D$, the feasible sets of size two include $\{x,\alpha\},\{y,\beta\}, \{x,y\}$. If $\{ y,\alpha\}$ is also feasible then $D|\{x,y,\alpha\}$ is isomorphic to one of the delta-matroids arising from \eqref{e13}, so $D$ has a minor isomorphic to $D_1$ or $D_5$. The case when $\{ x,\beta\}$ is feasible is similar. If $\{\alpha,\beta\}$ is feasible then $D|\{\alpha,\beta\}$ is isomorphic to $D_1$. The case that remains is when the feasible sets of $D|\{x,y,\alpha,\beta\}$ of size at most two are exactly \[ \emptyset, \{\alpha\}, \{\beta\}, \{x,\alpha\},\{y,\beta\}, \{x,y\}. \] By applying the Symmetric Exchange Axiom to each of the triples \[ (\{\alpha\},\{x,y\},y),\ (\{\beta\},\{x,y\},x),\ (\{\beta\},\{x,\alpha\},x)\ \text{and}\ (\{\alpha\},\{y,\beta\},y),\] where the three components of the triple play the roles of $F_1$, $F_2$ and $u$ in the Symmetric Exchange Axiom, one can show that each of the three element sets, \[ \{\alpha,x,y\}, \{\beta,x,y\}, \{\alpha,\beta,x\}, \{\alpha,\beta,y\}, \] is feasible in $D|\{x,y,\alpha,\beta\}$. Finally, $\{\alpha,\beta, x,y\}$ may or may not be feasible. If $\{\alpha,\beta, x,y\}$ is feasible then $(D|\{x,y,\alpha,\beta\})/\{x,y\}$ is isomorphic to $D_1$; if $\{\alpha,\beta, x,y\}$ is not feasible then $(D|\{x,y,\alpha,\beta\})/\{\alpha\}$ is isomorphic to $D_5$. This completes the base of the induction. For the inductive hypothesis, we assume that, for some odd $n>3$, if $D'$ is a normal delta-matroid and $G_{D'}$ has an odd cycle of length less than $n$, then $D'$ has a minor isomorphic to $D_1,D_3,D_4$, or $D_5$. Suppose that a shortest odd cycle $C$ of $G_D$ has length $n$. Again there are two sub-cases: when $v_L$ is not in $C$ and when it is. \smallskip \noindent\textbf{\textit{Sub-case 2.3.}} Suppose that $v_L$ is not in $C$. Let $C=v_{x_1}v_{x_2} \ldots v_{x_n}v_{x_1}$. Since each $x_i\in \overline{L}$ and $C$ is the shortest odd cycle in $G_D$, \begin{equation}\label{e5} \emptyset, \{ x_1,x_2 \}, \{ x_2,x_3 \}, \ldots,\{ x_n,x_1 \} \end{equation} is a complete list of the feasible sets of size at most two in $D|\{x_1,\ldots, x_n\}$. Next, we show \begin{equation}\label{e3} \{x_i,x_j,x_k\} \notin \mathcal{F}(D|\{x_1,\ldots, x_n\}), \quad \text{ for any distinct } 1\leq i,j,k\leq n. \end{equation} To see why \eqref{e3} holds, first note that, since $n>3$, every set of three distinct vertices in the cycle includes a non-adjacent pair. If $\{x_i,x_j,x_k\}$ were feasible in $D|\{x_1,\ldots, x_n\}$, then, without loss of generality, $\{x_j,x_k\}\notin\mathcal{F}(D|\{x_1,\ldots, x_n\})$. As $x_i\in\{x_i,x_j,x_k\}\bigtriangleup\emptyset$, an application of the Symmetric Exchange Axiom would imply that $\{x_i,x_j,x_k\}\bigtriangleup\{x_i,z\}$ is feasible for some $z\in\{x_i,x_j,x_k\}$. Thus $\{x_j,x_k\},\{x_j\}$, or $\{x_k\}$ would be feasible, a contradiction to~\eqref{e5}. Thus~\eqref{e3} holds. Next we show that, taking indices modulo $n$, \begin{equation}\label{e4} \{x_i,x_{i+1},x_j,x_{j+1}\} \in \mathcal{F}(D|\{x_1,\ldots, x_n\}), \end{equation} for any $i$ and $j$ such that $1 \leq i,j \leq n$ and $i,i+1,j,j+1$ are pairwise distinct. By \eqref{e5}, $\{ x_i,x_{i+1}\}$ and $\{ x_j,x_{j+1}\}$ are feasible. As $x_{j}$ is in their symmetric difference, by the Symmetric Exchange Axiom, $\{x_i,x_{i+1}\}\bigtriangleup\{x_j,y\}$ is feasible for some $y\in\{x_i,x_{i+1},x_j,x_{j+1}\}$. Thus $\{x_i,x_{i+1},x_j\}, \{x_i,x_j\}, \{x_{i+1},x_j\}$ or $\{x_i,x_{i+1},x_j,x_{j+1}\}$ is feasible. First suppose that neither $x_{i+1}$ and $x_j$ nor $x_{j+1}$ and $x_i$ are adjacent in $C$. By~\eqref{e5} and \eqref{e3}, $\{x_i,x_{i+1},x_j,x_{j+1}\}$ is feasible. Alternatively, if $x_{i+1}$ and $x_j$ are adjacent then the Symmetric Exchange Axiom implies that $\{x_i,x_{i+1}\}\bigtriangleup\{x_{i+3},z\}$ is feasible for some $z\in\{x_i,x_{i+1},x_{i+2},x_{i+3}\}$. Again,~\eqref{e5} and~\eqref{e3} imply that $\{x_i,x_{i+1},x_{i+2},x_{i+3}\}$ must be feasible. The other case is identical. This completes the justification of \eqref{e4}. Combining \eqref{e5}--\eqref{e4} gives that all of $ \emptyset, \{ x_1,x_2 \}, \{ x_2,x_3 \}, \ldots,\{ x_{n-2},x_1 \} $, but none of $\{x_1\}, \ldots, \{x_{n-2}\}$, are feasible in $(D|\{x_1,\ldots, x_n\})/\{ x_{n-1},x_n\}$. Consequently the graph $G_{(D|\{x_1,\ldots, x_n\})/\{ x_{n-1},x_n\}}$ has a shorter odd cycle than $G_D$. By the inductive hypothesis, $(D|\{x_1,\ldots, x_n\})/\{ x_{n-1},x_n\}$ and hence $D$ has a minor isomorphic to one of $D_1$, $D_3$, $D_4$ or $D_5$. \smallskip \noindent\textbf{\textit{Sub-case 2.4.}} Suppose that $v_L$ is in $C$. Let $C=v_Lv_{x_2}v_{x_3}\dots v_{x_n}v_L$. The edges of the cycle give that, for each $2\leq i\leq n-1$, $ \{x_i,x_{i+1}\} \in \mathcal{F}(D)$. Also, for $2\leq i\leq n$, since $x_i\in \overline{L}$ we have $\{x_i\} \notin \mathcal{F}(D)$. We also know that there are elements $\alpha, \beta\in L$ such that $\{\alpha\}, \{\beta\}, \{\alpha, x_2\},\{\beta,x_n\} \in \mathcal{F}(D)$ where possibly $\alpha=\beta$. In the case where $\alpha\neq\beta$, if $\{\alpha,\beta\}\in\mathcal{F}(D)$, then $D|\{\alpha,\beta\}$ is isomorphic to $D_1$, therefore we assume $\{\alpha,\beta\}\notin\mathcal{F}(D)$. The following analysis covers both the case where $\alpha=\beta$ and the case where $\alpha\neq\beta$. Using that $C$ is a shortest odd cycle, the feasible sets of $D|\{\alpha, \beta, x_2,\ldots, x_n\}$ of size at most two are exactly \begin{equation}\label{e6} \emptyset, \{\alpha\}, \{\beta\}, \{\alpha,x_2\}, \{ x_2,x_3 \}, \{ x_3,x_4 \}, \ldots, \{ x_{n-1},x_n \}, \{ \beta, x_n\}. \end{equation} An argument similar to the justification of \eqref{e3} gives that \begin{equation}\label{e7} \{x_i,x_j,x_k\} \notin \mathcal{F}(D|\{\alpha,\beta, x_2,\ldots, x_n\}), \quad \text{ for any distinct } 2\leq i,j,k\leq n. \end{equation} However \begin{equation}\label{e8} \{\alpha, x_{n-1}, x_n\}, \{\beta, x_{n-1}, x_n\} \in \mathcal{F}(D|\{\alpha,\beta,x_2,\ldots, x_n\}). \end{equation} To see this note that $x_{n-1} \in \{\alpha \} \bigtriangleup \{ x_{n-1},x_n \}$, so the Symmetric Exchange Axiom gives that one of $\{\alpha, x_{n-1} \}$, $\{x_{n-1}\}$, or $\{\alpha, x_{n-1}, x_n \}$ is feasible, and we know from \eqref{e6} that the feasible set must be the third option. That $\{\beta, x_{n-1}, x_n\}$ is feasible follows from a similar argument. We next show that for each $2\leq i < n-2$, \begin{equation}\label{e9} \{\alpha, x_2, x_{n-1}, x_n\}, \{x_i, x_{i+1}, x_{n-1}, x_n\}, \{\beta, x_{n-2}, x_{n-1}, x_n\} \in \mathcal{F}(D|\{\alpha,\beta,x_2,\ldots, x_n\}). \end{equation} For this, first consider $x_2 \in \{ x_{n-1}, x_n\}\bigtriangleup \{\alpha, x_2\}$. The Symmetric Exchange Axiom implies that $\{x_{n-1},x_n\}\bigtriangleup\{x_2,z\}$ is feasible for some $z\in\{\alpha,x_2,x_{n-1},x_n\}$. By~\eqref{e6} and \eqref{e7}, $z=\alpha$, thus $\{\alpha,x_2,x_{n-1},x_n\}$ is feasible. Next, to show that $\{x_i,x_{i+1},x_{n-1},x_n\}$ is feasible, we take $x_i\in\{x_{n-1},x_n\} \bigtriangleup\{x_i,x_{i+1}\}$ and apply the Symmetric Exchange Axiom as above to see that $\{x_{n-1},x_n\}\bigtriangleup\{x_i,z\}$ is feasible, where $z$ must equal $x_{i+1}$. Lastly, to show that $\{\beta,x_{n-2},x_{n-1},x_n\}$ is feasible, we first show that $\{\beta,x_{n-2},x_n\}\notin \mathcal{F}(D|\{\alpha,\beta,x_2,\ldots, x_n\})$. If $\{\beta,x_{n-2},x_n\}$ were feasible, then since $x_{n-2}\in \emptyset\bigtriangleup\{\beta,x_{n-2},x_n\}$, the Symmetric Exchange Axiom would give $\{x_{n-2}\}$, $\{\beta,x_{n-2}\}$ or $\{x_{n-2},x_n\}$ as feasible, a contradiction. Now showing that $\{\beta,x_{n-2},x_{n-1},x_n\}$ is feasible comes from taking $x_{n-2}\in\{\beta,x_n\}\bigtriangleup\{x_{n-2},x_{n-1}\}$. The Symmetric Exchange Axiom gives that $\{\beta,x_n\}\bigtriangleup\{x_{n-2},z\}$ is feasible for some $z\in\{\beta,x_{n-2},x_{n-1},x_n\}$, of which $z=x_{n-1}$ is the only possibility. From \eqref{e6}--\eqref{e9} it follows that all of $\emptyset$, $\{\alpha\}$, $\{\beta\}$, $\{\alpha,x_2\}$, $\{ x_2,x_3 \}$, $\ldots$, $\{ \beta, x_{n-2} \}$, but none of $\{x_2\}$, $\ldots$, $\{x_{n-2}\}$, are feasible in $D'=(D|\{\alpha, x_2,\ldots, x_n,\beta\})/\{ x_{n-1},x_n\}$. Hence the graph $G_{D'}$ has a shorter odd cycle than $G_D$. The inductive hypothesis gives that $D'$ and hence $D$ has a minor isomorphic to one of $D_1$, $D_3$, $D_4$ or $D_5$. This completes the proof of the sub-case, and the lemma. \end{proof} We now apply Lemma~\ref{l2} to prove our excluded-minor characterisation of the family of delta-matroids admitting a twist of width at most one. \begin{proof}[Proof of Theorem~\ref{t1}] All twists of the delta-matroids $D_1$, $D_2$, $D_3$ are of width at least two. Since the set of delta-matroids with a twist of width at most one is minor-closed it follows that no minor of a delta-matroid with a twist of width at most one is isomorphic to a member of $\mathcal{D}_{[3]}$. This proves one direction of the theorem. Conversely suppose that every twist of a delta-matroid $D=(E,\mathcal{F})$ is of width at least two. Let $A\in \mathcal{F}$. Then $D*A$ is a normal delta-matroid and in which every twist is of width at least two. By Lemma~\ref{l2}, $D*A$ has a minor isomorphic to one of $D_1, \ldots,D_5$. Using the fact that $D_4$ and $D_5$ are both twists of $D_2$, it follows from Lemma~\ref{l1} that $D$ has a minor isomorphic to a member of $\mathcal{D}_{[3]}$. \end{proof} \begin{remark} In the introduction, we mentioned the very close connection between delta-matroids and graphs in surfaces. Viewed as ribbon graphs, such graphs give rise to the minor-closed class of \emph{ribbon graphic delta-matroids} in much the same way as (abstract) graphs give rise to the class of graphic matroids. For a full explanation see~\cite{CMNR1}. The width of a delta-matroid can be viewed as the analogue of the genus (or more precisely the Euler genus) of an embedded graph, while twisting is the analogue of S.~Chmutov's partial duality of~\cite{Ch09}. Thus characterising delta-matroids with a twist of width one is the analogue of characterising embedded graphs having a partial dual embedded in the real projective plane. The topological graph theoretical analogues of Theorems~\ref{tm1}, \ref{t1} and~\ref{t2} can be found in \cite{mo13,mo16}. In fact the ribbon graph results provide versions of Theorems~\ref{tm1}, \ref{t1}, and~\ref{t2} that hold for the class of ribbon graphic delta-matroids. For a ribbon graphic version of Theorem~\ref{t1}, if $D$ is ribbon graphic and does not admit a twist of width at most one, then $D=D(G)$ for some ribbon graph $G$ that does not have a partial dual of Euler genus at most one. By Theorem~1.1 of~\cite{mo16}, it follows that one of the ribbon graphs $X_1$, $X_2$, or $X_3$ from Figure~1 of that paper must be a minor. By the compatibility of ribbon graph and delta-matroid deletion and contraction described in~\cite{CMNR1}, one of $D(X_1)=D_1$, $D(X_2)=D_3$, or $D(X_3)=D_3\ast a$ is a minor of $D$. The converse follows since the class is minor-closed. It is not difficult to see that neither $D_2$ nor any of its twists is ribbon-graphic, so they do not appear as excluded minors for this class, but several definitions from~\cite{CMNR1} are required to make the argument concise. Briefly, any ribbon-graphic delta-matroid with the same feasible sets of size at most two as $D_2$ must arise from a ribbon graph comprising a single vertex and three pairwise interlaced non-orientable loops. In any such ribbon-graphic delta-matroid there is no feasible set of size three. Thus $D_2$ is not ribbon graphic. As any twist of a ribbon-graphic delta-matroid is ribbon-graphic~\cite{ab2,CMNR1}, it follows that no twist of $D_2$ is ribbon-graphic. (An alternative way to see that $D_2$ is not ribbon graphic is to note that ribbon graphic delta-matroids are representable over $GF(2)$ and that $D_2$ is one of the excluded minors for that class \cite{ab3}.) Similar reasoning shows that Theorem~3.4 of~\cite{mo13} gives Theorem~\ref{t2} for ribbon graphic delta-matroids in the special case where $\lambda_{D_{\min}}(A)=0$; and Theorem~4.3(2) of~\cite{mo13} results in Theorem~\ref{tm1} for ribbon graphic delta-matroids. Deducing these results uses the fact that $A$ defines a biseparation of $G$ if and only if it is a separator of $D(G)$~\cite{CMNR1}. \end{remark} \begin{thebibliography}{10} \bibitem{BCN} J.~Bonin, C.~Chun, and S.~Noble. \newblock Delta-matroids as subsystems of sequences of {H}iggs lifts. \newblock {\em preprint}, 2017. \bibitem{ab1} A.~Bouchet. \newblock Greedy algorithm and symmetric matroids. \newblock {\em Math. Program.}, 38(2):147--159, 1987. \bibitem{abrep} A.~Bouchet. \newblock Representability of $\triangle$-matroids. \newblock {\em Combinatorics (Eger, 1987) Colloq. Math. Soc. J\'anos Bolyai}, 52:167--182, 1988. \bibitem{ab2} A.~Bouchet. \newblock Maps and {$\triangle$}-matroids. \newblock {\em Discrete Math.}, 78(1-2):59--71, 1989. \bibitem{ab3} A.~Bouchet. \newblock Representability of $\triangle$-matroids over ${\rm GF}(2)$. \newblock {\em Linear Algebra Appl.}, 146:67--78, 1991. \bibitem{Ch09} S.~Chmutov. \newblock Generalized duality for graphs on surfaces and the signed {B}ollob{\'a}s-{R}iordan polynomial. \newblock {\em J. Combin. Theory Ser. B}, 99(3):617--638, 2009. \bibitem{CMNR1} C.~Chun, I.~Moffatt, S.~D. Noble, and R.~Rueckriemen. \newblock Matroids, delta-matroids and embedded graphs. \newblock {\em preprint}, 2014. \bibitem{CMNR2} C.~Chun, I.~Moffatt, S.~D. Noble, and R.~Rueckriemen. \newblock On the interplay between embedded graphs and delta-matroids. \newblock {\em preprint}, 2014. \bibitem{adfund} A.~Duchamp. \newblock Circuit separation for symmetric matroids. \newblock {\em Linear Algebra Appl.}, 231:87--103, 1995. \bibitem{GI} J.~Geelen, and S.~Iwata. \newblock Matroid matching via mixed skew-symmetric matrices \newblock {\em Combinatorica}, 25(2):187--215, 2005. \bibitem{mo13} I.~Moffatt. \newblock Separability and the genus of a partial dual. \newblock {\em European J. Combin.}, 34(2):355--378, 2013. \bibitem{mo16} I.~Moffatt. \newblock Ribbon graph minors and low-genus partial duals. \newblock {\em Ann. Comb.}, 2(20):373--378, 2016. \end{thebibliography} \end{document}