# Limit-closed Profiles

Ann-Kathrin Elm  Research conducted at Universität Hamburg, Department of
Mathematics, Hamburg, Germany Ann-Kathrin Elm: Universität Heidelberg,
Department of Computer Science, Heidelberg, Germany<EMAIL_ADDRESS>heidelberg.de<EMAIL_ADDRESS>and  Hendrik Heine

###### Abstract.

Tangle-tree theorems are an important tool in structural graph theory, and
abstract separation systems are a very general setting in which tangle-tree
theorems can still be formulated and proven. For infinite abstract separation
systems, so far tangle-tree theorems have only been shown for special cases of
separation systems, in particular when the separation system arises from a
(locally finite) infinite graph. We present a tangle-tree theorem for infinite
separation systems where we do not place restrictions on the separation system
itself but on the tangles to be arranged in a tree.

###### Key words and phrases:

infinite abstract separation system, tree set, tangle-tree theorem, profile

###### 2020 Mathematics Subject Classification:

06-XX (Primary), 05C63, 05C05 (Secondary)

##  1\. Introduction

Tangles were first introduced by Robertson and Seymour in [11] as an
obstruction to high tree-width. One of the important ingredients in their
graph minor project was a tangle-tree theorem, that is a theorem giving a tree
decomposition separating all the tangles of a graph.

As it turns out these features of tangles, both being an obstruction and
admitting a tangle-tree theorem, can be formulated more abstractly. This is
the core of the theory of abstract separation systems formulated in [5]. In
this setting tangle-tree theorems are now usually formulated more generally in
terms of profiles instead of tangles and tree sets instead of tree
decompositions, as seen for instance in [7]. While that article gives a very
general such theorem for finite separation systems, for infinite separation
systems there is no general tangle-tree theorem. But there are several tangle-
tree theorems for special cases of infinite separation systems: for separation
systems that come from a (locally finite) graph (see for example [3]), are the
inverse limit of finite separation systems [8], or in which every separation
crosses only finitely many others [10]. In this article we consider a property
not of the infinite separation system but of the profiles to be distinguished
in order to obtain a tangle-tree theorem. In particular we ask that the
profiles to be distinguished are closed under taking limits (the formal
definition follows in Section 3).

In that same section we find, for a separation system and a set of regular
closed profiles, a tree set distinguishing the profiles in a two step process.
Here, a regular profile is a profile that does not contain certain separations
that behave very counter-intuitively. First, we consider a set of equivalence
classes of separations, show that these form a separation systems with special
properties, and find a tree set of such equivalence classes. Then we choose
representatives of for these equivalence classes that form a tree set. In
Section 4 we show that the regularity can be dropped from the requirements on
the profiles by slightly adjusting the separation system such that it does not
contain separations with counter-intuitive behaviour. Section 5 then applies
the result from Section 3 inductively to get a full tree of tangles for a
separation system with an order function. The main point here is that the
order function defines a chain of subsystems of the separation system, each
with its own profiles, and the resulting tree of tangles distinguishes all
profiles of the distinct subsystems at once.

##  2\. Preliminaries

pqrs Figure 1. In this figure, separations are depicted as a line with a small
arrow attached. This visualisation comes from the example of a separation
system where the separations are subsets of some ground set $E$ and the
partial order and involution are the subset relation and complement operation.
For a separation $s$, i.e. a subset of $E$, the line then depicts the border
between $s$ and its complement, and the arrow points towards the side which is
the complement of $s$.
So in this illustration, $p$ and $q$ cross and $p$ points towards $r$. Also
$s$ is the infimum of $p$ and $q$ and thus would technically have to be
depicted slightly more to the right, but then the illustration would be much
harder to understand. This type of visualisation does not work for trivial and
degenerate separations, as they cannot be properly represented as subsets of a
ground set.

We will assume the reader to be familiar with the basic definitions and facts
about separation systems and (submodular) universes, which are explained in
detail in [5]. In this paper, all order functions will only have values in the
integers. Also, we will only need the notion of oriented separations and not
the one of unoriented separations. So we will shorten the term “oriented
separation” to just “separation”. In a submodular universe
$(U,\leq,\mathord{{}^{*}})$, we will denote separations of order exactly $k$
as _$k$ -separations_, separations of order at most $k$ as _$\leq k$
-separations_ and separations of order less than $k$ as _$ <k$-separations_.
As defined in [2], a homomorphism of separation systems
$(S,\leq,\mathord{{}^{*}})$ and
$(S^{\prime},\leq^{\prime},{\mathord{{}^{*}}}^{\prime})$ is a map
$f:S\rightarrow S^{\prime}$ such that for all separations $s$ and $t$ in $S$,
$f(s^{*})={f(s)^{*}}^{\prime}$ and $s\leq t\Rightarrow f(s)\leq^{\prime}f(t)$.

The following definitions of profiles can be found in [7], and the
structurally submodular separation systems are defined for example in [6]. Let
$(U,\leq,\mathord{{}^{*}})$ be a universe of separations and
$(S,\leq,\mathord{{}^{*}})$ a subsystem. In this context, infima and suprema
of elements of $S$ are always taken in the universe111The alternative would be
to take them in the restriction of $\leq$ to $S$, where suprema and infima
need not always exist. and thus always exist, but need not be elements of $S$.
$S$ is _structurally submodular_ if for all separations $s$ and $t$ in $S$ at
least one of $s\vee t$ and $s\wedge t$ is contained in $S$. A _profile of $S$_
is a consistent orientation of $S$ such that for any elements $s$ and $t$ of
the profile the separation $(s\vee t)^{*}$ is not contained in the profile. In
particular, if $s\vee t$ is contained in $S$ then it is also contained in the
profile, and a separation system containing a degenerate separation does not
have a profile. Note that the definition of a profile thus not only depends on
the separation system but also on the surrounding universe. If $U$ is
submodular, then a _$k$ -profile_ of $U$ is a profile of $S_{k}$, the
subsystem of $U$ consisting of the separations of order less than $k$. A
_profile of $U$_ is a $k$-profile of $U$ for some $k\in\mathbb{N}$, and $k$ is
its _order_.

Given a $k$-profile $P$ of $U$ and $l\in\mathbb{N}$ with $l\leq k$, the set
$P\cap S_{l}$ is the $l$-profile _induced_ by $P$. Two profiles $P$ and $Q$ of
$U$ are _distinguished_ by a separation $s$ if $s\neq s^{*}$ and one of $s$
and $s^{*}$ is contained in $P$ and the other one in $Q$. If $U$ is submodular
and the order of $s$ is minimal among all separations distinguishing $P$ and
$Q$, then $s$ distinguishes them _efficiently_. A set of separations $T$
distinguishes a set $\mathcal{P}$ of profiles of $U$ (efficiently) if for
every pair of distinguishable profiles in $\mathcal{P}$ (that is, profiles for
which there is a separation distinguishing them) there is a separation in $t$
distinguishing them (efficiently). A profile $P$ of $U$ is _robust_ if for
every $r\in P$ and every $l$-separation $s$ the following holds: If the orders
of both $r^{*}\wedge s$ and $r^{*}\wedge s^{*}$ are less than the order of
$r$, then $P$ does not contain both $r^{*}\wedge s$ and $r^{*}\wedge s^{*}$.
There are also other, slightly weaker definitions of robustness. But that is
not relevant, as robustness is never used directly, only the following
consequence [7, Lemma 3.6]: In a submodular universe, if $r$ efficiently
distinguishes two robust profiles $P$ and $P^{\prime}$ and $s$ efficiently
distinguishes two robust profiles $Q$ and $Q^{\prime}$ and the order of $r$ is
less than the order of $s$, then one of $r\wedge s$, $r\wedge s^{*}$,
$r^{*}\wedge s$ and $r^{*}\wedge s^{*}$ efficiently distinguishes $Q$ and
$Q^{\prime}$.

##  3\. Equivalence classes

Let $S$ be a separation system in some universe $U$ and $\mathcal{P}$ a set of
regular profiles of $S$. Then we can define a map
$f_{\mathcal{P}}:S\rightarrow 2^{\mathcal{P}}$ via
$f_{\mathcal{P}}(s)=\\{P\in\mathcal{P}|s^{*}\in P\\}$. Intuitively, the image
of $f_{\mathcal{P}}$ condenses from $S$ the information how it distinguishes
the elements of $\mathcal{P}$. We consider $2^{\mathcal{P}}$ as a separation
system with inclusion as the order.

######  Lemma 3.1.

The map $f_{\mathcal{P}}$ is a homomorphism of separation systems which
respects $\vee$ and $\wedge$.

###### Proof.

Since profiles orient every separation, $f_{\mathcal{P}}$ respects the
involution. Furthermore if $s\leq t$ and $s^{*}\in P$ for some profile $P$,
then we cannot have $t\in P$ by consistency, so $f_{\mathcal{P}}(s)\leq
f_{\mathcal{P}}(t)$. Now it suffices to prove that for $s,t\in S$ with $s\vee
t\in S$ an arbitrary $P\in\mathcal{P}$ contains $s\vee t$ if and only if it
contains both $s$ and $t$. The forward implication follows by consistency, the
backwards one by the profile property. ∎

The fibers of $f_{\mathcal{P}}$ are exactly the equivalence classes obtained
by regarding two separations as equivalent if they are oriented the same way
by every profile in $\mathcal{P}$. Assuming a structurally submodular $S$,
comparing these equivalence classes via their images under $f_{\mathcal{P}}$
gives the same partial order as comparing them via their elements. In fact, a
slightly weaker condition suffices. Call $S$ _weakly $\mathcal{P}$-submodular
(with respect to $\mathcal{P})$_ if whenever $f_{\mathcal{P}}(s)\leq
f_{\mathcal{P}}(t)$ at least one of $s\vee t$ and $s\wedge t$ is contained in
$S$.

######  Proposition 3.2.

Let $S$ be weakly $\mathcal{P}$-submodular with respect to $\mathcal{P}$. Then
for $A,B\in\operatorname{im}(f_{\mathcal{P}})$ we have $A\leq B$ if and only
if there are $a\in f_{\mathcal{P}}^{-1}(A),b\in f_{\mathcal{P}}^{-1}(B)$ with
$a\leq b$.

###### Proof.

The backward direction is immediate by Lemma 3.1. For the forward direction
choose $a\in f_{\mathcal{P}}^{-1}(A),b\in f_{\mathcal{P}}^{-1}(B)$. At least
one of $a\wedge b$ and $a\vee b$ is contained in $S$ by weak submodularity. If
$a\wedge b\in S$, then by Lemma 3.1 it is contained in
$f_{\mathcal{P}}^{-1}(B)$ and thus forms the required pair together with $b$.
Similarly, if $a\vee b\in S$, then $a\vee b\in f_{\mathcal{P}}^{-1}(A)$ and it
forms the required pair with $a$. ∎

We want to use the transformation $f_{\mathcal{P}}$ to find a distinguishing
set for $\mathcal{P}$. We will proceed in two steps: First we will look for an
abstract distinguishing set in the image and then look for separations of $S$
to represent them.

Let us start by stating our objective for the first step more formally. We
will say that $A\in\operatorname{im}(f_{\mathcal{P}})$ _separates_
$P,Q\in\mathcal{P}$ if $P\in A$ and $Q\notin A$ or vice versa. Then we are
looking for some tree set $T\subseteq\operatorname{im}(f_{\mathcal{P}})$ such
that different elements of $\mathcal{P}$ are always separated by some element
of $\operatorname{im}(f_{\mathcal{P}})$. Since structural submodularity of $S$
translates to $\operatorname{im}(f_{\mathcal{P}})$, for finite $\mathcal{P}$
standard techniques easily show that this condition is enough to reach our
goal. If $\mathcal{P}$ is infinite these standard methods are not sufficient,
but there is a useful idea, seen for instance in [1] or [4], which may help.
That idea is taking only the _good_ separations, that is those not crossed by
any other separation, for our tree set.

In the following we will show that, given certain conditions, the set
$T(S,\mathcal{P})$ of good separations of $\operatorname{im}(f_{\mathcal{P}})$
(except $\emptyset$ and $\mathcal{P}$) does indeed meet our demands. Since
$T(S,\mathcal{P})$ is a tree set by definition, all that needs to be shown is
that $T(S,\mathcal{P})$ separates any two distinct elements of $\mathcal{P}$.
When dealing with finite separation systems, it is sometimes useful to
consider maximal separations. If we want to use this trick in the infinite
case, we encounter some difficulties. First of all, profiles may not even have
maximal elements, which would render our strategy impossible. Thus we require
our profiles to be _closed_ , meaning that any chain in the profile has a
supremum in the universe which is contained in the profile. This ensures that
each profile has a maximal element, but even these maximal elements may not
have the nice properties which we are used to, say when we have an order
function.

Thus we need one more condition, which emulates some of the additional
structure provided by an order function. We call $S$ _orderly_ (with respect
to $\mathcal{P}$) if for any $s,t\in S$ such that both $\\{s,t\\}$ and
$\\{s^{*},t^{*}\\}$ are subsets of (possibly different) elements of
$\mathcal{P}$ we have $s\vee t\in S$ and $s\wedge t\in S$. To give an example,
it will follow from Lemma 5.3 that the set of proper $k$-separations in a
$k$-connected graph is orderly.

######  Lemma 3.3.

If $S$ is orderly and every $P\in\mathcal{P}$ is closed, all different
$P,Q\in\mathcal{P}$ are separated by some $t\in T(S,\mathcal{P})$.

###### Proof.

Let $C$ be a chain in $S$ such that each element of $C$ is contained in $P$
and not in $Q$ which is maximal with these properties. Since $P$ is closed,
$C$ has a supremum $s$, which is contained in $P$. Furthermore, by
consistency, we have $s\notin Q$. Now it suffices to prove that
$f_{\mathcal{P}}(s)$ is good. If not, there exists some $x\in S$ such that the
images of $s$ and $x$ cross, without loss of generality $x\in P$. But since
$S$ is orderly, this would imply $s\vee x\in S$ and hence $s\vee x\in P$ and
this separation could have been added to $C$. ∎

Now let us consider the second step. Starting with a regular tree set $T$ in
$\operatorname{im}(f_{\mathcal{P}})$, we want to find a nested set of
preimages (or equivalently one isomorphic to $T$). Once again we want to use
maximal separations and so need the same conditions as before. Closure
guarantees that each equivalence class has a maximal separation and
orderliness that it is even greatest.

######  Lemma 3.4.

If every $P\in\mathcal{P}$ is closed, for every $t\in T$ the set
$f_{\mathcal{P}}^{-1}(t)$ has a greatest element.

###### Proof.

Let $X=f_{\mathcal{P}}^{-1}(t)$ and let $C$ be a nonempty chain in $X$. Since
$\mathcal{P}\setminus t$ is nonempty and each profile in that set is closed,
$C$ has a supremum $s$ with $f_{\mathcal{P}}(s)\supseteq t$. Conversely there
cannot be any $Q\in t$ with $s\in Q$, since we would then have $C\subseteq Q$
by consistency, a contradiction. Thus $s\in X$. This implies that any element
of $X$ lies below some maximal element.

Now let $a$ and $b$ be two maximal elements of $X$. Since $S$ is orderly,
$a\vee b\in S$ and then also $a\vee b\in X$. By maximality of $a$ and $b$
these must then both be equal to $a\vee b$ and we have $a=b$. Thus $X$ only
has a single maximal element which must then be greater than all other
separations in $X$. ∎

Let $m$ be the function mapping each $t\in T$ to the greatest element of
$f_{\mathcal{P}}^{-1}(t)$. We would like to use $m$ to choose the
representatives, however, this is not quite possible, since for $t\in T$ the
separations $m(t)$ and $m(t^{*})$ are usually not inverses. Fortunately, this
is no great obstacle. If we simply choose one of these two possible unoriented
separations, the only thing that could go wrong is that for $s\leq t$ we
choose $m(s)$ and $m(t^{*})^{*}$ as the representing separations. It thus
suffices to choose exactly opposite to a consistent orientation, which always
exists. So we fix a consistent orientation $o$ of $T$ and define the function
$m_{o}$ by mapping $s\in T$ to $m(s^{*})^{*}$ for $s\in o$ and to $m(s)$ for
$s\notin o$. Let $\hat{T}$ be the image of $T$ under $m_{o}$.

######  Corollary 3.5.

Let $S$ be orderly and every $P\in\mathcal{P}$ closed. Then $f_{\mathcal{P}}$
restricts to an isomorphism between $\hat{T}$ and $T$.

###### Proof.

Clearly, $m_{o}$ is the inverse map of $f_{\mathcal{P}}$ restricted to the
image of $m_{o}$. Since $f_{\mathcal{P}}$ is a homomorphism by Lemma 3.1, it
suffices to show that $m_{o}$ is, too. So let $s,t\in T$ be such that $s\leq
t$. We need to show that $m_{o}(s)\leq m_{o}(t)$. If $t\notin o$, we have
$m_{o}(t)=m(t)$. Since $S$ is orderly, we have $m(t)\vee m_{o}(s)\in S$. By
Lemma 3.1 $f_{\mathcal{P}}(m(t)\vee m_{o}(s))=f_{\mathcal{P}}(m(t))\cup
f_{\mathcal{P}}(m_{o}(s))=t\cup s=t$. But since $m(t)$ is a greatest element,
we must have $m_{o}(s)\leq m(t)=m_{o}(t)$. So we may assume $t\in o$ and by
consistency also $s\in o$. Then we have $m_{o}(s)=m(s^{*})^{*}$ and
$m_{o}(t)=m(t^{*})^{*}$. Since $S$ is orderly, we have $m(s^{*})\vee
m(t^{*})\in S$ and calculating with Lemma 3.1 as before we get
$f_{\mathcal{P}}(m(s^{*})\vee m(t^{*}))=s^{*}$. Again by choice of $m(s^{*})$
we must have $m(s^{*})\geq m(t^{*})$ and thus $m_{o}(s)\leq m_{o}(t)$. ∎

This completes the second step. Overall, we have now proven the following
theorem.

######  Theorem 3.6.

Let $S$ be a regular separation system orderly with respect to a set
$\mathcal{P}$ of closed profiles. Then there is a tree set $T$ with the
following properties:

  1. (1)

Any two different elements $\mathcal{P}$ are distinguished by some element of
$T$.

  2. (2)

Any element of $T$ distinguishes some elements of $\mathcal{P}$.

  3. (3)

In the set $P\cap T$ for every $P\in\mathcal{P}$ every separation lies below
some maximal separation.

##  4\. Non-regular profiles

In this section we want to show that in Theorem 3.6, the regularity condition
can be dropped. In order to do so, we will slightly adjust $S$ and
$\mathcal{P}$ to a regular separation system with a modified set of profiles.
Then the modified profiles are necessarily regular, and theory for regular
profiles can be applied to them and the adjusted separation system. As a last
step we will show that any tree set distinguishing the modified profiles also
distinguishes $\mathcal{P}$.

There is a procedure to make a separation system regular in [5]: first taking
its _essential core_ , i.e. deleting all trivial, co-trivial and degenerate
elements, and then taking the _regularization_ of that essential core, that
is, dropping relations of the form $s\leq s^{*}$ from the partial order. This
two-step-procedure is necessary because dropping relations of the form $s\leq
s^{*}$ from the partial order need not yield another partial order if there
are degenerate or trivial elements present. But if $S$ is a subsystem of a
surrounding universe, it is in general not possible to just delete trivial
elements from the universe, and then it is not possible to adjust the
surrounding universe to also be a surrounding universe for the regularization.
In order to overcome this problem, we will have to relax the notion of corners
in a separation system once more so we can cope without a surrounding
universe.

######  Definition 4.1.

Let $(S,\mathord{{}^{*}},\leq)$ be a separation system. A _corner map_ is a
map $\vee$ from a subset of $S\times S$ to $S$ such that

  * •

if $s\leq t$, then $\vee(s,t)$ is defined, and

  * •

if $\vee(s,t)$ is defined, then also $\vee(t,s)$ is defined and it is the
supremum of $s$ and $t$ in the partial order $\leq$.

For a separation system with corner map, in analogy to a separation system
that is a subsystem of a universe, we say that a corner $s\vee t$ _exists_ in
$S$ or _is contained in $S$_ if $\vee(s,t)$ is defined. Also, $\vee(s,t)$ will
be denoted by $s\vee t$, and $s\wedge t$ is a shorthand for $(s^{*}\vee
t^{*})^{*}$.

######  Example 4.2.

If $S$ is a separation system that is a subsystem of some universe $U$, then
$S$ naturally comes with a corner map where $\vee(s,t)$ is defined if $s\vee
t$, which exists in the surrounding universe, is contained in $S$. Another
example of a corner map, which can be defined without taking a surrounding
universe into account, is to define $\vee(s,t)$ to exist whenever $s$ and $t$
have a supremum in the partial order $\leq$. As every separation system can be
embedded into a universe in a way that preserves suprema of $\leq$ (see [9,
Theorem 3.1]), this example is actually a special case of the previous example
for a corner map. As a third example, one can define a corner map where
$\vee(s,t)$ is defined only when $s\leq t$ or $t\leq s$.

Formally, we have to redefine our terminology for separation systems with
corner map. But of course all these definitions will be the same as before and
just as expected.

######  Definition 4.3.

Let $(S,\leq,\mathord{{}^{*}},\vee)$ be a separation system with a corner map.
A _profile_ of the separation system with corner map is a consistent
orientation $P$ of $(S,\leq,\mathord{{}^{*}})$ such that for all $s,t$ in $P$,
if $s\vee t$ is defined then $(s\vee t)^{*}$ is not contained in $P$. Given a
set of profiles $\mathcal{P}$, the separation system with corner map is
_orderly_ with respect to $\mathcal{P}$ if for all separations $s$ and $t$
such that some profile in $\mathcal{P}$ contains $s$ and $t$ and some profile
in $\mathcal{P}$ contains $s^{*}$ and $t^{*}$ then both $s\vee t$ and
$s^{*}\vee t^{*}$ are defined. A profile $P$ is _closed_ in $S$ if for all
$\leq$-chains in $P$ the supremum with respect to $\leq$ exists in $S$ and is
contained in $P$.

Note that if $S$ is a separation system that is a subsystem of a universe $U$,
then a consistent orientation of $S$ is a profile of $S\subseteq U$ if and
only if it is a profile of $S$ with the induced corner map, and a profile of
$S$ that is closed with respect to $S$ as a subsystem of $U$ is also closed in
$S$ itself. Furthermore, if $\mathcal{P}$ is a set of profiles of $S$, then
$S\subseteq U$ is orderly with respect to $\mathcal{P}$ if and only if $S$
with the induced corner map is orderly with respect to $\mathcal{P}$.

Now we want to apply regularization to a separation system with corner map and
a set of profiles. Through this process we can essentially keep the corner map
and the set of profiles, and we preserve orderliness and closedness.

######  Definition 4.4.

Let $(S,\leq,\mathord{{}^{*}},\vee)$ be a separation system with a corner map.
The _essential core_ of $(S,\leq,\mathord{{}^{*}},\vee)$ is the set
$S^{\prime}$ of separations in $S$ that are neither degenerate nor trivial nor
co-trivial, together with the restrictions of $\leq$, $\mathord{{}^{*}}$ and
$\vee$ to $S^{\prime}$. The _regularization_ of the essential core is the
tuple $(S^{\prime},\leq^{\prime},\mathord{{}^{*}}^{\prime},\vee^{\prime})$
where $s\leq^{\prime}t$ for elements $s$ and $t$ of $S^{\prime}$ if and only
if $s\leq t$ and $s\neq t^{*}$, $\mathord{{}^{*}}^{\prime}$ is the restriction
of $\mathord{{}^{*}}$ to $S^{\prime}$ and $\vee^{\prime}$ is defined for all
those elements $s$ and $t$ of $S^{\prime}$ for which $s\vee t$ is defined,
contained in $S^{\prime}$, and the supremum of $s$ and $t$ in $\leq^{\prime}$.

######  Lemma 4.5.

Let $\mathcal{P}$ be a set of profiles of a separation system with corner map
$(S,\leq,\mathord{{}^{*}},\vee)$. Then the regularization
$(S^{\prime},\leq^{\prime},\mathord{{}^{*}}^{\prime},\vee^{\prime})$ of the
essential core is a regular separation system with corner map of which
$\mathcal{P}^{\prime}:=\\{P\cap S^{\prime}\colon P\in\mathcal{P}\\}$ is a set
of profiles. Moreover, if $S$ is orderly with respect to $\mathcal{P}$, then
$S^{\prime}$ is orderly with respect to $\mathcal{P}^{\prime}$, and if the
elements of $\mathcal{P}$ are closed with respect to $\leq$ then the elements
of $\mathcal{P}^{\prime}$ are closed with respect to $\leq^{\prime}$.

###### Proof.

It has already been shown in [5] that
$(S^{\prime},\leq^{\prime},\mathord{{}^{*}}^{\prime})$ is a regular separation
system, and $\vee^{\prime}$ is clearly a corner map of that separation system.

Let $P\in\mathcal{P}$. By the definition of profile of a separation system
with corner map, $P\cap S^{\prime}$ is a profile of
$(S^{\prime},\leq^{\prime},\mathord{{}^{*}}^{\prime},\vee^{\prime})$. We will
now show that if $P$ is closed with respect to $\leq$, then $P\cap S^{\prime}$
is closed with respect to $\leq^{\prime}$. So assume $P$ is closed with
respect to $\leq$ and let $(s_{i})_{i\in I}$ be a $\leq^{\prime}$-chain of
elements of $P\cap S^{\prime}$. Then $(s_{i})_{i\in I}$ is also a $\leq$-chain
of elements of $P$, so it has a supremum $s$ with respect to $\leq$ and that
supremum is contained in $P$. If $s=s_{i}$ for some index $i$, then $s_{i}$ is
contained in $P\cap S^{\prime}$ and is the supremum of the $s_{i}$ with
respect to $\leq^{\prime}$. We will show that $s$ is also the supremum of the
$s_{i}$ with respect to $\leq^{\prime}$ in the case that $s\neq s_{i}$ for all
indices $i$. For that, let $i$ be some index. As $s_{i}<s$, and $s_{i}$ is
contained in $S^{\prime}$ and thus neither trivial nor degenerate, also $s$ is
neither trivial nor degenerate. Furthermore, $s$ is contained in $P$ and hence
cannot be cotrivial. Thus $s$ is contained in $S^{\prime}$ and hence $s\in
P\cap S^{\prime}$. In order to show that $s_{i}\leq^{\prime}s$, let $j$ be
another index such that $s_{i}<^{\prime}s_{j}$. Then $s_{i}<s_{j}<s$, and as
$s_{j}$ is not trivial, $s_{i}\neq s^{*}$. Thus $s_{i}\leq^{\prime}s$. Let
$s^{\prime}$ be another upper bound of the $s_{i}$ with respect to
$\leq^{\prime}$. Then $s_{i}<s<s^{\prime}$, and as $s_{i}$ is not trivial,
$s^{*}\neq s^{\prime}$. Hence $s\leq^{\prime}s^{\prime}$, and $s$ is indeed
the supremum of the $s_{i}$ with respect to $\leq^{\prime}$.

We will now show that if $S$ is orderly with respect to $\mathcal{P}$, then
$S^{\prime}$ is orderly with respect to $\mathcal{P}^{\prime}$. So let $s$ and
$t$ be elements of $S^{\prime}$ and let $P$ and $Q$ be elements of
$\mathcal{P}^{\prime}$ such that $P\cap S^{\prime}$ contains both $s$ and $t$
and $Q$ contains both $s^{*}$ and $t^{*}$. We will only show that
$s\vee^{\prime}t$ is defined, the fact that $s^{*}\vee^{\prime}t^{*}$ is also
defined then follows from swapping the roles of $P$ and $Q$. As $S$ is orderly
with respect to $\mathcal{P}$, $s\vee t$ is defined and thus contained in $P$.
In particular $s\vee t$ is not co-trivial. Consider the case that $s\vee t=s$.
In that case $t\leq s$. As both $s$ and $t$ are contained in $P$ and are non-
degenerate, $t\neq s^{*}$ and thus $t\leq^{\prime}s$. Hence $s\vee^{\prime}t$
is defined and we are done. Similarly if $s\vee t=t$ then we are done. So we
may assume that $s<s\vee t$ and $t<s\vee t$. As $s$ is not trivial, $s\vee t$
is neither degenerate nor trivial, and thus $s\vee t$ is contained in $P\cap
S^{\prime}$. Again, as $s$ and $s\vee t$ are both contained in $P$ and non-
degenerate, $s\neq(s\vee t)^{*}$ and thus $s\leq^{\prime}s\vee t$. Similarly
$t\leq^{\prime}s\vee t$. Finally, let $p$ be another upper bound of $s$ and
$t$ in $\leq^{\prime}$ with $s\vee t\neq p$. Then $s<s\vee t<p$, so if $s\vee
t=p^{*}$ then $s$ is trivial. But $s$ is not trivial, and thus $s\vee t\neq
p^{*}$ so $s\vee t\leq^{\prime}p$. Hence $s\vee t$ is the supremum of $s$ and
$t$ with respect to $\leq^{\prime}$ and so $s\vee^{\prime}t$ is defined. ∎

So we have shown that we can make a separation system with corner map and a
set of profiles $\mathcal{P}$ regular. Now we have to show that if we find a
tree set of the regularization that distinguishes $\mathcal{P}^{\prime}$, then
we can translate it back to a nested subset of the original separation system
distinguishing $\mathcal{P}$.

######  Lemma 4.6.

Let $(S,\leq,\mathord{{}^{*}},\vee)$ be a separation system with a corner map
and let $\mathcal{P}$ be a set of profiles of that separation system. Denote
the regularization of the essential core of the separation system by
$(S^{\prime},\leq^{\prime},\mathord{{}^{*}}^{\prime},\vee^{\prime})$. If $T$
is a tree set contained in $S^{\prime}$ distinguishing $\\{P\cap
S^{\prime}\colon P\in\mathcal{P}\\}$, then $T$ is also a tree set of $S$ and
distinguishes $\mathcal{P}$.

###### Proof.

Let $T$ be a tree set contained in $S^{\prime}$ that distinguishes $\\{P\cap
S^{\prime}\colon P\in\mathcal{P}\\}$. Then $T$ is also a nested subset of $S$
and a tree set of $\leq$. Every profile contains every trivial and degenerate
separation, so every separation in $S$ distinguishing two profiles in
$\mathcal{P}$ is also contained in $S^{\prime}$. Hence, if $P$ and $Q$ are
distinct elements of $\mathcal{P}^{\prime}$, then $P\cap S^{\prime}$ and
$Q\cap S^{\prime}$ are distinct profiles of $S^{\prime}$ and thus $P\cap
S^{\prime}$ and $Q\cap S^{\prime}$ are distinguished by $T$. So $T$
distinguishes all elements of $\mathcal{P}$. ∎

Let us now summarise the results of this section so far.

######  Lemma 4.7.

Let $(S,\leq,\mathord{{}^{*}},\vee)$ be a separation system with corner map,
and let $\mathcal{P}$ be a set of profiles of this separation system. Then
there is a regular separation system with corner map
$(S^{\prime},\leq^{\prime}\mathord{{}^{*}}^{\prime},\vee^{\prime})$ and set of
profiles $\mathcal{P}^{\prime}$ such that every tree set distinguishing
$\mathcal{P}^{\prime}$ in $S^{\prime}$ also distinguishes $\mathcal{P}$ in
$S$. Moreover, if $S$ is orderly with respect to $\mathcal{P}$ then
$S^{\prime}$ is orderly with respect to $\mathcal{P}^{\prime}$ and if the
elements of $\mathcal{P}$ are closed with respect to $\leq$ then the elements
of $\mathcal{P}^{\prime}$ are closed with respect to $\leq^{\prime}$.

So now we can show that in Theorem 3.6 the regularity condition can be
dropped. Note that in the proof, the only properties of the universe
surrounding $S$ that is used are encoded by the properties of the induced
corner map. Therefore, Theorem 3.6 also holds (with the same proof) if $S$ is
not a subsystem of a universe but instead has a corner map.

So in particular we can prove the following generalisation of Theorem 3.6.

######  Corollary 4.8.

Let $(S,\leq,\mathord{{}^{*}},\vee)$ be a separation system with a corner map
that is orderly with respect to a set $\mathcal{P}$ of closed profiles. Then
there is a tree set $T$ with the following properties:

  1. (1)

Any two different elements $\mathcal{P}$ are distinguished by some element of
$T$.

  2. (2)

Any element of $T$ distinguishes some elements of $\mathcal{P}$.

  3. (3)

In the set $P\cap T$ for every $P\in\mathcal{P}$ every separation lies below
some maximal separation.

###### Proof.

By Lemma 4.5, the regularization
$(S^{\prime},\leq^{\prime},\mathord{{}^{*}}^{\prime},\vee^{\prime})$ is
orderly with respect to the set of profiles $\mathcal{P}^{\prime}:=\\{P\cap
S^{\prime}\colon P\in\mathcal{P}\\}$ and $\mathcal{P}^{\prime}$ is closed in
$S^{\prime}$. We can now obtain by Theorem 3.6 a tree set $T$ in $S^{\prime}$
distinguishing the elements of $\mathcal{P}^{\prime}$, which is a subset of
$S$ as required in this Corollary by Lemma 4.6. ∎

##  5\. A tangle-tree theorem for submodular separation systems

In this section, we will prove the following theorem. Recall that a profile of
a submodular universe is defined to be a $k$-profile of the universe for some
$k\in\mathbb{N}$.

######  Theorem 5.1 (main theorem).

Let $U$ be a submodular universe and let $\mathcal{P}$ be a collection of
distinguishable regular robust closed profiles. Then there is a tree set $T$
that efficiently distinguishes $\mathcal{P}$ such that every $t\in T$
efficiently distinguishes two profiles in $\mathcal{P}$.

######  Remark 5.2.

The tree set $T$ constructed in the proof of Theorem 5.1 additionally has the
property that for every $P\in\mathcal{P}$, every element of $T\cap P$ is less
than or equal to a maximal element of $T\cap P$.

We are going to recursively construct tree sets $T_{k}$ whose union then
efficiently distinguishes $\mathcal{P}$. To do this, let $\mathcal{P}_{k}$ be
the set of profiles of order at most $k$ that are induced by elements of
$\mathcal{P}$. For the construction of a tree set $T_{k+1}$ distinguishing the
elements of $\mathcal{P}_{k+1}$ we will employ the following proof strategy in
two steps, that is common in proofs of tree-of-tangles-theorems, for example
in [7]. First, for a $k$-profile $P\in\mathcal{P}_{k}$, Theorem 3.6 is applied
to the set of all $k+1$-profiles in $\mathcal{P}_{k+1}$ whose induced
$k$-profile is $P$ and to a carefully chosen subuniverse of $U$ to obtain a
tree set $T_{P}$. Second, it will be shown that $T_{k}$ together with all the
tree sets $T_{P}$ is a tree set that efficiently distinguishes
$\mathcal{P}_{k+1}$.

More precisely, we are going to show by induction that for every
$k\in\mathbb{N}$ there is a tree set $T_{k}$ with the following properties:

  * •

$T_{k}$ is a subset of $S_{k}$, and if $T_{k-1}$ exists then $T_{k-1}\subseteq
T_{k}$.

  * •

Every element of $T_{k}$ distinguishes two profiles in $\mathcal{P}_{k}$
efficiently.

  * •

$T_{k}$ distinguishes $\mathcal{P}_{k}$ efficiently.

  * •

For every $Q\in\mathcal{P}_{k}$, every element of $Q\cap T_{k}$ is less than
or equal to a maximal element of $Q\cap T_{k}$.

As the only $0$-profile is the empty set we define $T_{0}$ to be the empty
set. Assume that $T_{k}$ is already defined and we now want to define
$T_{k+1}$. For each $k$-profile $P\in\mathcal{P}_{k}$ let $\mathcal{Q}_{P}$ be
the set of all $(k+1)$-profiles in $\mathcal{P}_{k+1}$ whose induced
$k$-profile is $P$, $N_{P}$ the set of maximal elements of $P\cap T_{k}$ and
$U_{P}$ the set of all separations in $U$ towards which all separations of
$N_{P}$ point. Note that $U_{P}$ is a universe and closed under taking infima
and suprema of chains of bounded order, and that as a result the set of
$k$-separations of $U_{P}$ is structurally submodular and closed under taking
suprema of chains of bounded order. Then every profile in $\mathcal{Q}_{P}$
induces a closed $(k+1)$-profile of $U_{P}$.

We will want to apply the results of the previous section, in particular
Theorem 3.6, to $U_{P}$ and the profiles of $U_{P}$ induced by
$\mathcal{Q}_{P}$. In order to do so, we need to show that the separation
system $S_{k}$ of $U_{P}$ is orderly with respect to $\mathcal{Q}_{P}$. That
follows from the following, slightly more general statement.

######  Lemma 5.3.

Let $U$ be a submodular universe, $k$ a non-negative integer and $\mathcal{P}$
a set of $k+1$-profiles that all have the same induced $k$-profile. Then the
set of $k$-separations of $U$ is orderly with respect to $\mathcal{P}$.

###### Proof.

Assume $s$ and $t$ are $k$-separations of $U$ and $P$ and $Q$ are elements of
$\mathcal{P}$ such that $\\{s,t\\}\subseteq P$ and $\\{s^{*},t^{*}\\}\subseteq
Q$. By submodularity, one of $s\vee t$ and $s\wedge t$ is also a
$k$-separation, assume without loss of generality that $s\vee t$ is a
$k$-separation. Then $s\vee t$ is also contained in $P$.

First consider the case that $s\vee t$ is not contained in $Q$. Then $s\vee t$
distinguishes $P$ and $Q$, and thus has order exactly $k$. Hence by
submodularity also $s\wedge t$ is a $k$-separation and we are done.

So consider the case that $s\vee t\in Q$. As a separation system with a
degenerate separation does not have a profile, $s$ is not contained in $Q$.
Thus by consistency $s\leq s\vee t\in Q$ implies $s=(s\vee t)^{*}$. Similarly
$t=(s\vee t)^{*}$, so $s=t$ and the lemma holds. ∎

Now we will show that indeed all profiles in $\mathcal{Q}_{P}$ can be
distinguished by separations of $U_{P}$.

######  Lemma 5.4.

All profiles in $\mathcal{Q}_{P}$ are distinguished by separations of $U_{P}$
of order $k$.

###### Proof.

Let $f_{\mathcal{Q}_{P}}:U\rightarrow 2^{\mathcal{Q}_{P}}$ be defined as
Section 3. It suffices to show that if $r$ is a separation such that
$f_{\mathcal{Q}_{P}}(r)$ is neither $\emptyset$ nor $\mathcal{Q}_{P}$, then
there is an element of $U_{P}$ that has the same image under
$f_{\mathcal{Q}_{P}}$ as $r$. Let $X$ be the set of separations whose image
under $f_{\mathcal{Q}_{P}}$ is $f_{\mathcal{Q}_{P}}(r)$. Several times in this
proof we will use the fact that $f_{\mathcal{Q}_{P}}$ preserves infima and
suprema, and in particular any two elements of $X$ have an infimum and a
supremum.

If $N_{P}$ is empty, then $r$ itself is a separation of $U_{P}$ and we are
done, so assume otherwise. By Lemma 3.4, $X$ has a smallest element $s$. Let
$N^{\prime}$ be the set of all elements $n$ of $N_{P}$ such that $n\leq
s^{*}$. Define $X^{\prime}$ to contain all elements $x\in X$ with $n\leq
x^{*}$ for all $n\in N^{\prime}$. Just as in the proof of Lemma 3.4, the fact
that the profiles in $\mathcal{Q}_{P}$ are closed and Zorn’s Lemma imply that
$X^{\prime}$ has a maximal element $t$. See Fig. 2 for an illustration.

$n_{3}$$s$$t$$n_{1}$$n_{2}$$r$ Figure 2. The separation $s$ is less than the
separations $n_{1}^{*}$ and $n_{2}^{*}$, which is equivalent to $n_{1}\leq
s^{*}$ and $n_{2}\leq s^{*}$, and the separation $t$ is additionally bigger
than $n_{3}$.

We will show that all elements of $N_{P}$ point towards $t$. In order to do so
let $n$ be an element of $N_{P}$. If there is $q\in X$ such that $q\leq
n^{*}$, then $s\wedge q\in X$. By minimality of $s$ this implies $s=s\wedge
q$, so $s\leq q\leq n^{*}$ and thus $n\in N^{\prime}$. Hence $n$ points
towards $t$. The other case is where there is no such separation $q$, in
particular $t\wedge n^{*}$ is not a candidate for $q$. If $t\wedge n^{*}$ is a
$\leq k$-separation, then it is contained in $X$, because $n$ is contained in
all elements of $\mathcal{Q}_{P}$. So the fact that $t\wedge n^{*}$ is not
contained in $X$ implies that it is not a $\leq k$-separation. Because
$\mathcal{P}$ is robust and consistent, this implies that $t\vee
n=(t^{*}\wedge n^{*})^{*}$ efficiently distinguishes the same elements of
$\mathcal{Q}_{P}$ that $t$ distinguishes. Then $t$ is a $k$-separation and
thus contained in $X$, and all $n^{\prime}\in N^{\prime}$ point towards $t\vee
n$, so by maximality of $t$ in $X^{\prime}$ we have $t\vee n=t$ and hence
$n\leq t$. So also in this case $n$ points towards $t$. ∎

So in order to distinguish the elements of $\mathcal{Q}_{P}$, it suffices to
distinguish their intersections with $U_{P}$. We will do that by applying
Theorem 3.6 to the $k$-separations of $U_{P}$ and the profiles induced by
$\mathcal{Q}_{P}$. Call the obtained tree set $T_{P}$. Let $T_{k+1}$ be the
union of $T_{k}$ and all tree sets $T_{P}$ where $P$ is a $k$-profile
contained in $\mathcal{P}_{k}$.

######  Lemma 5.5.

$T_{k+1}$ is a tree set that distinguishes $\mathcal{P}_{k+1}$ efficiently,
and in which every separation distinguishes some elements of
$\mathcal{P}_{k+1}$.

###### Proof.

Let $P$ be a $k$-profile in $\mathcal{P}_{k}$. As for every separation $n$ in
$P\cap T_{k}$ there is an element $n^{\prime}$ of $N_{P}$ such that $n\leq
n^{\prime}$, $T_{k}$ is nested with every separation in $U_{P}$ and thus with
$T_{P}$. Also, if $P$ and $P^{\prime}$ are distinct $k$-profiles in
$\mathcal{P}_{k}$, then they are distinguished by some separation $n$ of
$T_{k}$, so they are also distinguished by some separation of $N_{P}$ which
then witnesses that every separation in $T_{P^{\prime}}$ is nested with every
separation in $T_{P}$. So $T_{k}$ is nested. Also by construction every
element of $T_{k+1}$ distinguishes two elements of $\mathcal{P}_{k+1}$ and
thus is neither small nor cosmall. Hence every element of $T_{k+1}$ is neither
trivial nor co-trivial nor degenerate.

In order to show that every two elements of $\mathcal{P}_{k+1}$ are
distinguished efficiently, let $P$ and $Q$ be two such elements that can be
distinguished. If $P$ and $Q$ can be distinguished by a separation of order at
most $k-1$, then they induce distinguishable elements of $\mathcal{P}_{k}$
which are thus efficiently distinguished by some separation $t$ of $T_{k}$.
Then $t$ also efficiently distinguishes $P$ and $Q$. So we are left with the
case that $P$ and $Q$ cannot be distinguished by a separation of order less
than $k$, which implies that they are both $(k+1)$-profiles and induce the
same $k$-profile $P^{\prime}$. But then $P$ and $Q$ are distinguished by a
separation in $T_{P^{\prime}}$, and that separation distinguishes them
efficiently. ∎

So in order to complete the proof of Theorem 5.1, we only have to prove the
following statement.

######  Lemma 5.6.

For every $Q\in\mathcal{P}_{k+1}$, every element of $Q\cap T_{k+1}$ is less
than or equal to a maximal element of $Q\cap T_{k+1}$.

###### Proof.

Let $Q\in\mathcal{P}_{k+1}$ and let $s\in Q\cap T_{k+1}$. By induction it
suffices to consider the case that $Q$ has order $k+1$. Denote the induced
$k$-profile of $Q$ by $Q^{\prime}$. If $s$ is not contained in
$T_{Q^{\prime}}$, then it is less than or equal to an element of
$N_{Q^{\prime}}$, and every element of $N_{Q^{\prime}}$ is either maximal in
$T_{k+1}\cap Q$ or less than a separation in $Q\cap T_{Q^{\prime}}$. So it
suffices to consider the case that $s\in T_{Q^{\prime}}$. But in this case by
Theorem 3.6 $s$ is less than or equal to a maximal element of
$T_{Q^{\prime}}\cap Q$ which then also is a maximal element of $Q\cap
T_{k+1}$. ∎

###### Proof of Theorem 5.1.

Let $T$ be the union of all the $T_{k}$ as defined in this section. Then $T$
is a tree set which distinguishes all distinguishable profiles in
$\mathcal{P}$ efficiently, and every separation in it distinguishes two
elements of $\mathcal{P}$ efficiently. ∎

## References

  * [1] Elad Aigner-Horev, Reinhard Diestel and Luke Postle  “The structure of 2-separations of infinite matroids”  In _J. Comb. Theory, Ser. B_ 116, 2016, pp. 25–56
  * [2] Nathan Bowler and Jakob Kneip  “Separations of sets”  In _Order_ 37, arXiv:1809.00625, 2020, pp. 411 –425
  * [3] Johannes Carmesin, Matthias Hamann and Babak Miraftab  “Canonical trees of tree-decompositions”  In _J. Comb. Theory, Ser. B_ 152, 2022, pp. 1–26
  * [4] William H. Cunningham and Jack Edmonds  “A combinatorial decomposition theory”  In _Can. J. Math._ 32, 1980, pp. 734–765
  * [5] Reinhard Diestel  “Abstract separation systems”  In _Order_ 35, arXiv:1406.3797, 2018, pp. 157–170
  * [6] Reinhard Diestel, Joshua Erde and Daniel Weißauer  “Structural submodularity and tangles in abstract separation systems”  In _J. Comb. Theory, Ser. A_ 167, 2019, pp. 155–180
  * [7] Reinhard Diestel, Fabian Hundertmark and Sahar Lemanczyk  “Profiles of separations: in graphs, matroids, and beyond”  In _Combinatorica_ 39.1, arXiv:1110.6207, 2019, pp. 37–75
  * [8] Reinhard Diestel and Jakob Kneip  “Profinite separation systems”  In _Order_ 37.1, 2020, pp. 179–205
  * [9] Christian Elbracht, Jakob Kneip and Maximilian Teegen  “The Structure of Submodular Separation Systems” Preprint arxiv: 2103.12162  arXiv, 2021
  * [10] Christian Elbracht, Jakob Kneip and Maximilian Teegen  “Trees of tangles in infinite separation systems”  In _Math. Proc. Camb. Philos. Soc._ 173.2, 2022, pp. 297–327
  * [11] Neil Robertson and P. D. Seymour  “Graph minors. X: Obstructions to tree-decomposition”  In _J. Comb. Theory, Ser. B_ 52.2, 1991, pp. 153–190