text:
\begin{document}
\abovedisplayshortskip=-3pt plus3pt
\belowdisplayshortskip=6pt

\maketitle

\begin{abstract}\noindent
  We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, and gives rise to new width parameters with associated duality theorems. The highly connected substructures witnessing large width are presented in a unified way akin to tangles, as orientations of low-order separations satisfying certain consistency axioms.
   \COMMENT{}
   \end{abstract}

\section{Introduction}\label{sec:intro}

There are a number of theorems in the structure theory of sparse graphs that assert a duality between high connectivity present somewhere in the graph and an overall tree structure. For example, a graph has small tree-width if and only if it contains no large-order bramble.
   \COMMENT{}
   The aim of this paper is to prove one such theorem in a general setting, a~theorem that will imply all the classical duality theorems as special cases, but with a unified and simpler proof. Our theory will give rise to new width parameters as well, with dual notions of highly connected substructures, and conversely provide dual tree-like structures for notions of high connectivity that have been considered before but for which no duality theorems were known.

Amini, Mazoit, Nisse, and Thomass\'e~\cite{MazoitPartition} have also established a theory of dualities of width parameters, which pursues (and achieves) a similar aim. Our theory differs from theirs in two respects: we allow more general separations of a given ground set than just partitions, including ordinary separations of graphs; and our `highly connected substructures' are modelled after tangles, while theirs are modelled on brambles. Hence while our main results can both be used to deduce those classical duality theorems for width parameters, they differ in substance. And so do their corollaries for the various width parameters, even if they imply the same classical results. Moreover, while the main results of~\cite{MazoitPartition} can easily be deduced from ours (see Section~\ref{subsec:partitionsub}), the converse seems less clear. And finally, our theory gives rise to duality theorems for new width parameters that can only be expressed in our set-up.

All we need in our set-up is that we have a notion of `separation' for the combinatorial structure to be considered, which will only have to satisfy some very basic assumptions. The best example of a separation $s$ is a set $\{A,B\}$ of subsets of a `ground set' $V$ that cover it, i.e., which satisfy $A\cup B = V$. Such a separation will have two orientations, $\vs$~and~$\sv$. In the example these will be the ordered pairs $(A,B)$ and~$(B,A)$, with no fixed rule saying which is which. Then $V$~might be the vertex set of a graph or the ground set of a matroid, and our separations might be defined as usual for graphs and matroids.

Our unified treatment of highly connected substructures is gleaned from the notion of tangles in graph minor theory~\cite{GMX}, or of ultrafilters in set theory. The idea is as follows. Consider any set ${S}$ of separations of a given graph or matroid. In order to deserve its name with respect to~${S}$, we expect of a `highly connected substructure'~$\C$ that no separation in $S$ divides it: that for each $s\in S$ it lies on one side of~$s$ but not the other. The structure~$\C$, whatever it may be, thus orients $s$ as either $\vs$ or~$\sv$, choosing the orientation that `points to it'. Our paradigm is that this overall orientation of $S$ is the only information about $\C$ we ever use: we need not know what $\C$ {\it is\/}, but only where it lies. In this spirit, we shall {\em define\/} all our `highly connected substructures' in precisely this way: as orientations of (the elements of) a given set $S$ of separations of some structure. For now, however, let us stay with the more intuitive notion that $\C$ is some (mysterious but `real') highly connected substructure that merely `induces' an orientation of~$S$.

For example, ${S}$ might be the set of all separations
\footnote{A separation $\{A,B\}$ of a graph is one of its vertex set with no edge from $A\sm B$ to $B\sm A$.}
  $\{A,B\}$ of a graph~$G$ such that $\abs{A\cap B} < k$ for some fixed~$k$. Then every $K_n$-minor $\C$ of~$G$ with $n\ge k$ will have a branch set in $A\sm B$ or in $B\sm A$, but not both. It therefore orients $\{A,B\}$: as $(A,B)$ if $B\sm A$ contains a branch set, and as~$(B,A)$ if $A\sm B$ does.
   \footnote{Thinking of $(A,B)$ as pointing towards~$B$ is, of course, is just a convention, but one we shall keep throughout the paper.}

Of course, such `real' highly connected substructures $\C$ do not induce arbitrary orientations of~${S}$: these will satisfy some consistency rules. For example, if $\vs$ points towards~$\C$ and $\vr$ points towards~$s$ (which will be made precise), then $\vr$ will also point towards~$\C$ while $\rv$ will not. While this particular rule will be common to all our notions of a highly connected substructure, there may be further rules specific to each, so that we can tell them apart even just from the orientations of~$S$ they induce. The additional rules will all stipulate that such an orientation of~${S}$ must not contain certain subsets of~$\vS$, the set of orientations of separations in~${S}$: such as the set $\{\rv,\vs\}$ in the above example, where $\vr$ points towards~$s$.

Thus, each $\C$ will determine, and in our paradigm be determined by, a collection $\F$ of `forbidden' subsets of~$\vS$, which the orientation of $S$ that $\C$ induces cannot contain. It will help to think of the elements of~$\F$ as sets of oriented separations which, collectively, point to a part of our structure deemed too small to accommodate~$\C$.
Tangles, for example, are defined in this way: with $\F$ the set of all triples $(A_1,B_1), (A_2,B_2), (A_3,B_3)$ of separations whose `rear' sides~$A_1,A_2,A_3$ cover the entire graph or matroid.
   \footnote{In the classical definition of a tangle, these triples are not required to point to some common place: their separations are even allowed to point away from each other. But this makes it even harder for our imagined $\C$ to comply with all three pointers, and we shall see that there is no loss of generality in requiring that they do point to some common place.}

The tree-like structure that is dual to a highly connected substructure~$\C$, i.e., which will exist in our given structure if and only if it contains no instance of~$\C$, will be defined by this same collection $\F$ of separation sets forbidden by~$\C$. It will typically come as a subset of~${S}$ that is nested, and which thus cuts up the underlying set in a tree-like way. And the `stars' of oriented separations at which this tree branches,  oriented towards that branch point, will be {\it required\/} to lie in~$\F$: between them, they identify a place in our structure that is too small to accommodate an instance of~$\C$. The tree structure dual to tangles, for example, branches at each node in three ways corresponding to the sides $A_1,A_2,A_3$ of a triple $(A_1,B_1), (A_2,B_2), (A_3,B_3)\in\F$.

The following familiar dualities between high local connectivity and tree structure can be captured in this way, and their known duality theorems will follow from our theorem. For graphs, we can capture \pd s and blockages~\cite{QuicklyExcludingForest}, \td s and brambles~\cite{ST1993GraphSearching}, \bd s and tangles of graphs~\cite{GMX}. For matroids, our framework captures \bd s and tangles~\cite{GMX,BranchDecMatroids}, as well as matroid \td s~\cite{HlinenyWhittle} and their dual objects proposed by Amini, Mazoit, Nisse, and Thomass\'e~\cite{MazoitPartition}. Our framework also captures \bd s and tangles of symmetric submodular functions~\cite{GMX,BranchDecMatroids}, which includes branch-width of graphs and matroids, carving-width of graphs~\cite{ratcatcher}, and rank-width of graphs~\cite{rankwidth}.
   \COMMENT{}

   Since brambles are not defined in terms of orientations of sets of separations, the duality theorem we obtain when we specify ${S}$ and~$\F$ to capture tree-width (of graphs or matroids) will differ from the known duality theorem for tree-width: our dual objects will be more like tangles, not collections of `touching' vertex or edge sets. So in this sense our duality theorem for tree-width is new, although it easily implies the classical theorem. Since ${S}$ and $\F$ can be chosen in many other ways too, our results also imply dualities for new width parameters.

Our unifying duality theorem will come in three flavours: as {\it weak\/}, {\it strong\/}, and {\it general\/} duality. Our {\it weak duality theorem\/}, presented in Section~\ref{sec:weak}, will be easy to prove but has no direct applications. It will be used as a stepping stone for both the {\it strong duality theorem\/} and the {\it general duality theorem\/}, our two main results. The strong duality theorem, presented in Section~\ref{sec:strong}, will imply all the classical results mentioned earlier. The general duality theorem, presented in Part~II of this paper~\cite{DiestelOumDualityII}, will be applicable to a much wider set of notions of highly connected substructure, including profiles~\cite{profiles, CDHH13CanonicalAlg, CDHH13CanonicalParts} and $k$-blocks~\cite{confing, ForcingBlocks}. But the tree-like structure witnessing their exclusion will be less specific than in the strong theorem, so these two theorems are independent.

\section{Terminology and basic facts}\label{sec:def}

A \emph{separation of a set} $V$ is a set $\{A,B\}$ such that $A\cup B=V$. The ordered pairs $(A,B)$ and $(B,A)$ are its {\it orientations\/}. The {\em oriented separations\/} of~$V$ are the orientations of its separations. Mapping every oriented separation $(A,B)$ to its {\it inverse\/} $(B,A)$ is an involution
   \COMMENT{}
   that reverses the partial ordering \[(A,B)\le (C,D) :\Leftrightarrow A\subseteq C \text{ and } B\supseteq D.\]
Note that this is equivalent to $(D,C)\le (B,A)$. Informally, we think of $(A,B)$ as \emph{pointing towards}~$B$ and \emph{away from}~$A$. Similarly, if $(A,B)\le (C,D)$, then $(A,B)$ \emph{points towards} $\{C,D\}$, while $(C,D)$ \emph{points away from} $\{A,B\}$.

Generalizing these properties of separations of sets, we now give an axio\-matic definition of `abstract' separations.
   \footnote{Our proofs will read a lot more smoothly in this abstract set-up, because it will use the familiar and intuitive arrow notation for orientations. When drawing examples, however, we shall usually work with separations of sets.}
   A {\em separation system\/} $(\vS,\le\,,\!{}^*)$ is a partially ordered set $\vS$ with an order-reversing involution~*. Its elements are called {\em oriented separations\/}. When a given element of $\vS$ is denoted as~$\vs$, its {\em inverse\/}~$\vs^*$ will be denoted as~$\sv$, and vice versa. The assumption that * be {\em order-reversing\/} means that, for all $\vr,\vs\in\vS$,

\begin{equation}\label{invcomp}
\vr\le\vs\ \Leftrightarrow\ \rv\ge\sv.
\end{equation}

A {\em separation\/} is a set of the form $\{\vs,\sv\}$, and then denoted by~$s$. We call $\vs$ and~$\sv$ the {\em orientations\/} of~$s$. The set of all such sets $\{\vs,\sv\}\sub\vS$ will be denoted by~$S$. If $\vs=\sv$, we call both $\vs$ and $s$ {\em degenerate\/}.

When a separation is introduced ahead of its elements and denoted by a single letter~$s$, its elements will then be denoted as $\vs$ and~$\sv$.
   \footnote{It is meaningless here to ask which is which: neither $\vs$ nor $\sv$ is a well-defined object just given~$s$. But given one of them, both the other and $s$ will be well defined. They may be degenerate, in which case $s = \{\vs\} = \{\sv\}$.}
   Given a set $S'$ of separations, we write $\vSdash := \bigcup S'\sub\vS$
   \COMMENT{}
   for the set of all the orientations of its elements. With the ordering and involution induced from~$\vS$, this is again a separation system.
   \footnote{For $S'=S$, our definition of $\vSdash$ is consistent with the existing meaning of~$\vS$.
   \COMMENT{}
   When we refer to oriented separations using explicit notation that indicates orientation, such as $\vs$ or $(A,B)$, we sometimes leave out the word `oriented' to improve the flow of words. Thus, when we speak of a `separation $(A,B)$', this will in fact be an oriented separation.}

Separations of sets, and their orientations, are clearly an instance of this if we identify $\{A,B\}$ with $\{(A,B),(B,A)\}$.

If there are binary operations $\vee$ and~$\wedge$ on our separation system~$\vS$ such that $\vr\vee\vs$ is the supremum and $\vr\wedge\vs$ the infimum of $\vr$ and~$\vs$ in~$\vS$, we call $(\vS,\le\,,\!{}^*,\vee,\wedge)$ a {\em universe\/} of (oriented) separations. By~\eqref{invcomp}, it satisfies De~Mor\-gan's law:

\begin{equation}\label{deMorgan}
   (\vr\vee\vs)^* =\> \rv\wedge\sv.
\end{equation}
   \COMMENT{}

The oriented separations of a set~$V$ form such a universe: if $\vr = (A,B)$ and $\vs = (C,D)$, say, then $\vr\vee\vs := (A\cup C, B\cap D)$ and $\vr\wedge\vs := (A\cap C, B\cup D)$ are again oriented separations of~$V$, and are the supremum and infimum of $\vr$ and~$\vs$. Similarly, the oriented separations of a graph form a universe. Its oriented separations of order~$<k$ for some fixed~$k$, however, form a separation system inside this universe that may not itself be a universe with respect to $\vee$~and~$\wedge$ as defined above.
   \COMMENT{}

A separation $\vr\in\vS$ is {\em trivial in~$\vS$\/}, and $\rv$ is {\em co-trivial\/}, if there exists $s \in S$ such that $\vr < \vs$ as well as $\vr < \sv$.
   \COMMENT{}
   Note that if $\vr$ is trivial in~$\vS$ then so is every $\vrdash \le \vr$. If $\vr$ is trivial, witnessed by~$\vs$, then $\vr < \vs < \rv$ by~\eqref{invcomp}. Hence if $\vr$ is trivial, then $\rv$ cannot be trivial. If $\vS$ is non-empty and finite,
   \COMMENT{}
   its separations cannot all be trivial or co-trivial: if $\vr$ is maximal among trivial ones, then both orientations of every $s\in S$ witnessing the triviality of~$\vr$ are nontrivial.
   \COMMENT{}

There can also be nontrivial separations $\vs$ such that $\vs < \sv$.
   \COMMENT{}
   But anything smaller than these is again trivial: if $\vr < \vs\le\sv$, then $s$ witnesses the triviality of~$\vr$. Separations~$\vs$ such that $\vs\le\sv$, trivial or not, will be called {\em small\/}; note that, by~\eqref{invcomp}, if $\vs$ is small then so is every~$\vsdash\le\vs$.

The trivial oriented separations of a set~$V$, for example, are those of the form $\vr = (A,B)$ with $A\sub C\cap D$ and $B\supe C\cup D = V$ for some $s = \{C,D\}\ne r$. The small separations $(A,B)$ of $V$ are all those with $B=V$.

Two separations $r,s$ are {\em nested\/} if they have comparable orientations; otherwise they \emph{cross}. Two oriented separations $\vr,\vs$ are {\em nested\/} if $r$ and~$s$ are nested.
   \footnote{Terms introduced for unoriented separations may be used informally for oriented separations too if the meaning is obvious, and vice versa.}
   \COMMENT{}
   We say that $\vr$ {\em points towards\/}~$s$, and $\rv$ {\em points away from\/}~$s$, if $\vr\le\vs$ or $\vr\le\sv$. Then two nested oriented separations are either comparable, or point towards each other, or point away from each other. A~set of separations is {\em nested\/} if every two of its elements are nested.

A set $O\sub \vS$ of oriented separations is {\em antisymmetric\/} if it does not contain the inverse of any of its elements.
   \COMMENT{}
   It is \emph{consistent} if there are no distinct $r,s\in S$ with orientations $\vr < \vs$ such that $\rv,\vs\in O$.
   \COMMENT{}
   (Informally: if it does not contain orientations of distinct separations that point away from each other.)

A non-empty set $\sigma$ of oriented separations is a \emph{star of separations} if they point towards each other: if $\vr\le\sv$ for all distinct $\vr,\vs\in\sigma$ (Fig.~\ref{fig:star}). Stars of separations are clearly nested. They are also consistent: if $\rv,\vs$ lie in the same star we cannot have $\vr < \vs$, since also $\vs\le \vr$ by the star property.
A~star~$\sigma$ need not be antisymmetric;
   \COMMENT{}
   but if $\{\vs,\sv\}\sub\sigma$, then any other $\vr\in\sigma$ will be trivial.
   \COMMENT{}
   \looseness=-1

   \begin{figure}[htpb]
   \centering
   	  \includegraphics{star.pdf}
   	  \caption{The separations $(A,B),(C,D),(E,F)$ form a 3-star}
   \label{fig:star}\vskip-6pt
   \end{figure}

An \emph{orientation} of a set~${S}$ of separations is a set $O\sub{\vS}$ that contains for every $s\in{S}$ exactly one of its orientations $\vs,\sv$. A \emph{partial orientation} of~${S}$ is an orientation of a subset of~${S}$: an antisymmetric subset of~$\vS$ plus, possibly, some degenerate elements of~$\vS$.

Every consistent orientation of $S$ contains all separations $\vr$ that are trivial in~$\vS$, because it cannot contain their inverse~$\rv$: if the triviality of $\vr$ is witnessed by $s\in S$, say, then $\rv$ would be inconsistent with both $\vs$ and~$\sv$. It is not hard to show that every consistent partial orientation of $S$ containing no co-trivial $\rv\in\vS$ extends to a consistent orientation of all of~$S$~\cite{TreeSets}.

\medbreak\penalty-200

Let $S$ be a set of separations.  An \emph{${S}$-tree\/} is a pair $(T,\alpha)$ of a tree $T$ with at least one edge and a function $\alpha\colon\vec E(T)\to \vS$ from the set
 $$\vec E(T) := \{\, (x,y) : \{x,y\}\in E(T)\,\}$$
 of the \emph{orientations of} its {\em edges} to~$\vS$ such that

\begin{itemize}
\item[(i)]
 for every edge $xy$ of~$T$, if $\alpha(x,y)=\vs$ then $\alpha(y,x)=\sv$.
\end{itemize}

\noindent It is an $S$-tree is {\em over $\F\sub 2^{\vec S}$} if, in addition,

\begin{itemize}
\item[(ii)]
 for every node $t$ of~$T$ we have $\alpha(\vec F_t)\in\F$, where
 $$\vec F_t := \{(x,t) : xt\in E(T)\}.$$
\end{itemize}

\noindent
 We shall call the set $\vec F_t\sub\vec E(T)$ the {\em oriented star at~$t$} in~$T$. Its image $\alpha(\vec F_t)\in\F$ is said to be {\em associated with\/} $t$ in $(T,\alpha)$.

The $S$-tree $(T,\alpha)$ is {\em redundant\/} if it has a node $t$ of~$T$ with distinct neighbours $t',t''$ such that $\alpha(t',t) = \alpha(t'',t)$; otherwise it is {\em irredundant\/}. Redundant $S$-trees can clearly be {\em pruned\/} to irredundant ones over the same~$\F$:

\begin{LEM}\label{prune}
If $(T,\alpha)$ is a redundant $S$-tree over~$\F$ and $x$ is any node of~$T$, then $T$ has a subtree~$T'$ containing~$x$ such that $(T',\alpha')$ is an irredundant $S$-tree over~$\F$, where $\alpha'$ is the restriction of $\alpha$ to $\vec E(T')$.\qed
\end{LEM}
   \COMMENT{}

An important example of ${S}$-trees are irredundant ${S}$-trees \emph{over stars}: those over some $\F$ all of whose elements are stars of separations. In such an ${S}$-tree $(T,\alpha)$ the map~$\alpha$ preserves the \emph{natural partial ordering} on $\vec E(T)$ defined by letting $(x,y) < (u,v)$ if there is a unique $\{x,y\}$--$\{u,v\}$ path in $T$ starting at~$y$ and ending at~$u$ (see Figure~\ref{Streeseps}):
   \COMMENT{}

   \begin{figure}[htpb]
\centering
   	  \includegraphics{Stree.pdf}\label{Streeseps}
   	  \caption{Edges $(x,y) < (u,v)$ and separations $(A,B)= \alpha(x,y)\le\alpha(u,v)=(C,D)\!\!\!\!\!\!\!\!$}
   \label{fig:Stree}\vskip-6pt
   \end{figure}

\begin{LEM}\label{preservele}
Let $(T,\alpha)$ be an irredundant $S$-tree over a set $\F$ of stars of separations. Then $\alpha$ preserves the natural partial ordering on~$\vec E(T)$.
\end{LEM}

\begin{proof}
As $(T,\alpha)$ is irredundant, distinct edges in an oriented star~$\vec F_t$ in~$T$ map to distinct separations in~$\alpha(\vec F_t)$. These point towards each other, since $\alpha(\vec F_t)\in\F$ is a star. Formally, this means that for every $t\in T$ the map~$\alpha$ preserves the partial ordering $\le$ that $\vec E(T)$ induces on the elements of~$\vec F_t$ and their inverses. This propagates through~$\vec E(T)$, to the effect that $\alpha$ preserves this ordering on all of~$\vec E(T)$: whenever $\ve \le \vf$ in $\vec E(T)$ we have $\alpha(\ve)\le\alpha(\vf)$ in~$\vS$.
\end{proof}

Two edges of an irredundant $S$-tree over stars cannot have orientations pointing towards each other that map to the same separation, unless this is trivial:

\begin{LEM}\label{NewLemma}
Let $(T,\alpha)$ be an irredundant $S$-tree over a set $\F$ of stars. Let $e,f$ be distinct edges of~$T$ with orientations $\ve < \fv$ such that $\alpha(\ve) = \alpha(\vf) =:\vr$. Then $\vr$ is trivial.

In particular, $T$~cannot have distinct leaves associated with the same star~$\{\rv\}$ unless $\vr$ is trivial or $T$ has only one edge~$e$ and $\alpha(\ve)=\alpha(\ev)$ is degenerate.
\end{LEM}

\begin{proof}
If $\alpha$ maps all $\vedash$ with $\ve < \vedash < \fv$ to $\vr$ or to~$\rv$, then the $e$--$f$ path in $T$ has a node with two incoming edges mapped to~$\vr$. This contradicts our assumption that $(T,\alpha)$ is irredundant. Hence there exists such an edge~$\vedash$ with $\alpha(\vedash) = \vs$ for some $s\ne r$. Lemma~\ref{preservele} implies that $\vr = \alpha(\ve) \le \alpha(\vedash) \le\alpha(\fv) = \rv$, so $\vr\le\vs$ as well as $\vr \le \sv$ by~\eqref{invcomp}. As $s\ne r$ these inequalities are strict, so $s$ witnesses that $\vr$ is trivial.
\end{proof}

Recall that, by definition, stars of separations need not be antisymmetric. While it is important for our proofs to allow this,
   \COMMENT{}
   we can always contract an $S$-tree $(T,\alpha)$ over a set $\F$ of stars to an $S$-tree $(T',\alpha')$ over the subset $\F'\sub\F$ of its antisymmetric stars. Indeed, if $T$ has a node~$t$ such that $\alpha(\vec F_t)$ is not antisymmetric, then $t$ has neighbours $t',t''$ such that $\alpha(t',t) = \vs = \alpha(t,t'')$ for some $\vs\in \vS$. Let $T'$ be obtained from~$T$ by deleting the component of $T-t't - tt''$ containing~$t$ and joining $t'$ to~$t''$. Let $\alpha'(t',t'') := \vs$ and $\alpha'(t'',t') := \sv$, and otherwise let $\alpha':= \alpha\!\restriction\! \vec E(T')$. Then $(T',\alpha')$ is again an $S$-tree over~$\F$. Since we can do this whenever some $\vec F_t$ maps to a star of separations that is not antisymmetric, but only finitely often, we must arrive at an $S$-tree over~$\F'$.

Note that, in the procedure just described, the tree $T'$ has the same set of leaves as~$T$. We can thus strengthen Lemma~\ref{NewLemma} for edges at leaves, as follows:

\begin{LEM}\label{onlyedge}
   \COMMENT{}
   Let $(T,\alpha)$ be an $S$-tree over a set $\F$ of stars. Let $x$ be a leaf of~$T$, let $e$ be the edge of $T$ at~$x$, and let $\ve$ be oriented away from~$x$. Assume that $\vr = \alpha(\ve)$ is nontrivial and nondegenerate. Then $T$ has a minor $T'$ containing~$x$ such that $(T',\alpha')$, where $\alpha' = \alpha\!\restriction\!\vec E(T')$, is an irredundant $S$-tree over~$\F$, and such that $\ve$ is the only edge in~$\vec E(T')$ with $\alpha'(\ve)=\vr$.
\end{LEM}

\begin{proof}
By Lemma~\ref{prune} we may assume that $(T,\alpha)$ is irredundant.
   \COMMENT{}
   Suppose $T$ has an edge $f\ne e$ with an orientation $\vf$ such that $\alpha(\vf)=\vr$. By Lemma~\ref{NewLemma} we cannot have $\ve < \fv$, so $\ve < \vf$ since $\ve$ issues from a leaf. By Lemma~\ref{preservele}, every edge $\vedash$ with $\ve\le\vedash\le\vf$ satisfies $\vr = \alpha(\ve)\le\alpha(\vedash)\le\alpha(\vf) = \vr$, so $\alpha(\vedash) = \vr$. We can now apply the reduction described just before this lemma to the initial node $t$ of~$\vf$, to obtain a smaller $S$-tree over~$\F$ that is still irredundant and contains~$x$. Iterating, we obtain the desired $S$-tree $(T',\alpha')$.
\end{proof}

\section{Weak duality}\label{sec:weak}

Our paradigm in this paper is to capture the notion of `highly connected substructures' in a given  combinatorial structure by orientations $O$ of a set $S$ of separations of this structure that satisfy certain consistency rules laid down by specifying a set $\F$ of `forbidden' sets of oriented separations that $O$ must not contain.\looseness=-1

Let us say that a partial orientation $P$ of $S$ \emph{avoids} $\F\sub 2^{\vS}$ if $2^P\cap\F = \emptyset$. We say that $\F$ {\em forces\/} a separation $\vr\in\vS$ if $\{\rv\}\in\F$ or $r$ is degenerate. And we call $\F$ {\em standard\/} if it forces every trivial separation in~$\vS$.

\begin{THM}[Weak Duality Theorem]\label{thm:weak}
  Let $(\vS,\le\,,\!{}^*)$ be a separation system and $\F\sub 2^\vS\!$ a standard set of stars.
   \COMMENT{}
   Then exactly one of the following assertions holds:
\begin{enumerate}[\rm(i)]\itemsep0pt
  \item There exists an ${S}$-tree over~$\F$.
    \COMMENT{}
  \item There exists an orientation of~${S}$ that avoids~$\F$.
      \COMMENT{}
  \end{enumerate}
\end{THM}

For the easy direction, that (i) and (ii) cannot both hold, we do not need the assumptions that $\F$ is standard and consists of stars:

\begin{LEM}\label{lem:notboth}
  Let $(\vS,\le\,,\!{}^*)$ be a separation system and $\F\sub 2^\vS$.
  If there exists an ${S}$-tree over~$\F$, then no orientation of~${S}$ avoids~$\F$.
\end{LEM}

\begin{proof}
  Let $(T,\alpha)$ be an ${S}$-tree over $\F$, and let $O$ be an orientation of~${S}$. Let $t\in V(T)$ be a sink in the orientation of the edges of~$T$ that $O$ induces via~$\alpha$.
   \COMMENT{}
   Then $\alpha(\vec F_t) \sub O$. Since $\alpha(\vec F_t)\in\F$, as $(T,\alpha)$ is an $S$-tree, this means that $O$ does not avoid~$\F$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:weak}]
  By Lemma~\ref{lem:notboth}, at most one of (i) and (ii) holds.
  We now show that at least one of them holds. Let
 $$O^- := \{\,\vs\mid \{\sv\}\in\F\,\}.$$
   \COMMENT{}
    Then any $\F$-avoiding orientation of~$S$ must include~$O^-$. As $\F$ is standard, $O^-$~contains all the trivial separations in~$\vS$.

If $O^-\supe \{\vs,\sv\}$ for some~$s\in S$, possibly degenerate, then $(T,\alpha)$ with $T=K_2$ and ${\rm im}\,\alpha=\{\vs,\sv\}$ is an $S$-tree over~$\F$. So we may assume that $O^-$ is antisymmetric: a~partial orientation of~$S\sm D$, where $D$ is the set of degenerate elements of~$S$. We apply induction on $|S\sm D|-|O^-|$ to show that, whenever $\F$ is such that $O^-$ is antisymmetric, either (i) or (ii) holds.

  If $|S\sm D| = |O^-|$, then ${O^-\cup\vec D}$ is an orientation of all of~${S}$. If (ii) fails then ${O^-\cup\vec D}$~has a subset $\sigma\in\F$. By definition of~$O^-$, and since $O^-$ is antisymmetric, $\sigma$~is not a singleton set.
   \COMMENT{}
   Let $T$ be a star of $|\sigma|$ edges with centre~$t$, say, and let $\alpha$ map its oriented edges $(x,t)$ bijectively to~$\sigma$. Then $(T,\alpha)$ satisfies~(i).
   \COMMENT{}

We may thus assume that ${S\sm D}$ contains a separation $s_0$ such that neither $\vso$ nor~$\svo{}$ is in ${O^-}$. Then $\vso$ and~$\svo{}$ are nontrivial. Let
 $$\F_1 := \F\cup\{\{\vso\}\}\quad\text{and}\quad\F_2 := \F\cup\{\{\svo{}\}\},$$
 and put $O^-_i  := \{\,\vs\mid \{\sv\}\in\F_i\,\}$ for $i=1,2$. Note that $|O^-_i| > |O^-|$, and $O^-_i$ is again antisymmetric.

Since any $\F_i$-avoiding orientation of~$S$ also avoids~$\F$, we may assume that no orientation of~$S$ avoids~$\F_i$, for both $i=1,2$. By the induction hypothesis, there are ${S}$-trees $(T_i,\alpha_i)$ over~$\F_i$. Unless one of these is in fact over~$\F$,
   \COMMENT{}
   the tree $T_1$~has a leaf~$x_1$ associated with~$\{\vso\}$, while $T_2$ has a leaf $x_2$ associated with~$\{\svo\}$. Use Lemma~\ref{prune} to prune the $(T_i,\alpha_i)$ to irredundant $S$-trees $(T'_i,\alpha'_i)$ over~$\F_i$ containing~$x_i$. As $\svo$ and~$\vso{}$ are nontrivial, and $s_0\notin D$, Lemma~\ref{NewLemma} implies that $x_1$ and $x_2$ are the only leaves of $T'_1$ and~$T'_2$ associated with $\{\vso\}$ and~$\{\svo\}$, respectively.

  Let $T$ be the tree obtained from the disjoint union of~$T'_1-x_1$ and $T'_2-x_2$ by joining  the neighbour $y_1$ of $x_1$ in~$T'_1$ to the neighbour~$y_2$ of~$x_2$ in~$T'_2$. Let $\alpha\colon\vec E(T)\to \vS$ map $(y_1,y_2)$ to~$\vso$ and $(y_2,y_1)$ to~$\svo{}$ and otherwise extend $\alpha'_1$ and~$\alpha'_2$. Then $\alpha'_1(y_1,x_1) = \alpha(y_1,y_2) = \alpha'_2(x_2,y_2)$, so $\alpha$ maps the oriented stars of edges at $y_1$ and~$y_2$ to the same stars of separations in~$\vS$ as~$\alpha'_1$ and~$\alpha'_2$ did. These lie in~$\F$, so $(T,\alpha)$ is an ${S}$-tree over~$\F$.
\end{proof}

Theorem~\ref{thm:weak}, alas, has a serious fault: there are few, if any, sets $S$ and $\F\sub 2^\vS$ such that $\F$ consists of stars in~$\vS$ and the $\F$-avoiding orientations of~$S$ (all of them) capture an interesting notion of highly connected substructure found in the wild. The reason for this is that we are not, so far, requiring these orientations $O$ to be consistent: we allow that $O$ contains separations $\rv$ and $\vs$ when $\vr < \vs$, which will not usually be the case when $O$ is induced by a meaningful highly connected substructure in the way discussed earlier.

So what happens if we strengthen (ii) so as to ask for a consistent orientation of~$S$? Our requirement that $\F$ be standard is certainly compatible with this: as noted earlier, consistent orientations of~$S$ have to contain all the trivial separations in~$\vS$.

Still, our proof breaks down as early as the induction start: we now also have to ask that $O^-$~-- indeed, $O^-\cup D$~-- should be consistent. Again, it is not unnatural even to require even that $O^-$ be closed down in~$(\vS,\le)$ (which implies consistency),
   \COMMENT{}
   or equivalently, that if $\{\vr\}\in\F$ and $\vr < \vs$ then also $\{\vs\}\in\F$. For if a singleton star $\{\vr\}$ is in~$\F$, the idea is that the part of our structure to which $\vr$ points is too small to contain a highly connected substructure; and then the same should apply to all $\vs\ge\vr$.
   \COMMENT{}

But now we have a problem at the induction step: when forming the~$\F_i$, we now have to add not only $\{\vso\}$ and~$\{\svo{}\}$ to~$\F$, but all singleton stars $\{\vs\}$ with $\vso\le\vs$ or $\svo{}\le\vs$, respectively, to keep $O^-$ closed down. This, then, spawns more problems: now the $T_i$ can have many leaves associated with a singleton star of $\F_i$ that is not in~$\F$.
   \COMMENT{}
   Even if each of these occurs only once, there is no longer an obvious way of how to merge $T_1$ and~$T_2$ into a single $S$-tree over~$\F$.

We shall deal with this problem in the next section, as follows. Rather than adding singletons of the orientations of some fixed separation $s_0$ to~$\F$ to form the~$\F_i$ we shall add some~$\{\rvi\}$ such that $\vri$ is minimal in~$\vS\sm(O^-\cup D)$. Then $\{\rvi\}$ can be associated with at most one leaf of~$(T'_i,\alpha'_i)$, because $\vri\notin O^-$ will be nontrivial (cf.\ Lemma~\ref{NewLemma}). These $\vri$ will be chosen nested, so that both point to some $s_0$ between them. We shall then modify the two $S$-trees over the~$\F_i$ into $S$-trees over $\F\cup\{\{\vso\}\}$ and~$\F\cup\{\{\svo\}\}$ by `shifting' their separations to either side of~$s_0$, and then merge these shifted $S$-trees as before to obtain one over~$\F$.\looseness=-1

\section{Strong duality}\label{sec:strong}

Let $\vr$ be a nontrivial and nondegenerate
   \COMMENT{}
    element of a separation system ${(\vS,\le\,,\!{}^*)}$ contained in some universe $(\vU,\le\,,\!{}^*,\vee,\wedge)$ of separations,
   \COMMENT{}
   the ordering and involution on~$\vS$ being induced by those of~$\vU$. Assume that $\{\rv\}$ is associated with a leaf of an irredundant $S$-tree $(T,\alpha)$ over some standard set $\F\sub 2^\vS$ of stars.

Consider any $\vso\in\vS$ such that $\vr\le\vso$.
   \COMMENT{}
   Our aim is to `shift' $(T,\alpha)$ to a new $S$-tree $(T,\alpha')$ based on the same tree~$T$, by modifying $\alpha$ in such a way that $\vso$ points to all the separations in the image of~$\alpha'$.

Let $S_{\ge\vr}$ be the set of all separations $s\in S$ that have an orientation ${\vs\ge\vr}$. Since  $\{\rv\}$ is associated with a leaf, and the $T$-edge at that leaf, when oriented away from it, points to all the other edges of~$T$ (Fig.~\ref{fig:shiftsep}, left), Lemma~\ref{preservele} implies that $\vSr$
   \COMMENT{}
   includes the image of~$\alpha$. And since $\vr$ is nontrivial, only one of the two orientations $\vs$ of every $s\in S_{\ge\vr}\sm\{r\}$ satisfies $\vs\ge\vr$. Letting
 $$f\shift(\!\vr)(\vso) (\vs) := \vs\vee\vso\quad\text{and}\quad f\shift(\!\vr)(\vso) (\sv) := (\vs\vee\vso)^*$$
 for all $\vs \ge \vr$ in $\vSr\sm\{\rv\}$
   \COMMENT{}
   thus defines a \emph{shifting map} $f\shift(\!\vr)(\vso)\colon \vSr\to\vU$ (Fig.~\ref{fig:shiftsep}, right).
   \COMMENT{}
   Note that
   \COMMENT{}
   $f\shift(\!\vr)(\vso)(\vr) = \vso$, since $\vr\le\vso$.

   \begin{figure}[htpb]
\centering
   	  \includegraphics{shiftsep.pdf}
   	  \caption{Shifting $\alpha(\ve) = \vs$ to $\alpha'(\ve) = \vs\vee\vso$}
   \label{fig:shiftsep}\vskip-6pt
   \end{figure}

The concatenation
 $$\alpha' := f\shift(\!\vr)(\vso) \circ\ \alpha$$
 is a well-defined map from $\vec E(T)$ to~$\vU$. We would like it to take its images in~$\vS$, but will need some assumptions to ensure this.

To help us show that $(T,\alpha')$ is over~$\F$ if $(T,\alpha)$ is, we also need that $f\shift(\!\vr)(\vso)$ maps the stars $\alpha(\vec F_t)$ to stars. This would be immediate if we could show that $f\shift(\!\vr)(\vso)$ preserved the ordering~$\le$ on~$\vec E(T)$. It does in fact do this, but only with one exception: if $\vr < \rv$,
   \COMMENT{}
   it can happen that $f\shift(\!\vr)(\vso)(\vr) = \vso \not< \svo = f\shift(\!\vr)(\vso)(\rv)$.
   \footnote{This is because $f\shift(\!\vr)(\vso)(\rv)$, unlike $f\shift(\!\vr)(\vso)(\vs)$ for all other $\vs \ge \vr$, was defined indirectly as the inverse of~$f\shift(\!\vr)(\vso)(\vr)$. Note that Lemma~\ref{lem:shifting} excludes {\em only} this case: every $\vs\in\vSr$ other than~$\vr$ itself relates to $\rv$ via its relationship to~$\vr$ and~\eqref{invcomp}, which $f\shift(\!\vr)(\vso)$ preserves.}
   \COMMENT{}
   By choosing $(T,\alpha)$ irredundant we shall be able to ensure that this exception remains irrelevant,
   \COMMENT{}
   but until then we have to exclude it:

\begin{LEM}\label{lem:shifting}
The map $f = f\shift(\!\vr)(\vso)$ preserves the ordering $\le$ on $\vSr\sm\{\rv\}$.
   \COMMENT{}
\end{LEM}

\begin{proof}
Consider separations $\vs\le\vsdash$ in~$\vSr\sm\{\rv\}$.
Suppose first that $\vr\le\vs$.
   \COMMENT{}
   Then $f(\vsdash) = \vsdash\vee\vso$ lies above (is $\ge$ than) both $\vso$ and~$\vs$.
   \COMMENT{}
   It therefore also lies above their supremum $f(\vs) = \vs\vee\vso$.
    \COMMENT{}
  We may therefore assume that $\vr\le\sv$.

If even $\vr\le\svdash$, then $\vr\le\svdash\le\sv$.
   \COMMENT{}
   This reduces to the case above on renaming $\svdash$ as~$\vs$ and $\sv$ as~$\vsdash$. We may thus assume that $\vr\le\vsdash$.

Now $f(\vs) = (\sv\vee\vso)^* = \vs\wedge\svo\le \vs\le\vsdash\le \vsdash\vee\vso = f(\vsdash)$ by~\eqref{deMorgan}.
   \COMMENT{}
\end{proof}

Let us say that $\vso\in\vS$ is \emph{linked to} $\vr\in\vS$ if $\vso\ge\vr$ and every $\vs\ge\vr$ such that $\vs\ne\rv$
   \COMMENT{}
   satisfies $\vs\vee\vso\in\vS$. (This will ensure that $\alpha'$ has its image in~$\vS$.) Let us call $\vS$ \emph{separable} if for every two nontrivial and nondegenerate $\vr,\rvdash\in\vS$ such that $\vr\le\vrdash$ there exists an $s_0\in S$ with an orientation $\vso$ linked to~$\vr$ and its inverse $\svo$ linked to~$\rvdash$. (Notice that any such~$s_0$ will also be nondegenerate.)
   \COMMENT{}

\begingroup\lineskiplimit=-2pt
Finally, we need a condition on~$\F$ to ensure that the shifts of stars of separations associated with nodes of~$T$ are not only again stars but are also again in~$\F$. Let us say that a separation $\vso\in\vS$ is \emph{$\F$-linked} to~$\vr\in\vS$ if $\vso$ is linked to $\vr$ and the  image under $f\shift(\!\vr)(\vso)$ of any star $\sigma\sub \vSr\sm\{\rv\}$ in~$\F$ that has an element $\vs\ge\vr$
   \COMMENT{}
   is again in $\F$.
   \COMMENT{}
    We say that $\vS$ is \emph{$\F$-separable} if for all $\vr,\rvdash\in\vS$ that are not forced by~$\F$
   \COMMENT{}
   and satisfy $\vr\le\vrdash$ there exists an $s_0\in S$ with an orientation~$\vso$ that is $\F$-linked to~$\vr$  and such that $\svo$ is $\F$-linked to~$\rvdash$.

\endgroup
Often, the proof that $\vS$ is $\F$-separable can be split into two easier parts, a proof that $\vS$ is separable and one that $\F$ is \emph{closed under shifting}: that whenever $\vso\in\vS$ is linked to some $\vr\le\vso$ not forced by~$\F$ it is even $\F$-linked to~$\vr$. Indeed, the following lemma is immediate from the definitions:

\begin{LEM}\label{lem:Fsep}
  If $\vS$ is separable and $\F$ is closed under shifting, then $\vS$ is $\F$-separable.\qed
\end{LEM}

   In Section~\ref{sec:appl} we shall see that for all sets $\F$ describing classical highly connected substructures, such as tangles and brambles (as well as many others), the relevant separation systems $\vS$ are $\F$-separable. In most cases, $\F$~will even be closed under shifting, in which case we will simply prove this stronger property.

We now have all the ingredients needed to shift an $S$-tree:

\begin{LEM}\label{lem:shifttree}
  Let $\F\sub 2^\vS$ be a set of stars,
   \COMMENT{}
   and let $(T,\alpha)$ be an irredundant ${S}$-tree over~$\F$. Let $x$ be a leaf of~$T$, let $\ve$ be its edge at~$x$ oriented away from~$x$, and assume that $\vr = \alpha(\ve)$ is nontrivial and nondegenerate. Suppose that $\alpha(\vedash)\ne\vr$ for every other $\vedash\in\vec E(T)$. Let $\vso\in\vS$ be $\F$-linked to~$\vr$,
   \COMMENT{}
   and let $\alpha' := f\shift(\!\vr)(\vso) \circ\ \alpha$. Then $(T,\alpha')$ is an $S$-tree over~$\F\cup\{\{\svo\}\}$ in which $\{\svo\}$ is associated with~$x$ but with no other leaf of~$T$.
\end{LEM}

\begin{proof}
  Since $\F$ consists of stars and $(T,\alpha)$ is irredundant, the map $\alpha$ preserves the natural ordering on~$\vec E(T)$ (Lemma~\ref{preservele}). Since $\{\rv\}$ is associated with a leaf of~$T$, and every edge of $T$ has an orientation away from this leaf, $\alpha$~maps $\vec E(T)$ to~$\vSr$. As $f\shift(\!\vr)(\vso)$ is defined on this set, the map $\alpha'$~is well defined. Its image lies in~$\vS$, because $\vso$ is linked to~$\vr$.
   \COMMENT{}\looseness=-1

By assumption, $x$~is the only node $t$ of~$T$ such that $\rv\in\alpha(\vec F_t)$. We may thus apply Lemma~\ref{lem:shifting} to deduce that $f\shift(\!\vr)(\vso)$ maps the stars $\alpha(\vec F_t)\in\F$ with $t\ne x$ to stars, and as $\vso$ is $\F$-linked to~$\vr$ these lie in~$\F$.
   \COMMENT{}
   As $x$ is associated with~$\{\rv\}$ in $(T,\alpha)$ and $f\shift(\!\vr)(\vso)(\rv) = \svo$, this means that $(T,\alpha')$ is an $S$-tree over~$\F\cup \{\{\svo\}\}$ in which $x$ is associated with~$\{\svo\}$.

Suppose $\{\svo\}$ is also associated in~$(T,\alpha')$ with another leaf $y\ne x$ of~$T$.
   \COMMENT{}
   Let $\{\rvdash\}$ be associated with $y$ in~$(T,\alpha)$. Then $f\shift(\!\vr)(\vso)(\vrdash) = \vso$, while $\vrdash \le \rv$ by Lemma~\ref{preservele}.
   \COMMENT{}
If $\vr = \vso$ then $f\shift(\!\vr)(\vso)$ is the identity on~$\vSr$,
   \COMMENT{}
   so $\{\svo\} = \{\rv\}$ is associated with $x$ and $y$ also in $(T,\alpha)$. But this contradicts our assumptions about~$\vr$.
   \COMMENT{}
   Hence $\vr < \vso = f\shift(\!\vr)(\vso)(\vrdash) \le f\shift(\!\vr)(\vso)(\rv) = \svo$, where the $\le$ comes from applying Lemma~\ref{lem:shifting} to $\vr\le\rvdash$ (neither of which is~$\rv$, by assumption), and then applying~\eqref{invcomp}.
   \COMMENT{}
   Thus, $s_0$ witnesses that $\vr$ is trivial in~$\vS$, contrary to our assumptions.
   \COMMENT{}
   \end{proof}

We can now strengthen our weak duality theorem so as to yield consistent orientations, provided that $\vS$ is $\F$-separable. Given a separation system $(\vS,\le\,,\!{}^*)$ and a set $\F\sub 2^\vS$, let us call an orientation $O$ of~$S$ an {\em $\F$-tangle\/} if it is consistent and avoids~$\F$, that is, $2^O\cap\F = \emptyset$.

\begin{THM}[Strong Duality Theorem]\label{thm:strong}
  Let $(\vU,\le\,,\!{}^*,\vee,\wedge)$ be a universe of  separations containing a separation system $(\vS,\le\,,\!{}^*)$. Let $\F\sub 2^\vS$ be a standard set of stars. If $\vS$ is $\F$-separable,
   \COMMENT{}
   exactly one of the following assertions holds:
\begin{enumerate}[\rm(i)]\itemsep0pt
  \item There exists an ${S}$-tree over $\F$.
  \item There exists an $\F$-tangle of~$S$.
  \end{enumerate}
\end{THM}

\goodbreak

\begin{proof}
  By Lemma \ref{lem:notboth}, (i) and (ii) cannot both hold; we show that at least one of them holds. The set
 $$O^- := \{\,\vs\mid \{\sv\}\in\F\,\}$$
 contains all the trivial separations in~$\vS$, because $\F$ is standard. If $O^-\supe \{\vs,\sv\}$ for some~$s\in S$, then $(T,\alpha)$ with $T=K_2$ and ${\rm im}\,\alpha=\{\vs,\sv\}$ is an $S$-tree over~$\F$. We may thus assume that $O^-$ is antisymmetric. In particular, then, $O^-$~contains no degenerate elements of~$\vS$.

Let $D$ be the set of degenerate elements of~$S$. Let $R$ be the set of separations in $S\sm D$ of which neither orientation lies in~$O^-$. We apply induction on $|R|$
   \COMMENT{}
   to show that (i) or~(ii) holds whenever $\F$ is such that $O^-$ is antisymmetric.
   \COMMENT{}

Before we start the induction, let us show that $O^-$ is consistent. If not, then $O^-$ contains some $\rv$ and~$\vrdash$ such that $\vr < \vrdash$. As $O^-$ is antisymmetric, it then does not contain their inverses $\vr$ and~$\rvdash$,
   \COMMENT{}
  so $\F$ does not force these.
   \COMMENT{}
   Since $\vS$ is $\F$-separable, there exists an $s_0\in S$ with orientations~$\vso,\svo$ such that $\vso$ is $\F$-linked to~$\vr$ and $\svo$ is $\F$-linked to~$\rvdash$. Since $r$ is not degenerate
   \COMMENT{}
   and $\vso$ is $\F$-linked to~$\vr$, the singleton star $\{\vr\}\in\F$
   \COMMENT{}
   shifts to $\{f\shift(\!\vr)(\vso) (\vr)\} = \{\vso\}\in\F$, so $\svo\in{O^-}$. Likewise, since $r'$ is not degenerate and $\svo$ is linked to~$\rvdash$ we have $\vso\in{O^-}$. This contradicts our assumption that ${O^-}$ is antisymmetric.

Let us show that $O^-\cup \vec D$ is still consistent. Suppose $r\ne s$ are such that $\rv,\vs\in O^-\cup\vec D$ and $\vr < \vs$. Then $r$ and $s$ are not both in~$D$, since that would imply $\vr < \vs = \sv < \rv = \vr$. Since $O^-$ is consistent, we may thus assume that $\rv\in O^-$ and $\vs\in\vec D$ (or vice versa, which is equivalent by~\eqref{invcomp}).
   \COMMENT{}
   Then $\vr$ is trivial, as $\vr < \vs = \sv$. Hence $\vr\in O^-$ as well as, by assumption, $\rv\in O^-$. This contradicts our assumption that $O^-$ is antisymmetric.

If $|R|=0$, then $O^-\cup\vec D$ is either itself an $\F$-tangle of~$S$ or contains a star $\sigma\in\F$. By definition of~$O^-$, and since $O^-$ is antisymmetric, $\sigma$~is not a singleton subset of~$O^-$,
   \COMMENT{}
   and hence not a singleton subset of~$\vec D$ either (because that would be a subset of~$O^-$ since it lies in~$\F$). Thus, $|\sigma|\ge 2$. Let $T$ be a star of $|\sigma|$ edges with centre~$t$, say, and let $\alpha$ map its oriented edges $(x,t)$ bijectively to~$\sigma$. Then $(T,\alpha)$ satisfies~(i).
   \COMMENT{}

For the induction step,
   \COMMENT{}
   pick $\vro\in\vec R$.
   \COMMENT{}
   Then neither $\vro$ nor $\rvo$ lies in~$O^-\cup\vec D$; let $\vrone\le\vro$ and $\rvtwo\le\rvo$ be minimal in~$\vS\sm (O^-\cup\vec D)$.
   \COMMENT{}
   Then $\vrone\le\vro\le\vrtwo$. As $\F$ forces neither $\vrone$ nor~$\rvtwo$
   \COMMENT{}
     and $\vS$ is $\F$-separable, there exists an ${s_0\in S}$ with orientations~$\vso,\svo$ such that $\vso$ is $\F$-linked to~$\vrone$ and $\svo$ is $\F$-linked to~$\rvtwo$.
   \COMMENT{}

Since $O^-$ is antisymmetric, it does not contain both $\vso$ and~$\svo$. Let us assume that $\svo\notin O^-$, i.e.\ that $\{\vso\}\notin\F$. Then $\{\vrone\}\notin\F$, because $\vso$ is $\F$-linked to~$\vrone$ and $f\shift(\vrone)(\vso)$ maps the star $\{\vrone\}\sub \vSrone\sm\{\rvone\}$ to~$\{\vso\}$. Thus, $\vrone$ and $\rvone$ both lie outside $O^-\cup\vec D$.

We can now hope to apply the induction hypothesis to~$\F_1 := \F\cup\{\{\rvone\}\}$, because
 $$O^-_1 := O^-\cup \{\vrone\} =  \{\,\vs\mid \{\sv\}\in\F_1\,\}$$
 is again antisymmetric,
   \COMMENT{}
   and the set $R_1$ of separations in $S\sm D$ with neither orientation in $O^-_1$ is smaller than~$R$. Also, $\F_1$~is a standard set of stars, because $\F$~is. But we still have to check that $\vS$ is $\F_1$-separable.

   \begingroup\lineskiplimit=-3pt
To do so, consider separations $\vr,\rvdash\in\vS$ not forced by~$\F_1$ such that $\vr\le\vrdash$. We have to find an $s_1\in S$ with an orientation~$\vsone$ that is $\F_1$-linked to~$\vr$  and such that $\svone$ is $\F_1$-linked to~$\rvdash$. By assumption, there is such an $s_1\in S$ for $\vr$ and $\vrdash$ with respect to~$\F$; let us take this~$s_1$, with orientations $\vsone,\svone$ such that $\vsone$ is $\F$-linked to~$\vr$ and $\svone$ is $\F$-linked to~$\rvdash$. We have to show that these are even $\F_1$-linked as above, i.e., that for the unique star $\{\rvone\}$ in $\F_1\sm\F$ we have $\{f\shift(\!\vr)(\vsone) (\rvone)\}\in\F_1$ if $\vr\le\rvone\ne\rv$
   \COMMENT{}
   (so that $\{\rvone\}\sub \vSr\sm\{\rv\}$),
   \COMMENT{}
   and $\{f\shift(\rvdash)(\svone) (\rvone)\}\in\F_1$ if $\rvdash\le\rvone\ne\vrdash$. In either case, the image $\sv$ of~$\rvone$ under the relevant map is either equal to~$\rvone$ (in which case we are done)
   \COMMENT{}
   or greater,
   \COMMENT{}
   by definition of the shift operator$\,\downarrow$. If $\rvone < \sv$, then $s\notin D$, since otherwise ${\vr\le\rvone < \vs=\sv}$ would be trivial
    \COMMENT{}
   and hence forced by~$\F$. And $\vs < \vrone$ by~\eqref{invcomp}, so $\vs\in O^-\cup\vec D$ by the minimality of $\vrone$ in~$\vS\sm (O^-\cup\vec D)$. Thus $\vs\in O^-$, and hence ${\{\sv\}\in\F\sub\F_1}$, by the definition of~$O^-$. This completes our proof that $\vS$ is $\F_1$-separable.

   \endgroup
We can thus apply the induction hypothesis to~$\F_1$. If it returns an $\F_1$-tangle of~$S$, then this is our desired $\F$-tangle. So we may assume that it returns an $S$-tree $(T_1,\alpha_1)$ over~$\F_1$. If this $S$-tree is even over~$\F$, our proof is complete. We may thus assume that $T_1$ has a leaf $x_1$ associated with~$\{\rvone\}$. We now apply Lemma~\ref{onlyedge} to prune $(T_1,\alpha_1)$ to an irredundant $S$-tree over~$\F_1$ that still contains~$x_1$, and in which no oriented edge other than the edge $\ve$ issuing from~$x_1$ maps to~$\vrone$. For simplicity, let us continue to call this $S$-tree $(T_1,\alpha_1)$. Let $\alpha'_1 := f\shift(\vrone)(\vso)\circ\alpha_1$. By Lemma~\ref{lem:shifttree}, $(T_1,\alpha_1)$ shifts to an $S$-tree $(T_1,\alpha'_1)$ over $\F\cup\{\{\svo\}\}$, in which $x_1$ is associated with~$\{\svo\}$ but with no other leaf of~$T_1$. All the other nodes of $T_1$ are therefore associated with stars in~$\F$.
   \COMMENT{}

If $\{\svo\}\in\F$,
   \COMMENT{}
   then $(T_1,\alpha'_1)$ is in fact an $S$-tree over~$\F$, completing our proof. We may thus assume that $\{\svo\}\notin\F$, or equivalently that $\vso\notin O^-$. We can now use the induction hypothesis exactly as above (where we assumed that $\svo\notin O^-$),
   \COMMENT{}
   considering~$\rvtwo$ in the same was as we just treated~$\vrone$, to obtain an irredundant $S$-tree $(T_2,\alpha'_2)$ over $\F\cup\{\{\vso\}\}$ in which $\{\vso\}$ is associated with a unique leaf~$x_2$, and all the other nodes are associated with stars in~$\F$.
   \COMMENT{}

These trees can now be combined to the desired $S$-tree $(T,\alpha)$ over~$\F$ as in the proof of Theorem~\ref{thm:weak}:
   \COMMENT{}
   add to the disjoint union $(T_2 - x_2)\cup (T_1 - x_1)$ the edge $y_2y_1$ between the neighbour $y_2$ of $x_2$ in $T_2$ and the neighbour $y_1$ of $x_1$ in~$T_1$, put $\alpha(y_2,y_1) := \vso$ and $\alpha(y_1,y_2) := \svo$, and otherwise let $\alpha$ extend $\alpha'_1$ and~$\alpha'_2$.
\end{proof}

\section{Applications of strong duality}\label{sec:appl}

In this section we show that the separation systems usually considered for graphs and matroids are all separable, and that the collections $\F$ needed to capture highly connected substructures such as tangles, brambles and blockages are closed under shifting. This will make our strong duality theorem imply the classical duality theorems for graphs and matroids. We also obtain some interesting new such theorems.
   \COMMENT{}

Let us call a real function $\vs\mapsto\ord(\vs)$ on a universe $(\vU,\le\,,\!{}^*,\vee,\wedge)$
   \COMMENT{}
   of oriented separations an \emph{order function} if it is non-negative, symmetric and submodular, that is, if $0\le \ord(\vs)=\ord(\sv)$ and
\[\ord(\vr\vee\vs) + \ord(\vr\wedge\vs)\le \ord(\vr)+\ord(\vs)\]
for all $\vr,\vs\in \vU$. We then call $\ord(s) := \ord(\vs)$ the \emph{order} of $s$ and of~$\vs$. For every positive integer~$k$,
 $$\vS_k := \{\vs\in \vU : \ord(\vs) < k\}$$
is a separation system (though not necessarily a universe).

\goodbreak

\begin{LEM}\label{lem:separable}
  Every such $\vS_k$ is separable.
\end{LEM}

\begin{proof}
Given nontrivial and nondegenerate $\vr,\rvdash\in\vS_k$ such that $\vr\le\vrdash$, we have to find an $\vso\in \vS_k$ such that $\vso$ is linked to~$\vr$ and $\svo$ is linked to~$\rvdash$. We choose $\vso\in\vU$ of minimum order with $\vr\le\vso\le\vrdash$.
   \COMMENT{}
   Since $\vr$ is a candidate for~$\vso$, we have $\ord(\vso)\le\ord(\vr)$ and hence $\vso\in\vS_k$. We show that $\vso$ is linked to~$\vr$; by symmetry, this will imply also that $\svo$ is linked to~$\rvdash$.

Let us show that every $\vs\ge\vr$ in~$\vS_k$ satisfies $\vs\vee\vso\in\vS_k$.
   \COMMENT{}
   We prove this by showing that $\ord(\vs\vee\vso)\le \ord(\vs)$,
   \COMMENT{}
   which will follow from submodularity once we have shown that $\ord(\vs\wedge\vso)\ge \ord(\vso)$. This, however, holds since $\vs\wedge\vso$ was a candidate for the choice of~$\vso$: we have $\vr\le\vs\wedge\vso$ since $\vr\le\vs$ and $\vr\le\vso$, while $\vs\wedge\vso\le\vso\le\vrdash$.
\end{proof}

For most of this section (all except~\ref{subsec:bwdsubmodular}), whenever we consider a graph $G=(V,E)$ it will have at least one vertex, and we consider the universe $\vU$ of its (oriented) \emph{vertex separations}, the separations $(A,B)$ of~$V$ such that $G$ has no edge between $A\sm B$ and~$B\sm A$. We then take
 $$\ord(A,B) := \abs{A\cap B}$$
 as our order function for~$\vU$.

\subsection{Branch-width and tangles of graphs}\label{subsec:bwd}

Robertson and Seymour~\cite{GMX} introduced branch-width and tangles for graphs, and more generally for hypergraphs. For the sake of readability we only treat simple graphs here (no parallel edges or loops), but our results extend readily to multigraphs and hypergraphs with the obvious adaptations.

Let $G = (V,E)$ be a finite
   \COMMENT{}
graph. A \emph{tangle of order~$k$} in~$G$ is (easily seen to be equivalent to)
   \COMMENT{}
          an orientation of~$S_k$ that avoids
 $$\F := \big\{\{(A_1,B_1), (A_2,B_2), (A_3,B_3)\}\sub \vS_k : G[A_1]\cup G[A_2]\cup G[A_3] = G\big\}.$$
(The three separations $(A_1,B_1), (A_2,B_2), (A_3,B_3)$ need not be distinct.) This set $\F$ is clearly standard; in fact, it forces all the small separations in~$\vS_k$, those of the form~$(A,V)$.

Notice that any $\F$-avoiding orientation $O$ of~$S_k$ is consistent, and therefore an $\F$-tangle in our sense, since for any pair of separations $(C,D)\le (A,B)$ we have $G[D]\cup G[A]\supe G[B]\cup G[A] = G$ and hence $\{(D,C),(A,B)\}\in\F$. Similarly, $O$~must contain all $(A,B)$ with $|A|<k$: it cannot contain $(B,A)$, as $(A,V)\in O$ by~$\{(V,A)\}\in\F$ but $\{(B,A),(A,V)\}\in\F$.
   \looseness=-1

Since our duality theorems, so far, only work with $\F$ consisting of stars of oriented separations, let us consider the set $\F^*$ of those sets in~$\F$ that are stars. Using submodularity we can easily show that an $\F^*$-avoiding orientation of~$S_k$ in fact avoids all of~$\F$~-- but only if we assume consistency:
   \COMMENT{}

\begin{LEM}\label{F*toF}
Every consistent $\F^*$-avoiding orientation $O$ of~$S_k$ avoids~$\F$.
\end{LEM}

\begin{proof}
   \COMMENT{}
   Suppose $O$ has a subset $\sigma\in\F$. We show that as long as this set is not an inclusion-minimal nested set in~$\F$, we can either delete one of its elements, or replace it by a smaller separation in~$O$, so that the resulting set $\sigma'\sub O$ is still in~$\F$ but is smaller or contains fewer pairs of crossing separations. Iterating this process, we eventually arrive at a minimal nested set in~$\F$ that is still a subset of~$O$. By its minimality, this set is an antichain,
   \COMMENT{}
   and all consistent nested antichains are stars. Our subset of $O$ will thus lie in~$\F^*$, contradicting our assumption that $O$ avoids~$\F^*$.

If $\sigma$ has two comparable elements, we delete the smaller one and retain a subset of $O$ in~$\F$. We now assume that $\sigma$ is an antichain, but that it contains two crossing separations, $\vr = (A,B)$ and $\vs = (C,D)$ say. As these and their inverses lie in~$\vS_k$, submodularity implies that one of the separations $(A\cap D, {B\cup C})\le (A,B)$ and $(B\cap C, A\cup D)\le (C,D)$ also lies in~$\vS_k$. Let us assume the former; the other case is analogous.

Let $\sigma'$ be obtained from $\sigma$ by replacing $\vr$ with $\vrdash := (A\cap D, B\cup C)\in\vS_k$. Then $\sigma'$ is still in~$\F$, since any vertex or edge of $G[A]$ that is not in $G[A\cap D]$ lies in~$G[C]$, and $(C,D)$ is still in~$\sigma'$. Moreover, while $\vr$ crosses~$\vs$, clearly $\vrdash$ does not. To complete the proof, we just have to show that $\vrdash$ cannot cross any separation $\vt\in\sigma'$ that was nested with~$\vr$.

If $\vr\le\vt$ or $\vr\le\tv$, then $\vrdash\le\vr$ is nested with~$\vt$, as desired. If not then $\vt\le \vr$, since $\{\vr,\vt\}\sub O$ is consistent.
   \COMMENT{}
   This contradicts our assumption that $\sigma$ is an antichain.
\end{proof}

\begin{LEM}\label{TanglesShiftable}
$\F^*$ is closed under shifting.
\end{LEM}

\begin{proof}\sloppy
This is easy from the definitions. Informally, if $(X,Y)\in\vS = \vS_k$ is linked to some $\vr\le (X,Y)$ not forced by~$\F$ and we shift a star
  \[\sigma = \{(A_1,B_1), (A_2,B_2), (A_3,B_3)\}\sub \vSr\sm\{\rv\}\]
 with $\vr\le (A_1,B_1)$, say, then we replace $(A_1,B_1)$ with~$(A_1\cup X,B_1\cap Y)$, and $(A_i,B_i)$ with $(A_i\cap Y,B_i\cup X)$ for $i\ge 2$. As any vertex or edge that is not in~$G[Y]$ lies in~$G[X]$, this means that ${\bigcup_i G[A_i] = G}$ remains unchanged.
\end{proof}

The following elementary lemma provides the link between our $S$-trees and \bd{}s as defined by Robertson and Seymour~\cite{GMX}:

\begin{LEM}\label{bwd-Stree}
For every integer $k \ge 3$,\/
   \footnote{See the remark after Theorem~\ref{TangleThm}.}
   our graph $G$ has branch-width less than~$k$ if and only if $G$ has an $S_k$-tree over~$\F^*$.
\end{LEM}

\begin{proof}
  If $\abs{E(G)}\le 1$, then the branch-width is $0$ by definition, and $G$ has an $S_k$-tree over~$\F^*$ with two nodes and a single edge mapped to~$(V,V)$ both ways. We now assume that $G$ has at least $2$ edges.
  \COMMENT{}

  Let us prove the forward implication first. We may assume that $G$ has no isolated vertices, because we can easily add a leaf in an $S_k$-tree corresponding to an isolated vertex.
  \COMMENT{}

  Suppose $(T,L)$ is a \bd{} of width~$<k$. For each edge $e=st$ of $T$, let $T_s$ and $T_t$ be the components of $T-e$ containing $s$ and~$t$, respectively. Let $A_{s,t}$ and $B_{s,t}$ be the sets of vertices incident with an edge in $L^{-1}(V(T_s))$ and $L^{-1}(V(T_t))$, respectively, except that if $A_{s,t}$ contains only two vertices we always put both these also in~$B_{s,t}$ (and similarly vice versa).
   \COMMENT{}
   Note that $B_{s,t} = A_{t,s}$.

  For all adjacent nodes $s, t\in T$ let $\alpha(s,t) := (A_{s,t},B_{s,t})$. Since $G$ has no isolated vertices these $\alpha(s,t)$ are separations, and since $(T,L)$ has width~$<k$ they lie in~$\vS_k$. For each internal node $t$ of $T$ and its three neighbours $s_1,s_2,s_3$, every edge of $G$ has both ends in one of the~$G[A_{s_i,t}]$, so
 $${\alpha(\vec F_t) =\{\alpha(s_1,t),\alpha(s_2,t),\alpha(s_3,t)\}\in \F}.$$
 As $A_{s_i,t}\subseteq A_{t,s_j} = B_{s_j,t}$ for all $i\ne j$, the set $\alpha(\vec F_t)$ is a star. For leaves $t$ of~$T$, the associated star $\alpha(\vec F_t)$ has the form $\{(V,A)\}$ with $|A|=2$,
   \COMMENT{}
   which is in $\F^*$ since $k\ge 3$. This proves that $(T,\alpha)$ is an $S_k$-tree over~$\F^*$.

  Now let us prove the converse. We may again assume that $G$ has no isolated vertex.
  \COMMENT{}
  Let $(T,\alpha)$ be an $S_k$-tree over~$\F^*$. For each edge $e$ of $G$, let us orient the edges $st$ of $T$ towards $t$ whenever $\alpha(s,t)=(A,B)$ is such that $B$ contains both ends of~$e$. If $e$ has its ends in~$A\cap B$, we choose an arbitrary orientation of~$st$. As $T$ has fewer edges then nodes, there exists a node $t=:L(e)$ such that every edge at~$t$ is oriented towards~$t$.

  Let us choose an $S_k$-tree $(T,\alpha)$ and $L\colon E\to V(T)$ so that the number of leaves in $L(E)$ is maximized, and subject to this with $\abs{V(T)}$ minimum. We claim that, for every edge $e$ of~$G$, the node $t=L(e)$ is a leaf of~$T$. Indeed, if not, let us extend~$T$ to make $L(e)$ a leaf. If $t$ has degree $2$, we attach a new leaf~$t'$ to~$t$ and put $\alpha(t',t)=(V(e),V)$ and $L(e)=t'$, where $V(e)$ denotes the set of ends of~$e$.
If $t$ has degree~$3$ then, by definition of~$\F$, there is a neighbour $t'$ of $t$ such that $e\in G[A]$ for $(A,B) = \alpha(t',t)$. As $t=L(e)$, this means that $e$ has both ends in~$A\cap B$. Subdivide the edge~$tt'$, attach a leaf $t^*$ to the subdividing vertex~$t''$, put $\alpha(t',t'')=\alpha(t'',t)=(A,B)$
   \COMMENT{}
   and $\alpha(t^*,t'')=(V(e),V)$,
   \COMMENT{}
   and let~$L(e)=t^*$. In both cases, $(T,\alpha)$ is still an $S_k$-tree over $\F^*$.
   \COMMENT{}

In the same way one can show that $L$ is injective. Indeed, if ${L(e') = t = L(e'')}$ for distinct $e',e''\in E$, we could increase the number of leaves in~$L(E)$ by joining two new leaves $t',t''$ to the current leaf~$t$, letting $\alpha(t',t)=(V(e'),V)$ and $\alpha(t'',t)=(V(e''),V)$, and redefine $L(e')$ as~$t'$ and $L(e'')$ as~$t''$.

By the minimality of~$\abs{V(T)}$, every leaf of $T$ is in~$L(E)$, since we could otherwise delete it. Finally, no node $t$ of $T$ has degree~2, since contracting an edge at~$t$ while keeping $\alpha$ unchanged on the remaining edges would leave an $S_k$-tree over~$\F^*$. (Here we use that $G$ has no isolated vertices, and that $L(e)\ne t$ for every edge $e$ of~$G$.)
   \COMMENT{}

Hence $L$~is a bijection from~$E$ to the set of leaves of~$T$, and $T$ is a ternary tree. Thus, $(T,L)$ is a \bd{} of~$G$, clearly of width less than~$k$.
\end{proof}

We can now derive, and extend, the Robertson-Seymour~\cite{GMX} duality theorem for tangles and branch-width:

\begin{THM}\label{TangleThm}
The following assertions are equivalent for finite graphs $G\ne\emptyset$ and~${k>0}\!:$
\vskip-6pt\vskip0pt
\begin{enumerate}[\rm(i)]\itemsep=0pt
\item $G$ has a tangle of order~$k$.
\item $G$ has an $\F$-tangle of $S_k$.
\item $G$ has an $\F^*$-tangle of $S_k$.
\item $G$ has no $S_k$-tree over $\F^*$.
\item $G$ has branch-width at least~$k$, or $k\le 2$ and $G$ is a disjoint union of stars and isolated vertices and has at least one edge.
   \COMMENT{}
\end{enumerate}
\end{THM}

\begin{proof}
   If $k=1$, then all statements are true. If $k=2$, they are all true if $G$ has an edge, and all false if not. Assume now that $k\ge 3$.

(i)$\leftrightarrow$(ii) follows from the definition of a tangle (as earlier) and our observation that they are consistent.
   \COMMENT{}

(ii)$\to$(iii) is trivial; the converse is Lemma~\ref{F*toF}.

(iii)$\leftrightarrow$(iv) is an application of Theorem~\ref{thm:strong}.

(iv)$\leftrightarrow$(v) is Lemma~\ref{bwd-Stree}.
\end{proof}

The exception in (v) for $k\le 2$ is due to a quirk in the notion of branch-width, which results from its emphasis on separating individual edges. The branch-width of all nontrivial trees other than stars is~2, but it is 1 for stars~$K_{1,n}$. For a clean duality theorem (even one just in the context of~\cite{GMX}) it should be~2 also for stars: every graph with at least one edge has a tangle of order~$2$, because we can orient all separations in~$S_2$ towards a fixed edge. Similarly, the branch-width of a disjoint union of edges is~0, but its tangle number is~2.
   \COMMENT{}

\subsection{Tree-width and brambles of graphs}\label{subsec:twd}

We now apply our strong duality theorem to obtain a new duality theorem for tree-width in graphs. Its witnesses for large tree-width will be orientations of~$S_k$, like tangles, and thus different from brambles (or `screens'), the dual objects in the  classical tree-width duality theorem of Seymour and Thomas~\cite{ST1993GraphSearching}.

This latter theorem, which ours easily implies, says that a finite graph either has a \td\ of width less than~$k-1$ or a bramble of order at least~$k$, but not both. The original proof of this theorem is as mysterious as the result is beautiful. The shortest known proof is given in~\cite{DiestelBook10noEE} (where we refer the reader also for definitions), but it is hardly less mysterious. A~more natural, if slightly longer, proof was given recently by Mazoit~\cite{MazoitTWduality}. The proof via our strong duality theorem, as outlined below, is certainly not shorter (all told), but it seems to be the simplest available so far.
   \footnote{For example, we do not need Menger's theorem, as all the other proofs do.}

Consider a finite graph $G = (V,E)$ with the set of vertex separations $S_k$ of order less than some integer~$k>0$, as defined at the start of Section~\ref{sec:appl}.
   \COMMENT{}
   Let
 $$\textstyle \F_k := \big\{\, \sigma\sub \vS_k \mid \sigma = \{(A_i,B_i):i=0,\ldots,n\} \text{ is a star with } \big|\bigcap_{i=0}^n B_i\big|< k\,\big\}. $$

$\F_k$ is clearly standard; in fact, it forces all small separations in~$\vS_k$, those of the form~$(A,V)$. We have also seen that $\vS_k$ is separable (Lemma~\ref{lem:separable}). To apply Theorem~\ref{thm:strong} we thus only need the following lemma (cf.~Lemma~\ref{lem:Fsep})~-- whose proof contains the only bit of magic now left in tree-width duality:

\begin{LEM}\label{lem:twd-shiftable}
  $\F_k$ is closed under shifting.
\end{LEM}

\begin{proof}
  Consider a separation $\vso=(X,Y)\in\vS_k =: \vS$ linked to some $\vr\in\vS_k$ not forced by~$\F_k$. Let
 $$\sigma = \big\{(A_i,B_i):i=0,\ldots,n\big\}\sub {\vSr}\sm\{\rv\}$$
 be a star in~$\F_k$ with $\vr\le (A_0,B_0)$.
   \COMMENT{}
   Then
\begin{equation}\label{eq:S1}
   \vr\le (A_0,B_0)\le (B_i,A_i) \text{ for all }i\ge 1.
\end{equation}
  We have to show that
 $$\sigma' = \big\{(A'_i,B'_i): i=0,\dots,n \big\}\in \F_k$$
  for $(A'_i,B'_i) := f\shift(\!\vr)(\vso) (A_i,B_i)$.

\goodbreak

From Lemma~\ref{lem:shifting} we know that $\sigma'$ is a star. Since $(X,Y)$ is linked to~$\vr$,
   \COMMENT{}
   we have $\sigma'\sub \vS_k$ by~\eqref{eq:S1}.
   \COMMENT{}
   It remains to show that $\big|\bigcap_{i=0}^n B'_i\big| < k$. The trick will be to rewrite this intersection as the intersection of the two sides of a suitable separation that we know to be in~$S_k$.
   \COMMENT{}

By~\eqref{eq:S1} we have $(A'_0,B'_0) = (A_0\cup X,B_0\cap Y)$, while $(A'_i,B'_i) = (A_i\cap Y,B_i\cup X)$ for $i\ge 1$.
  Since the $(A_i,B_i)$ are separations, i.e.\ in~$\vU$,
  so is $\big(\bigcap_{i=1}^n  B_i,\bigcup_{i=1}^n A_i\big)$.
  As trivially $(V,B_0)\in\vU$, this implies that, for $B^*:= \bigcap_{i=1}^n B_i$, also
    \COMMENT{}
  $$\Big(\bigcap_{i=1}^n B_i \cap V\,,\, \bigcup_{i=1}^n A_i\cup B_0\Big) \specrel={\eqref{eq:S1}} (B^*,B_0) \in\,\vU\,.$$
Since $\sigma\in\F_k$ we have $\abs{B^*,B_0} = \big|\bigcap_{i=0}^n B_i\big| < k$, so $(B^*,B_0)\in \vS_k$ (Fig.~\ref{fig:shiftingTDs}).
   \footnote{The~$A_i$, of course, are `more disjoint' than they appear in the figure.}
 As also $\vr\le (B^*,B_0)$ by~\eqref{eq:S1},
   \COMMENT{}
   the fact that $(X,Y)$ is linked to~$\vr$
   \COMMENT{}
  therefore implies that $(B^*\cup X, B_0\cap Y)\in \vS_k$. But then
 $$\Big|\bigcap_{i=0}^n B'_i\Big| = \Big|(B_0\cap Y) \cap \bigcap_{i=1}^n (B_i\cup X)\Big| = \big| B_0\cap Y, B^*\cup X\big| < k\,, $$
which means that $\sigma'\in\F_k$.
   \end{proof}

    \begin{figure}[htpb]
     \centering
   	  \includegraphics{ShiftingTDs.pdf}
   	  \caption{Shifting the separation $(B^*,B_0)$}
      \label{fig:shiftingTDs}
    \end{figure}

What remains now is just easy translation work between our terminology and the terms in which tree-width duality is traditionally cast:

\begin{LEM}\label{lem:twd-tree}
  $G$ has an $S_k$-tree $(T,\alpha)$ over~$\F_k$ if and only if it has a \td\ $(T,\V)$ of width less than~$k-1$.
\end{LEM}

\begin{proof}
Given any $S$-tree $(T,\alpha)$ of~$G$ over a set $\F$ of stars, let $\V = (V_t)_{t\in T}$ be defined by letting
\begin{equation}\label{Vt}
 V_t = \bigcap\big\{\, B : (A,B) = \alpha(s,t),\ st\in E(T)\big\}.
\end{equation}
It is easy to check~\cite{confing} that $(T,\V)$ is a \td\ of~$G$ with adhesion sets $V_t\cap V_{t'} = A\cap B$ whenever $(A,B) = \alpha(t,t')$. If $S=S_k$ and $\F=\F_k$ as earlier, we have $|V_t| < k$ at all $t\in T$,
   \COMMENT{}
   so $(T,\V)$ has width less than~$k-1$.

Conversely, given a \td\ $(T,\V)$ with $\V = (V_t)_{t\in T}$, say, define $\alpha\colon\vec E(T)\to \vS_k$ as follows. We may assume that $T$ has at least two nodes: if it has only one, $t$~say, we add another, $t'$, with $V_{t'}=V_t=V$. Given $t_1 t_2\in E(T)$, let $T_i$ be the component of $T-t_1 t_2$ containing~$t_i$, and put $U_i := \bigcup_{t\in V(T_i)} V_t$ ($i=1,2$). Then let $\alpha(t_1, t_2):= (U_1, U_2)$. One easily checks~\cite{DiestelBook10noEE} that $U_1\cap U_2 = V_{t_1}\cap V_{t_2}$, so $\alpha$ takes its values in~$\vS_k$ if $(T,\V)$ has width~$<k-1$. Moreover, every part $V_t$ satisfies~\eqref{Vt}, so if $(T,\V)$ has width $<k-1$ then $(T,\alpha)$ is over~$\F_k$.
\end{proof}

The translation between orientations of~$S_k$ and brambles in a graph $G$ is more interesting. Before the notion of a bramble was introduced in~\cite{ST1993GraphSearching} (under the name of `screen'), Robertson and Seymour had looked for an object dual to small tree-width that was more akin to our $\F_k$-tangles: maps $\beta$ assigning to every set $X$ of fewer than $k$ vertices one component of~$G-X$. The question was how to make these choices consistent, so that they would define a `highly connected substructure' dual to small tree-width. The obvious consistency requirement, that $\beta(Y)\sub \beta(X)$ whenever $X\sub Y$, is easily seen to be too weak,
   \COMMENT{}
   while asking that $\beta(X)\cap \beta(Y)\ne\emptyset$ for all~$X,Y$ turned out to be too strong. In~\cite{ST1993GraphSearching}, Seymour and Thomas then found a requirement that worked: that any two such sets, $\beta(X)$ and~$\beta(Y)$, should \emph{touch}: that either they share a vertex or $G$ has an edge between them. Such maps $\beta$ are now called \emph{havens}, and it is easy to show that $G$ admits a haven of \emph{order~$k$} (one defined on all sets $X$ of fewer than $k$ vertices) if and only if $G$ has a bramble of order at least~$k$.

The notion of `touching' was perhaps elusive because it appeals directly to the structure of~$G$, its edges: it is not phrased purely in terms of set containment. It turns out, however, that it can be captured in such terms after all, as the consistency of orientations of~$S_k$ (see Figure~\ref{fig:touch}):

\begin{LEM}\label{BrambleTranslation}
  $G$ has a bramble of order at least $k$ if and only if $G$ has an $\F_k$-tangle of~$S_k$.
\end{LEM}

\begin{proof}
  Let $\B$ be a bramble of order at least $k$. For every $\{A,B\}\in S_k$, since $A\cap B$ is too small to cover~$\B$ but every two sets in $\B$ touch and are connected, exactly one of the sets $A\sm B$ and $B\sm A$ contains an element of~$\B$. Thus,
  \[O=\{\, (A,B)\in \vS_k : B\sm A\text{ contains an element of } \B\,\}\]
  is an orientation of~$S_k$, which for the same reason is clearly consistent.
   \COMMENT{}

  To show that $O$ avoids $\F_k$, let $\sigma = \{(A_1,B_1),\ldots,(A_n,B_n)\}\in \F_k$ be given. Then $\big|\bigcap_{i=1}^n B_i\big|<k$, so some $C\in\B$ avoids this set and hence lies in the union of the sets $A_i\sm B_i$. But these sets are disjoint, since $\sigma$ is a star. Hence $C$ lies in one of them, $A_1\sm B_1$ say, putting $(B_1,A_1)$ in~$O$. But then $(A_1,B_1)\notin O$, so $\sigma\not\sub O$ as claimed.

  Conversely, let $O$ be an $\F_k$-tangle of~$S_k$. We shall define a bramble~$\B$ containing for every set $X$ of fewer than $k$ vertices exactly one component of~$G-X$, and no other sets. Such a bramble will have order at least~$k$, since no such set $X$ covers it.

Given such a set~$X$, note first that $X\ne V$. For if $|V|<k$, then the trivial oriented separations of~$G$ form a star in~$\F_k$; since they must be contained in any consistent orientation of~$S_k$, there cannot be an $\F_k$-tangle in~$G$. Let $C_1,\ldots,C_n$ be the vertex sets of the components of~$G-X$. Consider the separations $(A_i,B_i)$ with $A_i = C_i\cup N(C_i)$ and $B_i = V\sm C_i$. Since
 $$\sigma_X := \{\,(A_i,B_i) \mid\, i=1,\dots,n\,\}$$
 is a star in~$\F_k$, not all the $(A_i,B_i)$ lie in~$O$. So $(B_i,A_i)\in O$ for some~$i$, and since $O$ is consistent this $i$ is unique. Let us make $C_i$ an element of~$\B$.

It remains to show that every two sets in~$\B$ touch. Given $C,C'\in\B$, there are sets $X$ and $X'$ such that $\sigma_X$ contains a separation $(A,B)$ with $A = C\cup N(C)$ and $(B,A)\in O$, and likewise for~$C'$. If $C$ and~$C'$ do not touch, then $C'\sub B\sm A$ and hence $A'\sub B$ (Fig.~\ref{fig:touch}), and similarly $A\sub B'$. Hence $(A,B)\le (B',A')\in O$ but also $(B,A)\in O$, contradicting the consistency of~$O$.
   \end{proof}

   \begin{figure}[htpb]
\centering
   	  \includegraphics{touch.pdf}
   	  \caption{If $C,C'$ do not touch, then $(B,A)$ and $(B',A')$ are inconsistent.}
   \label{fig:touch}
   \end{figure}

We can now prove, and extend, the tree-width duality theorem of Seymour and Thomas~\cite{ST1993GraphSearching}:

\begin{THM}\label{BrambleThm}
The following assertions are equivalent for finite graphs $G\ne\emptyset$ and~${k>0}\!:$

\begin{enumerate}[\rm(i)]\itemsep=0pt
\item $G$ has a bramble of order at least~$k$.
\item $G$ has an $\F_k$-tangle of~$S_k$.
\item $G$ has no $S_k$-tree over~$\F_k$.
\item $G$ has tree-width at least~$k-1$.
\end{enumerate}
\end{THM}

\begin{proof}
(i)$\leftrightarrow$(ii) is Lemma~\ref{BrambleTranslation}.

(ii)$\leftrightarrow$(iii) holds by Lemma~\ref{lem:twd-shiftable} and Theorem~\ref{thm:strong}.

(iii)$\leftrightarrow$(iv) is Lemma~\ref{lem:twd-tree}.
\end{proof}

\subsection{Path-width and blockages of graphs}\label{subsec:pathwidth}

A \emph{\pd} of a graph $G$ is a \td\ of $G$ whose decomposition tree is a path. The \emph{path-width} of~$G$ is the least width of such a \td. Since the $S_k$-trees in Theorem~\ref{BrambleThm} are just another description of \td s of width~$<k-1$, its equivalence of (i), (ii) and~(iii) immediately yields a duality theorem for path-width if we replace $\F_k$ with
 $$\textstyle \F_k^{(2)} := \big\{\, \sigma\sub \vS_k \mid \sigma = \{(A_1,B_1),(A_2,B_2)\} \text{ is a star with } \big|B_1\cap B_2\big|< k\,\big\},$$
 its subset of stars of order at most~2.
   \COMMENT{}

Instead of the brambles in Theorem~\ref{BrambleThm}\,(i), Bienstock, Robertson, Seymour and Thomas~\cite{QuicklyExcludingForest} propose a more tangle-like kind of dense object dual to path-width, which they call `blockages'. They show that $G$ has path-width at least $k-1$ if and only it contains a blockage of order~$k-1$ (see below for definitions).
   \footnote{They go on to show that any graph with a blockage of order~$k-1$, and hence every graph of path-width at least~$k-1$, contains every forest of order~$k$ as a minor~-- a corollary perhaps better known than their path-width duality theorem as such.}
   In this section we deduce their result from our strong duality theorem.

Given a set $X$ of vertices in $G=(V,E)$, let us write $\partial(X)$ for the set of vertices in $X$ that have a neighbour outside~$X$. A \emph{blockage of order $k-1$}, according to~\cite{QuicklyExcludingForest}, is a collection $\B$ of sets $X\sub V$ such that
\begin{enumerate}[(B1)]\itemsep=0pt
\item $\abs{\partial(X)} < k$ for all $X\in\B$;
\item $X'\in\B$ whenever $X'\subseteq X\in\B$ and $\abs{\partial(X')} < k$;
\item for every $\{X_1,X_2\}\in S_k$, exactly one of $X_1$ and $X_2$ lies in~$\B$.
\end{enumerate}

To deduce the duality theorem of~\cite{QuicklyExcludingForest} from our strong duality theorem, we just need to translate blockages into orientations of~$S_k$:
   \COMMENT{}

\begin{THM}
The following assertions are equivalent for finite graphs $G\ne\emptyset$ and~${k>0}\!:$

  \begin{enumerate}[\rm(i)]\itemsep=0pt
  \item $G$ has a blockage of order $k-1$.
  \item $G$ has an $\F_k^{(2)}$-tangle of~$S_k$.
  \item $G$ has no  $S_k$-tree over $\F_k^{(2)}$.
  \item $G$ has path-width at least $k-1$.
  \end{enumerate}

\end{THM}

\begin{proof}
Since $\F_k^{(2)}$ is just the restriction of the $\F_k$ from Section~\ref{subsec:twd} to stars with at most two separations, it is closed under shifting by Lemma~\ref{lem:twd-shiftable}. By Lemmas \ref{lem:separable} and~\ref{lem:Fsep} this implies that $\vS_k$ is $\F_k^{(2)}$-separable. Theorem~\ref{thm:strong}, therefore, yields the equivalence of (ii) and~(iii), which is equivalent to~(iv) by Lemma~\ref{lem:twd-tree}.
   \COMMENT{}

(i)$\to$(ii): Suppose that $G$ has a blockage~$\B$ of order $k-1$. By (B2) and (B3),
  \[ O=\{\,(X,Y)\in \vS_k: X\in \B\,\}\]
  is a consistent orientation of~$S_k$.

For a proof that $O$ avoids every singleton star $\{(A,X)\}\in\F_k^{(2)}$ it suffices to show that $\B$ contains every set~$X$ of order~$<k$: then $(X,A)\in O$ and hence $(A,X)\notin O$. To show that $X\in\B$, consider the separation $\{X,V\}\in S_k$. If $V\in\B$, then also $X\in\B$ by~(B2), contradicting~(B3). Hence $V\notin\B$, and thus $X\in\B$ by~(B3).

To complete the proof that $O$ avoids~$\F_k^{(2)}$ consider ${\{(A_1,B_1),(A_2,B_2)\}\in \F_k^{(2)}}$ with $(A_1,B_1)\neq (A_2,B_2)$, and suppose that $(A_1,B_1)\in O$. Since $\{(A_1,B_1),(A_2,B_2)\}$ is a star,
   \COMMENT{}
   $\{B_1,B_2\}$ is a separation. As $|B_1\cap B_2|<k$ by definition of~$\F_k^{(2)}$, it lies in~$S_k$. Applying (B3) three times, we deduce from our assumption of $A_1\in \B$ that $B_1\notin \B$, and hence $B_2\in\B$, and hence $A_2\notin \B$. Thus, $(A_2,B_2)\notin O$.

(ii)$\to$(i): Let $O$ be an $\F_k^{(2)}$-tangle of~${S}_{k}$. We claim that
 $$\B := \{\, X : (X,Y)\in O\,\}$$
is a blockage of order $k-1$. Clearly, $\B$ satisfies (B1).

Given $\{X_1,X_2\}\in S_k$ as in~(B3),
   \COMMENT{}
   assume that $(X_1,X_2)\in O$. Then $X_1\in \B$. If also $X_2\in\B$, there exists $Y_2$ such that $(X_2,Y_2)\in O$. Then $\{X_1\cap Y_2,X_2\}$ is still a separation of~$V$,
   \COMMENT{}
   and clearly in~$S_k$. As $(X_1\cap Y_2,X_2)\le (X_1,X_2)\in O$ and $O$ is consistent, we have $(X_1\cap Y_2,X_2)\in O$. Then $\{(X_1\cap Y_2,X_2),(X_2,Y_2)\}$ is a star in $\F_k^{(2)}$, contradicting our assumption.

Given $X'\sub X\in\B$ as in~(B2), with $(X,Y)\in O$ say,
   \COMMENT{}
   let $Y':= \partial(X')\cup (V\sm X')$ and $Z := \partial(X)\cup (V\sm X)$. Then $Z\sub Y$ and hence $|X\cap Z|\le |X\cap Y| < k$, so $\{X,Z\}\in S_k$. By (B3)
   \COMMENT{}
   we have $Z\notin \B$ and hence $(Z,X)\notin O$, so $(X,Z)\in O$.
   \COMMENT{}
   Since $O$ is consistent and $\vS_k\owns (X',Y')\le (X,Z)$,
   \COMMENT{}
   we thus obtain $(X',Y')\in O$ and hence $X'\in\B$, as desired.
\end{proof}

\subsection{Branch-width and tangles for submodular order functions: carving width, rank width, and matroid tangles}\label{subsec:bwdsubmodular}

The concepts of branch-width and tangles were introduced by Robertson and Seymour~\cite{GMX} not only for graphs but more generally for hypergraphs. As the order of an oriented separation $(A,B)$ they already considered, instead of just~$|A\cap B |$, arbitrary symmetric submodular order functions~$\ord(A,B)$ and proved the relevant lemmas more generally for these. Geelen, Gerards, Robertson, and Whittle~\cite{BranchDecMatroids} applied this explicitly to the submodular connectivity function in matroids.

Our aim in this section is to derive from Theorem~\ref{thm:strong} a duality theorem for branch-width and tangles in arbitrary separation universes with an order function, as introduced at the start of Section~\ref{sec:appl}. This will imply the above branch-width duality theorems for hypergraphs and matroids,
   \COMMENT{}
   as well as their cousins for carving width~\cite{ratcatcher}
   \COMMENT{}
   and rank-width of graphs~\cite{rankwidth}.
   \COMMENT{}

Let $\vU$ be any universe of separations of some set~$E$
   \COMMENT{}
   of at least two elements,
   \COMMENT{}
   with an order function $(A,B)\mapsto \ord(A,B)$. Given $k>0$, call an orientation of
 $$S_k = \{\,\{A,B\}\in U: \ord(A,B)<k\,\}$$
   a \emph{tangle of order~$k$} if it avoids
\[
\F = \big\{
  \{(A_1,B_1),(A_2,B_2),(A_3,B_3)\}\subseteq \vS_k:  A_1\cup A_2\cup A_3 = E
\,\big\}.
\]
 Here, $(A_1,B_1), (A_2,B_2), (A_3,B_3)$ need not be distinct; in particular, $\F$~is standard
   \COMMENT{}
   and tangles are consistent.
   \COMMENT{}
   This extends the existing notions of tangles for hypergraphs and matroids, with their edge set or ground set as~$E$, partitions as separations, and the appropriate order functions.
   \COMMENT{}

Let $\F^*\sub\F$ be the set of stars in~$\F$.
   \COMMENT{}
   As in Lemma~\ref{TanglesShiftable}, it is easy to prove that $\F^*$ is closed under shifting. We have the following analogue of Lemma~\ref{F*toF}:

\begin{LEM}\label{lem:F*toFsub}
  Every consistent $\F^*$-avoiding orientation of~$S_k$ avoids~$\F$.\qed
\end{LEM}

By Lemmas~\ref{lem:separable} and~\ref{lem:F*toFsub}, Theorem~\ref{thm:strong} now specializes as follows:

\begin{THM}
  Given a separation universe $\vU$ with an order function, and~${k>0}$, the following assertions are equivalent:
\vskip-3pt\vskip0pt
  \begin{enumerate}[\rm (i)]\itemsep=0pt
  \item $\vU$ has a tangle of order~$k$.
     \COMMENT{}
  \item $\vU$ has an $\F^*$-tangle of~$S_k$.
  \item $\vU$ has no $\vS_k$-tree over~$\F^*$.\qed
  \end{enumerate}
\end{THM}

As in the proof of Lemma~\ref{bwd-Stree} one can check that, in a hypergraph or matroid, (iii)~is equivalent to saying that its branch-width is at least~$k$.

\subsection{Matroid tree-width}\label{subsec:matroid}
Hlin{\v e}n{\'y} and Whittle~\cite{HlinenyWhittle,HlinenyWhittleErrata} generalized the notion of tree-width from graphs to matroids.
   \footnote{In our matroid terminology we follow Oxley~\cite{OxleyBook}.}
   Our aim in this section is to specialize our strong duality theorem to a duality theorem for tree-width in matroids.
   \COMMENT{}

Let $M=(E,I)$ be a matroid with rank function $r$. Its \emph{connectivity function} is defined as
 $$\lambda(X) := r(X)+r(E\sm X)-r(M).$$
 We consider the universe $\vU$ of all bipartitions $(X,Y)$ of~$E$. Since
 $$\ord(X,Y):= \lambda(X) = \lambda(Y)$$
 is non-negative, submodular and symmetric, it is an order function on~$\vU$.

A \emph{\td} of~$M$ is a pair~$(T,\tau)$, where $T$ is a tree and ${\tau\colon E\to V(T)}$ is any map.
Let $t$ be a node of~$T$, and let $T_1,\ldots,T_d$ be the components of $T-t$. Then the \emph{width} of~$t$ is the number
   \COMMENT{}
\[ \sum_{i=1}^d r(E\sm F_i) - (d-1)\, r(M),\]
where $F_i=f^{-1}(V(T_i))$. (If $t$ is the only node of~$T$, we let its width be~$r(M)$.) The \emph{width} of $(T,\tau)$ is the maximum width of the nodes of~$T$. The \emph{tree-width} of~$M$ is the minimum width over all \td{}s of~$M$.

Matroid tree-width was designed so as to generalize the tree-width of graphs:

\begin{THM}[Hlin{\v e}n{\'y} and Whittle~\cite{HlinenyWhittle,HlinenyWhittleErrata}]
  The tree-width of a finite graph containing at least one edge equals the tree-width of its cycle matroid.
\end{THM}

In order to specialize Theorem~\ref{thm:strong} to a duality theorem for tree-width in matroids, we again consider for $k>0$ the set
 $$S_k = \{\,\{A,B\}\in U: \ord(A,B)<k\,\};$$
 then $\vS_k$ is separable by Lemma~\ref{lem:separable}. For stars $\sigma = \{(A_i,B_i) :i = 0,\ldots,n\}\sub\vU$ we write
 $$\starorder\sigma := \sum_{i=0}^n r(B_i) - n\, r(M)\,.$$
We consider
 $$\F_k := \big\{\, \sigma\sub \vU : \sigma \text{ is a star with } \starorder\sigma <k\,\big\}.$$
   \COMMENT{}

Clearly, the singleton stars $\{(A,B)\}$ in~$\F_k$ are precisely those with $r(B) < k$.
   \COMMENT{}
   We remark that requiring $\sigma\sub \vS_k$ in the definition of~$\F_k$ would not spare us a proof of the following lemma, which we shall need in the proof of Lemma~\ref{lem:matroidTDs}.

\begin{LEM}\label{lem:matroidTW}
Every $\sigma\in\F_k$ is a subset of~$\vS_k$.
\end{LEM}

\begin{proof}
We show that every $A_i$ in a star $\sigma = \{(A_i,B_i):i=0,\ldots,n\}\sub\vU$ satisfies $\lambda(A_i)\le\starorder\sigma$; if $\sigma\in\F_k$, this implies that $\ord(A_i,B_i)<k$ as desired. Our proof will be for $i=0$; the other cases then follow by symmetry.

Since $\sigma$ is a star we have $A_i\sub B_j$ whenever $i\ne j$, and in particular $A_{i+1}\sub B_i^*:= B_1\cap\ldots\cap B_i$ for $i=1,\dots,n-1$.
   \COMMENT{}
   Hence $B_i^*\cup B_{i+1}\supe E$. Submodularity of the rank function now gives
   \COMMENT{}
\[
r(B_i^*)+r(B_{i+1})\ge r(B_i^*\cap B_{i+1}) + r(B_i^*\cup B_{i+1}) = r(B_{i+1}^*) + r(M)
\]
   \COMMENT{}
   for each $i=1,\ldots,n-1$. Summing these inequalities over $i=1,\ldots,n-1$, and noting that $B^*_1 = B_1$, yields
 $$r(B_1)+\ldots+r(B_n)\ge r(B_1\cap \ldots\cap B_n) + (n-1)\, r(M).$$
Using that $\sigma$ is a star and hence $A_0 \sub B_1\cap\ldots\cap B_n$, we deduce
\begin{align*} \starorder\sigma =
\sum_{i=0}^n r(B_i) - n\, r(M) &\ge r(B_0)+r(B_1\cap \ldots\cap B_n)-r(M)\\
 \noalign{\vskip-6pt}
   & \ge r(B_0)+r(A_0)-r(M)\\
 \noalign{\vskip3pt}
   & = \lambda(A_0).
\end{align*}
as desired.
\end{proof}

In order to apply Theorem~\ref{thm:strong}, we have to prove that $\vS_k$ is $\F_k$-separable:

\begin{LEM}
  $\vS_k$ is $\F_k$-separable.
\end{LEM}

\begin{proof}
Let $\vr,\rvdash\in\vS_k$ that are not forced by~$\F_k$ and satisfy $\vr\le\vrdash$ be given. Pick $(X,Y)\in\vS_k$ with $\vr\le (X,Y)\le\vrdash$ and $|X,Y|$ minimum.
   \COMMENT{}
   We claim that $(X,Y)$ is $\F_k$-linked to~$\vr$ and $(Y,X)$ is $\F_k$-linked to~$\rvdash$. By symmetry,
   \COMMENT{}
   it is enough to prove that $(X,Y)$ is $\F_k$-linked to~$\vr$.

The proof of Lemma~\ref{lem:separable} shows that $(X,Y)$ is linked to~$\vr$.
   \footnote{Technically, we do not need this fact at this point and could use Lemma~\ref{lem:matroidTW} to deduce it from the fact that all $\sigma'$ as below lie in~$\F_k$. But that seems heavy-handed.}
   \COMMENT{}
   To show that $(X,Y)$ is even $\F_k$-linked to~$\vr$, consider a star
 $$\sigma=\big\{(A_i,B_i):i=0,\ldots,n\big\}\sub \vSr\sm\{\rv\}$$
 in~$\F_k$ (where $\vS:=\vS_k$) with $\vr\le (A_0,B_0)$. Then
\begin{equation}\label{eq:S1matroid}
   \vr\le (A_0,B_0)\le (B_i,A_i) \text{ for all }i\ge 1.
\end{equation}
  We have to show that
 $$\sigma' = \big\{(A'_i,B'_i): i=0,\dots,n \big\}\in \F_k$$
  for $(A'_i,B'_i) := f\shift(\!\vr)(\vso) (A_i,B_i)$.

  From Lemma~\ref{lem:shifting} we know that $\sigma'$ is a star. Since $(X,Y)$ is linked to~$\vr$,
   \COMMENT{}
   we have $\sigma'\sub \vS_k$ by~\eqref{eq:S1matroid}.
   \COMMENT{}
   It remains to show that $\starorder{\sigma'} < k$. We show that, in fact,
 \begin{equation}\label{eq:ranksum}
  \big(\starorder{\sigma'}=\big)\quad  r(Y\cap B_0)+\sum_{i=1}^n r(X\cup B_i)- n\, r(M) \le\starorder\sigma\,;
 \end{equation}
 as $\starorder\sigma < k$ by our assumption that $\sigma\in\F_k$, this will complete the proof.

By submodulary of the rank function, we have
  \begin{align}\nonumber
    r(Y\cap B_0)+r(Y\cup B_0)&\le r(Y)+r(B_0)\\
    \nonumber
    \text{and}\quad r(X\cup B_i)+r(X\cap B_i)&\le r(X)+r(B_i)\quad \text{for }i = 1,\dots,n.
  \end{align}
 For our proof of~\eqref{eq:ranksum} we need to show that the sum of the first terms in these $n+1$ inequalities is at most the sum of the last terms.
   \COMMENT{}
   This will follow from these inequalities once we know that the sum of the second terms is at least the sum of the third terms. So let us prove this, i.e., that
 \begin{equation}\label{eq:ranknew}
 r(Y\cup B_0) + \sum_{i=1}^n r(X\cap B_i)\ge r(Y) + n\, r(X)\,.
 \end{equation}
 For $i=1,\dots,n$ let us abbreviate $A_i^* := A_1\cup\ldots\cup A_i$ and $B_i^* := B_1\cap\ldots\cap B_i$.

Since $\sigma$ is a star we have $A_i\sub B_j$ whenever $i\ne j$. Hence $A_n^*\subseteq B_0$, giving
  \begin{equation}
   r(Y\cup B_0)\ge r(Y\cup A_n^*),
    \label{eq:matroid1}
  \end{equation}
and $A_{i+1}\sub B_i^*$ for $i \ge 1$. Hence $B_i^*\cup B_{i+1}\supe E$. By submodularity, this implies
  \begin{align}\nonumber
r(X\cap B_i^*)+r(X\cap B_{i+1})&\ge r(X\cap (B^*_i\cap B_{i+1})) + r(X\cap (B_i^*\cup B_{i+1}))\\
    &= r(X\cap B_{i+1}^*) + r(X)\nonumber
  \end{align}
   for each $i=1,\ldots,n-1$. Summing this for $i=1,\ldots,n-1$, and recalling that $B^*_1 = B_1$, we obtain
   \COMMENT{}
 \begin{equation}\label{eq:matroid2}
 \sum_{i=1}^n r(X\cap B_i)\ge r(X\cap B_n^*) + (n-1)\, r(X)\,.
 \end{equation}

Since $\{X,Y\}$ and $\{B_n^*,A_n^*\}$ are bipartitions of~$E$, so is $\{X\cap B_n^*,Y\cup A_n^*\}$. Moreover, we have $\vr\le (X\cap B_n^*,Y\cup A_n^*)$ since $\vr\le (X,Y)$ and $\vr\le (B^*_n,A^*_n)$ by~\eqref{eq:S1matroid}, and we also have $(X\cap B_n^*,Y\cup A_n^*)\le (X,Y)\le\vrdash$. It would therefore contradict our choice of~$(X,Y)$ if we had $\ord(X\cap B_n^*,Y\cup A_n^*) < \ord(X,Y)$.
   \COMMENT{}
  Hence $\ord(X\cap B_n^*,Y\cup A_n^*) \ge \ord(X,Y)$, and therefore
    \COMMENT{}
  \begin{equation}
  r(X\cap B_n^*) + r(Y\cup A_n^*) \ge r(X)+r(Y).
  \label{eq:matroid3}
  \end{equation}
 Adding up inequalities~\eqref{eq:matroid1}, \eqref{eq:matroid2},~\eqref{eq:matroid3} we obtain~\eqref{eq:ranknew}, proving~\eqref{eq:ranksum}.
\end{proof}

\begin{LEM}\label{lem:matroidTDs}
  $M$ has an ${S}_k$-tree over $\F_k$ if and only if  it has tree-width~$<k$.
\end{LEM}

\begin{proof}
 For the forward implication, consider any $S_k$-tree $(T,\alpha)$ of~$M$. Given $e\in E$, orient every edge $st$ of~$T$, with $\alpha(s,t) = (A,B)$ say, towards~$t$ if $e\in B$, and let $\tau$ map $e$ to the unique sink of~$T$ in this orientation. Then $(T,\tau)$ is a \td\ of~$M$. If $(T,\alpha)$ is over $\F_k$, the decomposition is easily seen to have width less than~$k$.

Conversely, let $(T,\tau)$ be a \td\ of~$M$ of width~$<k$. If ${r(M)<k}$, then $\{(\emptyset,E)\}$ and $\{(E,\emptyset)\}$ are both singleton stars in~$\F_k$, so there is a 2-node $S_k$-tree over~$\F_k$. We may thus assume that $r(M)\ge k$, and so $T$ has at least two nodes. For each edge $e=st$ of~$T$, let $T_s$ and~$T_t$ be the components of $T-e$ containing $s$ and~$t$, respectively. Let
 $$\alpha(s,t) := \big(\tau^{-1}(T_s),\tau^{-1}(T_t)\big)\in\vU.$$
   Since every node $t$ has width less than~$k$, its associated star $\{\,\alpha(s,t) : st\in E(T)\}$ of separations is in~$\F_k$. By Lemma~\ref{lem:matroidTW} this implies that $\alpha(\vec E(T))\sub \vS_k$, so $(T,\alpha)$~is an $S_k$-tree over~$\F_k$.\looseness=-1
\end{proof}

Theorem~\ref{thm:strong} now yields the following duality theorem for matroid tree-width.

\begin{THM}
  Let $M$ be a matroid, and let $k>0$ be an integer. Then the following statements are equivalent:
  \begin{enumerate}[\rm (i)]\itemsep=0pt
  \item $M$ has tree-width at least $k$.
  \item $M$ has no $S_k$-tree over $\F_k$.
  \item $M$ has an $\F_k$-tangle of~$S_k$.

 \qed \end{enumerate}
\end{THM}

\subsection{Tree-decompositions of small adhesion}\label{subsec:adhesion}

As a case in point, let us illustrate the versatility of Theorem~\ref{thm:strong} by deducing a duality theorem for a new width parameter: one that bounds the width and the adhesion of a \td\ independently, that is, allows the first bound to be greater.

Recall that the \emph{adhesion} of a \td{} $(T,\V)$ of a  graph $G=(V,E)$ is the largest size of an attachment set, the number $\max_{st\in E(T)} \abs{V_{s}\cap V_t}$. (If $T$ has only one node~$t$, we set the adhesion to $\abs{V_t} = |V|$.) Trivially if a \td{} has width~$<k-1$, then it has an adhesion~$<k$.

The idea now is to have a duality theorem for graphs whose tree structures are the \td s of adhesion~$<k$ and width less than $w-1 \ge k-1$. For $w=k$ this should default to the usual duality between tree-width and havens or brambles, as discussed in Section~\ref{subsec:twd}.

Let $\vS_k$ be as defined at the beginning of Section~\ref{sec:appl}, with $\vU$ the uni\-verse of all oriented vertex separations of~$G$ equipped with the usual order function. Recall that $\vS_k$ is separable by Lemma~\ref{lem:separable}. Let
\[ \F^w_k=\big\{\sigma\subseteq \vS_k\mid \sigma=\{(A_i,B_i):i=0,\ldots,n\}\text{ is a star with $\textstyle\big\lvert\bigcap_{i=0}^n B_i\big\rvert<w$}\big\},\]
as done previously in Section~\ref{subsec:twd} for $w=k$.

\begin{LEM}\label{lem:twdadh-shitable}
  $S_k$ is $\F^w_k$-separable.
\end{LEM}

\begin{proof}
  Let $\vr,\rvdash\in\vS_k$ that are not forced by $\F^w_k$ and satisfy $\vr\le\vrdash$ be given. Pick $\vso = (X,Y)\in\vS_k$ with $\vr\le (X,Y)\le\vrdash$ and $|X,Y|$ minimum.
   \COMMENT{}
   We claim that $(X,Y)$ is $\F^w_k$-linked to~$\vr$ and $(Y,X)$ is $\F^w_k$-linked to~$\rvdash$. By symmetry,
   \COMMENT{}
   it is enough to prove that $(X,Y)$ is $\F^w_k$-linked to~$\vr$.

The proof of Lemma~\ref{lem:separable} shows that $(X,Y)$ is linked to~$\vr$. To show that $(X,Y)$ is even $\F^w_k$-linked to~$\vr$, consider a star
 $$\sigma=\big\{(A_i,B_i):i=0,\ldots,n\big\}\sub \vSr\sm\{\rv\}$$
 in~$\F^w_k$ (where $\vS:=\vS_k$) with $\vr\le (A_0,B_0)$. Then
\begin{equation}\label{eq:S2}
   \vr\le (A_0,B_0)\le (B_i,A_i) \text{ for all }i\ge 1.
\end{equation}
  We have to show that
 $$\sigma' = \big\{(A'_i,B'_i): i=0,\dots,n \big\}\in \F^w_k$$
  for $(A'_i,B'_i) := f\shift(\!\vr)(\vso) (A_i,B_i)$.

\goodbreak

From Lemma~\ref{lem:shifting} we know that $\sigma'$ is a star. Since $(X,Y)$ is linked to~$\vr$,
   \COMMENT{}
   we have $\sigma'\sub \vS_k$ by~\eqref{eq:S2}.
   \COMMENT{}
   It remains to show that $\big|\bigcap_{i=0}^n B'_i\big| < w$. As in Lem\-ma~\ref{lem:twd-shiftable}, we shall prove this by rewriting the intersection of all the~$B'_i$ as an intersection of the two sides of a suitable separation,
   \COMMENT{}
   and use submodularity and the choice of~$(X,Y)$ to show that this separation has order~$<w$.

By~\eqref{eq:S2} and the definition of~$f\shift(\!\vr)(\vso)$, we have $(A'_0,B'_0) = (A_0\cup X,B_0\cap Y)$, while $(A'_i,B'_i) = (A_i\cap Y,B_i\cup X)$ for $i\ge 1$.
  Since the $(A_i,B_i)$ are separations, i.e.\ in~$\vU$,
  so is $\big(\bigcap_{i=1}^n  B_i,\bigcup_{i=1}^n A_i\big)$.
  As trivially $(V,B_0)\in\vU$, this implies that, for $B^*:= \bigcap_{i=1}^n B_i$, also
    \COMMENT{}
  $$\Big(\bigcap_{i=1}^n B_i \cap V\,,\, \bigcup_{i=1}^n A_i\cup B_0\Big) \specrel={\eqref{eq:S2}} (B^*,B_0) \in\,\vU\,.$$
Note that
\begin{equation}\label{eq:B}
\ord(B^*,B_0) = \abs{B^*\cap B_0} = \big|\bigcap_{i=0}^n B_i\big| < w
\end{equation}
since $\sigma\in\F^w_k$.

As $\vr\le (X,Y)$, and also $\vr\le (B^*,B_0)$ by~\eqref{eq:S2}, we further have
 $$\vr\le (X\cap B^*, Y\cup B_0) \le (X,Y)\le\vrdash.$$
 Hence if $\ord(X\cap B^*, Y\cup B_0) < \ord(X,Y)$ then this would contradict our choice of~$(X,Y)$.
   \COMMENT{}
   Therefore $\ord(X\cap B^*, Y\cup B_0) \ge \ord(X,Y)$. As
 $$\ord(X\cap B^*,Y\cup B_0) + \ord(X\cup B^*, Y\cap B_0)\ \le\ \ord(X,Y)+\ord(B^*,B_0)$$
by submodularity, we deduce that
 $$\ord(X\cup B^*, Y\cap B_0)\ \le\ \ord(B^*,B_0)\ <\ w$$
by~\eqref{eq:B}. Hence
 $$\Big|\bigcap_{i=0}^n B'_i\,\Big| = \Big|(B_0\cap Y) \cap \bigcap_{i=1}^n (B_i\cup X)\Big| = \big| B_0\cap Y, B^*\cup X\big| < w\,, $$
which means that $\sigma'\in\F^w_k$ as desired.
\end{proof}

The following translation lemma is proved like Lemma~\ref{lem:twd-tree}:
   \COMMENT{}

\begin{LEM}
  $G$ has an $S_k$-tree over $\F^w_k$ if and only if it has a \td{} of width~$ < w-1$ and adhesion~$ < k$.
\end{LEM}

Theorem~\ref{thm:strong} and our two lemmas imply the following duality theorem:

\begin{THM}
  The following assertions are equivalent for all finite graphs $G\ne\emptyset$ and integers ${w\ge k>0\!:}$
   \vskip-3pt\vskip0pt
  \begin{enumerate}[\rm (i)]\itemsep=0pt
  \item $G$ has an $\F^w_k$-tangle of~$S_k$.
  \item $G$ has no $S_k$-tree over $\F^w_k$.
  \item $G$ has no \td{} of width~$<w-1$ and adhesion~$<k$.\qed
  \end{enumerate}
\end{THM}

\subsection{Weakly Submodular Partition Functions}\label{subsec:partitionsub}

Amini, Mazoit, Nisse and Thomass\'e~\cite{MazoitPartition}, and Lyaudet, Mazoit and Thomass\'e~\cite{MazoitPushing}, proposed a framework to unify duality theorems in graph minor theory which, unlike ours, is based exclusively on partitions. Their work, presented to us by Mazoit in the summer of 2013, inspired us to look for possible simplifications, for generalizations to separations that are not partitions, and for applications to tangle-like dense objects not covered by their framework. Our findings are presented in this paper and its sequel~\cite{DiestelOumDualityII}. Although our approach differs from theirs, we remain indebted to Mazoit and his coauthors for this inspiration.

Since the applications of our strong duality theorem include the applications of~\cite{MazoitPartition}, it may seem unnecessary to ask whether our result also implies theirs directly. However, for completeness we address this question now.
   \COMMENT{}

A~\emph{partition} of a finite set~$E$ is a set of disjoint subsets of~$E$, possibly empty, whose union is~$E$. We write $\P(E)$ for the set of all partitions of~$E$. In~\cite{MazoitPartition}, any function $\P(E)\to \mathbb{R}\cup\{\infty\}$ is called a \emph{partition function} of~$E$. We abbreviate $\psi(\{A_1,\dots,A_n\})$ to $\psi(A_1,\dots,A_n)$, but note that the partition remains unordered. A partition function $\psi$ is called \emph{weakly submodular} in~\cite{MazoitPartition} if, for every pair $(\A,\B)$ of partitions of~$E$ and every choice of $A_0\in\A$ and $B_0\in\B$, one of the following holds with $\A =: \{A_0,\ldots,A_n\}$ and $\B =: \{B_0,\ldots,B_m\}$:
\begin{enumerate}[(i)]
\item there exists a set $F$ such that $A_0\subseteq F\subseteq A_0\cup (E\sm B_0)$ and $\psi(A_0,\ldots,A_n)>\psi(F,A_1\sm F,\ldots,A_{n}\sm F)$;
\item $\psi(B_0,\ldots,B_m)\ge \psi\big(B_0\cup (E\sm A_0),B_1\cap A_0,\ldots,B_{m}\cap A_0\big)$.
\end{enumerate}

Let us translate this to our framework. Given $A\sub E$, let $\bar A:= E\sm A$. Then $\vU := \{ (A,\bar A) : A\sub E\}$ is a universe. Given a partition function~$\psi$ of~$E$, let\looseness=-1
 $$\vS_k = \big\{(A,\bar A)\in \vU :  \psi(A,\bar A) < k\big\}.$$
   \COMMENT{}
Every partition $\A = \{A_0,\ldots,A_n\}$ defines a star $\{(A_0,\bar A_0),\dots, (A_n,\bar A_n)\}\sub\vU$, which we denote by~$\sigma(\A)$. Let
\[\F_k := \big\{ \sigma(\A) : \A\in\P(E)\text{ and } \psi(\A) < k \big\}\cup \{\{(\bar X,X)\}: \abs{X}\le 1,~ \psi(\bar X, X)<k\}.\]
\COMMENT{}
 If all the stars in $\F_k$ are subsets of~$\vS_k$, we call $\psi$ \emph{monotone}. All the  weakly submodular partition functions used in~\cite{MazoitPartition} for applications are monotone, and we do not know whether any exist that are not.
   \COMMENT{}

\begin{LEM}\label{lem:weaksub-sep}
  If $\psi$ is weakly submodular, then $\vS_k$ is $\F_k$-separable.
\end{LEM}

\begin{proof}
  Let $\vS=\vS_k$. Let $\vr,\rvdash\in\vS$ that are not forced by~$\F_k$ and satisfy $\vr\le\vrdash$ be given. Pick $\vso = (X,Y)\in\vS$ with $\vr\le \vso\le\vrdash$ and $\psi(X,Y)$ minimum.
   We claim that $\vso$ is $\F_k$-linked to~$\vr$ and $\svo$ is $\F_k$-linked to~$\rvdash$. By symmetry, it is enough to prove that $\vso$ is $\F_k$-linked to~$\vr$.

  We first prove that $\vso$ is linked to $\vr$. Let $\vs=(A,B)\in \vSr\sm\{\rv\}$ be given. Since $\psi$ is weakly submodular, one of the following assertions holds:
   \COMMENT{}
  \begin{enumerate}[\rm (i)]\itemsep=0pt
  \item there exists $F$ such that $X\subseteq F\subseteq X\cup A$ and $\psi(X,Y)>\psi(F,\bar F)$;
     \COMMENT{}
  \item $\psi(B,A)\ge \psi(B\cup Y,A\cap X)$.
  \end{enumerate}
  Since $X\sub F\sub X\cup A\sub A$, we have $\vr\le (F,\bar F)\le \vrdash$. So (i) does not hold, by the choice of $(X,Y)$. So by (ii), $\vso\wedge\vs =(A\cap X,B\cup Y)\in \vS$. This proves that $\vso$ is linked to $\vr$.

  Now let us show that stars can be shifted. Let
  \[\sigma=\{(A_i,B_i):i=0,\ldots,n\}\]
  be a star in~$\F_k\cap {\vSr}$, with $(A_0,B_0)\ge \vr$.
  We have to show that
 \[\sigma' = \big\{(A'_i,B'_i): i=0,\dots,n \big\}\in \F_k\]
  for $(A'_i,B'_i) := f\shift(\!\vr)(\vso) (A_i,B_i)$.  Since $\vr\le (A_0,B_0)\le (B_i,A_i)$ for $i\ge 1$, we have
  $(A'_0,B'_0) = (A_0\cup X,B_0\cap Y)$, while $(A'_i,B'_i) = (A_i\cap Y,B_i\cup X)$ for $i\ge 1$.

 If $n=0$, then $\abs{B_0'}\le \abs{B_0}\le 1$ and so $\sigma'=\{(A_0',B_0')\}\in\F_k$.
 If $n\neq 0$, then $\psi(A_0,\ldots,A_n) < k$.
By the minimal choice of~$\vso=(X,Y)$, there exists no $F$ such that $X\subseteq F\subseteq X\cup A_0$ and $\psi(X,Y)>\psi(F,\bar F)$ (as earlier).
Applying the weak submodularity of $\psi$ with $(X,Y)$ and $(A_0,\ldots,A_n)$, we deduce that
\[\psi(A'_0,\dots,A'_n) = \psi(A_0\cup X,\ A_1\cap Y,\,\ldots\,,A_n\cap Y)\le \psi(A_0,\ldots,A_n) < k.\]
Thus, $\sigma'\in \F_k$.
\end{proof}

In~\cite{MazoitPartition}, a \emph{$k$-bramble} for a weakly submodular partition function~$\psi$ of~$E$ is a non-empty set $\B$ of pairwise intersecting subsets of~$E$ that contains an element from every partition $\A$ of $E$ with ${\psi(\A) < k}$. It is \emph{non-principal} if it contains no singleton set~$\{e\}$.
In our terminology, Amini et al.~\cite{MazoitPartition} prove that there exists a non-principal $k$-bramble for~$\psi$ if and only if there is no $S_k$-tree over~$\F_k$; they call this a `partitioning $k$-search tree'.

Now any $k$-bramble~$\B$ defines an orientation $O$ of~$S_k$: given $\{A,B\}\in S_k$ exactly one of $A,B$ must lie in~$\B$,
   \COMMENT{}
  and if $B$ does we put $(A,B)$ in~$O$. Clearly $O$ is consistent
   \COMMENT{}
   and avoids non-singleton stars in~$\F_k$, and if $\B$ is non-principal it avoids all singleton stars in $\F_k$. Conversely, given an orientation $O$ of~$S_k$, let ${\B := \{ B : (A,B)\in O\}}$. If $O$ is consistent, no two elements of~$\B$ are disjoint. If $O$ avoids singleton stars in~$\F_k$, then $\B$ is non-principal.
   \COMMENT{}
   And finally, if $\psi$ is monotone and $O$ avoids~$\F_k$, then $\B$ contains an element from every partition $\A=\{A_1,\dots, A_n\}$ of~$E$ with $\psi(\A) < k$: since $\sigma(\A)\in\F_k$ there is $(A_i,\bar A_i)\in \sigma(\A)\sm O$, which means that $(\bar A_i,A_i)\in O$
   \COMMENT{}
   and thus $A_i\in\B$.

Lemma~\ref{lem:weaksub-sep} and Theorem~\ref{thm:strong} thus imply the duality theorem of Amini et al.~\cite{MazoitPartition} for monotone weakly submodular partition functions:

\begin{THM}
  The following assertions are equivalent for all monotone weakly submodular partition functions $\psi$ of a finite set~$E$ and $k>0$:
  \begin{enumerate}[\rm (i)]\itemsep=0pt
  \item There exists a non-principal $k$-bramble for~$\psi$.
  \item $S_k$ has an $\F_k$-tangle.
  \item There exists no $S_k$-tree over $\F_k$.
  \item There exists no partitioning $k$-search tree.
  \end{enumerate}
\end{THM}
   \COMMENT{}

\subsection{Further applications}\label{subsec:further}

There are some obvious ways in which we can modify the sets $\F$ considered so far in this section to create new kinds of highly connected substructures and obtain associated duality theorems as corollaries of Theorem~\ref{thm:strong}. For example, we might strengthen the notion of a tangle by forbidding not just all the 3-sets of separations whose small sides together cover the entire graph or matroid, but forbid all such $m$-sets with $m$ up to some fixed value $n>3$. The resulting set $\F$ can then be replaced by its subset $\F^*$ of stars without affecting the set of consistent orientations avoiding~$\F$, just as in Lemma~\ref{F*toF}.
   \COMMENT{}

Similarly, we might like \td s whose decomposition trees have degrees of at least~$n$ at all internal nodes: graphs with such a \td, of width and adhesion~$<k$ say, would `decay fast' along $(<k)$-separations. Such \td s can be described as $S_k$-trees over the subset $\F^n_k$ of all $(\ge n)$-sets and singletons in the usual $\F_k$ that captures tree-width~$<k$ (Section~\ref{subsec:twd}).
   \COMMENT{}

Another ingredient we might wish to change are the singleton stars in $\F$ associated with leaves. For example, we might be interested in \td s whose leaf parts are planar, while its internal parts need not be planar but might have to be small. Theorem~\ref{thm:strong} would offer dual objects also for such decompositions.

Conversely, it would be interesting to see whether other natural highly connected substructures than those discussed in the preceding sections can be described as $\F$-tangles for some~$\F$ of a suitable set $S$ of separations~-- of a graph or something else.

Bowler~\cite{B14KkandNPC} answered this in the negative for complete minors in graphs, a natural candidate. Using the terminology of~\cite{DiestelBook10noEE} for minors $H$ of~$G$, let us say that a separation $(A,B)$ of $G$ \emph{points to} an $I H\sub G$ if this $I H$ has a branch set in $B\sm A$ but none in~$A\sm B$. A~set of oriented separations \emph{points to} a given $IH$ if each of its elements does. Clearly, for every $IK_k\sub G$ exactly one of $(A,B)$ and $(B,A)$ in $\vS_k$ points to this~$IK_k$.

\begin{THM}
For every $k\ge 5$ there exists a graph $G$ such that for no set $\F\sub 2^{\vS_k}$ of stars are the $\F$-tangles of $S_k$ precisely the orientations of~$S_k$ that point to some $IK_k\sub G$.
\end{THM}

To prove this,
   \COMMENT{}
   Bowler considered as $G$ a subdivision of $K_k$ obtained by subdividing every edge of $K_k$ exactly once. He constructed an orientation $O$ such that every star $\sigma\sub O$ points to an~$IK_k$ but the entire $O$ does not. This~$O$, then, avoids every $\F$ consisting only of stars not pointing to any~$IK_k$. But any $\F\sub 2^{\vS_k}$ such that the orientations of $S_k$ pointing to an $IK_k$ are precisely the $\F$-tangles must consist of stars not pointing to an~$IK_k$, since any star that does is contained in the unique orientation of~$S_k$ pointing to the $IK_k$ to which this star points.

\medbreak

However, $K_k$~minors can be captured by $\F$-avoiding orientations of $S_k$ if we do not insist that $\F$ contain only stars but allow it to contain \emph{weak stars}: sets of oriented separations that pairwise either cross or point towards each other (formally: consistent antichains in~$\vS_k$).
   \COMMENT{}
   In~\cite{DiestelOumDualityII} we prove a duality theorem for orientations of separation systems avoiding such collections $\F$ of weak stars.

\section*{Acknowledgement}
We enjoyed a visit by Fr\'ed\'eric Mazoit to the University of Hamburg in the summer of 2013, when he gave a series of lectures on the duality theorems for width parameters developed in~\cite{MazoitPartition,MazoitPushing} and we tried, unsuccessfully, to apply these to the dense substructures to be treated in Part II of this paper~\cite{DiestelOumDualityII}.

\bibliographystyle{abbrv}
\bibliography{collective}

\end{document}

config: arxiv