# Mathematical Representation
of Multitarget Systems

Ronald Mahler, Random Sets LLC, Eagan, MN, U.S.A

###### Abstract

This paper systematically compares two mathematical foundations for
multitarget tracking: labeled random finite sets (LRFS’s) and trajectory
random finite sets (TRFS’s).

##  I Introduction

As an engineering discipline, multitarget tracking dates back to the seminal
paper by Reid [1] and earlier—see [2] for an overview. The last 20 years of
multitarget tracking research have differed from the 20 years preceding them
in that there has been an increasing emphasis on theoretically rigorous
statistical foundations that also facilitate the development of practical
multitarget tracking algorithms.

Probably the most notable such algorithm is the generalized labeled multi-
Bernoulli (GLMB) filter, which arose from the random finite set (RFS) [3] and
labeled random finite set (LRFS) [4], [5] paradigms. Its most recent
implementations—made possible by the application of advanced Gibbs statistical
sampling techniques to the LRFS multitarget posterior density
$f_{k}(X|Z_{1:k})$ on labeled multitarget state-sets $X$—can simultaneously
track over one million targets in significant clutter in real time using off-
the-shelf computing equipment [6].

In the LRFS approach, the state of a multitarget system at time $t_{k}$ is
modeled as a labeled finite subset
$X=\\{(\mathbf{x}_{1},\ell_{1}),...,(\mathbf{x}_{n},\ell_{n})\\}\subseteq\mathfrak{X}_{0}\times\mathfrak{L}$
where: $\mathfrak{X}_{0}$ is the kinematic state space and $\mathfrak{L}$ is a
countable set of “track labels”; $\
X_{\mathfrak{L}}=\\{\ell_{1},...,\ell_{n}\\}$ is the set of labels of the
elements of $X$; and $|X|=|X_{\mathfrak{L}}|$ where $|S|$ denotes the
cardinality of a finite set $S$. That is, $X$ is “labeled” if the targets in
$X$ have unique labels. Given this, a time-evolving multitarget population is
represented as a time-sequence $X_{1},...,X_{k},...$ of multitarget labeled
state-sets at the measurement-collection times $t_{1},...,t_{k},...$

Since 2014, however, it has repeatedly been asserted that the LRFS framework
is seriously deficient because LRFS labels in $\mathfrak{L}$ have “…no direct
and unambiguous connection to the physical phenomena under observation…” ([7],
p. 2, column 2). Worse, “…adding labels to the state artificially increases
the uncertainty in the tracking problem…” ([7], p. 3, top of column 1).

The remedy that has been proposed is as follows: Replace the LRFS framework
with an allegedly label-free “trajectory random finite set” (TRFS) framework.
That is, replace the time-sequence $X_{1},...,X_{k}$ with a finite “set of
trajectories” (SoT) $\mathbf{T}=\\{T_{1},...,T_{n}\\}$ where each “trajectory”
$T_{k}$ is a vector of the form

$T_{k}=(t_{k},\mathbf{x}^{1:i})\overset{{}_{\text{abbr.}}}{=}((t_{k},\mathbf{x}^{1}),(t_{k+1},\mathbf{x}^{2}),...,(t_{k+i-1},\mathbf{x}^{i}))$
(1)

where $t_{k}$ and $t_{k+i-1}$ are the trajectory’s beginning and end times and
where
$\mathbf{x}^{1:i}:\mathbf{x}^{1},\mathbf{x}^{2},...,\mathbf{x}^{i}\in\mathfrak{X}_{0}$
are its respective kinematic states at those times.

The purpose of this paper is to substantiate the following claims:

  1. 1.

These criticisms of the LRFS framework are mistaken;

  2. 2.

the TRFS framework itself has no direct and unambiguous connection to the
physical phenomena under observation; and

  3. 3.

it itself seriously increases uncertainty in the tracking problem.

The analysis that follows will begin with phenomenological and epistemological
basics—specifically, with the basic semiotic concepts of signified (an entity)
versus signifier (a name for that entity in some symbolic language). It will
be shown, step-by-step, that the LRFS framework arises inevitably from the
phenomenological requirements of the multitarget tracking application. It will
then be shown that the TRFS framework arises by stripping from the LRFS
framework the signifiers (labels) that signify actual physical phenomena—i.e.,
the unique identities that real-world targets actually possess. Stated more
forthrightly:

  1. $\bullet$

Jettisoning the signifier (the label and the information that it carries)
effectively throws the baby (the unique target that it signifies) out with the
bathwater.

The remainder of the paper is organized as follows: mathematical
representation of targets (Section II); mathematical representation of target
trajectories (Section III); and conclusions (Section IV).

In what follows, $\mathbb{N}=\\{0,1,2,...\\}$ denotes the natural numbers;
$\mathbb{N}^{+}=\\{1,2,...\\}$ the nonzero natural numbers; $\mathbb{R}^{+}$
the positive real numbers; and $\delta_{i,j}$ the Kronecker delta.

##  II Mathematical Representation of Targets

The section is organized as follows: mathematical representation of target
kinematics (Section II-A); mathematical representation of target identity
(Section II-B); and mathematical representation of multitarget states (Section
II-C).

###  II-A Mathematical Representation of Target Kinematics

A target is a macroscopic physical entity. This means in particular that it
has a position, which is typically mathematically idealized as a unique point
in three-dimensional Euclidean space. A point position must be designated by
some sort of symbolic identifier—a “signifier,” in the patois of semiotics.
This signifier is not—indeed, cannot be—unique. It typically consists of a
triplet of real numbers (continuous state variables) in some coordinate system
(Cartesian, cylindrical, spherical, etc.) centered at some origin point
(geocentric, etc.), each variable having a unit of measurement (metric,
English, etc.), and the value of each variable being expressed in terms of
some number-system base (decimal, binary, hexadecimal, etc.).

Two points should be emphasized:

  1. 1.

The arbitrariness of a position signifier does not negate the reality,
physicality, or uniqueness of the position that it signifies; and the same is
true of any other kinematic state variable.

  2. 2.

The existence of an infinitude of possible signifiers for a position does not
contravene the usual requirement that there be a one-to-one correspondence
between physical states and their mathematical representations. For position
(or any other kinematic state variable), it is enough that this correspondence
exists once the following have been selected: number base, measurement units,
coordinate system origin, and coordinate system.

###  II-B Mathematical Representation of Target Identity

As a macroscopic physical entity, a target has a discrete-valued state
variable—its unique identity—which must be assigned some appropriate
signifier. As with position, this signifier cannot be unique. For example, it
can be (in the case of people) a social security number or a name such as “Bob
Aardvark” or “Sue Zebra”; or (in the case of aircraft) a tail number or a
manufacturers’ serial number.

The arbitrariness of this signifier does not preclude the reality,
physicality, or uniqueness of the target identity which it signifies. And the
infinitude of possible identity-signifiers does not violate the one-to-one
correspondence principle. Since the number of target identities is finite but
usually unknown, it is enough that such a correspondence exists once a
countable set of identity-signifiers has been chosen.

When the actual identity of a physical object is unknown, it can be assigned a
tentative identifier—for example, a “track label.” Neither the provisionality
nor the infinitude of possible such labels means that they are “artificial
variables…added to the target states” ([9], p. 1884). Rather, they are stand-
ins for the unique identities of actual physical objects and, as such, are no
more “artificial” than any other signifier for those objects. To claim
otherwise is to implicitly claim that (for example) target-classifier
algorithms—which estimate the types or even identities of physical targets—are
“non-physical.”

###### Remark 1

“Target types” or “target classes” are signifiers that are less accurate than
identities but typically more accurate than labels. As noted in [8], p. 259,
Remark 33, they—unlike identities—are not necessarily time-invariant because
some targets can have multiple, distinct phenomenological “modes.” Typical
examples include: variable swept-wing aircraft (extended-wing vs. delta-wing);
mobile missile launchers (launch-ready vs. transiting); and diesel-electric
submarines (surfaced vs. submerged). This complication can be addressed within
the RFS/LRFS framework but will not be further addressed in this paper.

These points having been made, we are now in a position to address the
theoretically and phenomenologically correct mathematical representation of
time-evolving multitarget populations.

###  II-C Mathematical Representation of Multitarget States

As noted earlier, the state of a point target at a particular instant has the
mathematical form
$\xi=(\mathbf{x},\ell)\in\mathfrak{X}=\mathfrak{X}_{0}\times\mathfrak{L}$
where $\mathbf{x}\in\mathfrak{X}_{0}$ is its kinematic state (position,
velocity, orientation, etc.) and $\ell\in\mathfrak{L}$ is a provisional
identifying label drawn (without replacement) from a countable set
$\mathfrak{L}$ of such labels.

This, in turn, means that it is impossible for a target population to contain
pairs $(\mathbf{x},\ell)$, $(\mathbf{y},\ell)$ with $\mathbf{x}\neq\mathbf{y}$
since, then (for example) “Bob” could be in two different places
simultaneously. Nor can it contain pairs $(\mathbf{x},\ell)$,
$(\mathbf{x},\ell)$, since then two copies of (for example) “Bob” could exist
simultaneously. Consequently, the state of a target population must must be a
collection
$\xi_{1}=(\mathbf{x}_{1},\ell_{1}),...,\xi_{n}=(\mathbf{x}_{n},\ell_{n})$
where the kinematic states have distinct labels—i.e.,

$\
|\\{(\mathbf{x}_{1},\ell_{1}),...,(\mathbf{x}_{n},\ell_{n})\\}|=|\\{\ell_{1},...,\ell_{n}\\}|=n.$
(2)

This collection does not have a natural ordering—e.g., is “Bob” greater or
less than “Sue”? Thus $\xi_{1},...,\xi_{n}$ must have the mathematical form
$\\{\xi_{1},...,\xi_{n}\\}\subseteq\mathfrak{X}_{0}\times\mathfrak{L}$—i.e., a
finite set—and not
$(\xi_{1},...,\xi_{n})\in(\mathfrak{X}_{0}\times\mathfrak{L})^{n}$—i.e., a
vector.

There are three additional reasons why vectors are theoretically inappropriate
representations of multitarget populations ([10], Section 2.4).

  1. 1.

Statistical Bias. Imposing nonphysical information on a physical system can
create a statistical bias. The most obvious such biases are deliberate—e.g.,
forcing a multitarget tracker-classifier to prioritize targets of interest
(ToI’s), e.g., “Bob” is tactically more threatening than “Sue.” The concept of
ToI is subjective and contextual, not physical. Forcing it upon a target
population results in a nonphysical statistical bias in favor of more
tactically significant ToI’s. Similarly, physical targets do not have a
natural ordering. Forcing one upon a population (as with vector
representation) runs the risk of introducing an unknown statistical bias. (In
the TRFS framework, target ordering is also viewed as “non-physical,” see [7],
Abstract.)

  2. 2.

Uniqueness of States. There should be a one-to-one correspondence between
physical states and their mathematical representations. Because physical
states have no inherent ordering, there are $n!$ possible vector
representations $\vec{\xi}_{\pi}=(\xi_{\pi 1},...,\xi_{\pi n})$ of the same
multitarget population $\xi_{1},...,\xi_{n}$, for permutations $\pi$ on
$1,...,n$. There is no way to choose one particular permutation as a
representative, without implicitly assuming that the targets have a specific
ordering.

  3. 3.

Performance Evaluation. Multitarget tracking algorithms are multitarget state
estimators. Performance evaluation of such algorithms requires the existence
of a mathematical metric on multitarget states, in order to measure the
distance between the ground truth state and any given estimated state.
However, no such distance metric exists for vector representation. Assume the
contrary: a metric $d(\vec{\xi}_{1},\vec{\xi}_{2})$. Then if $\pi$ is not the
identity permutation, $\vec{\xi}_{\pi}\neq\vec{\xi}$ and yet
$d(\vec{\xi}_{\pi},\vec{\xi})=d(\vec{\xi},\vec{\xi})=0$, which contradicts the
definition of a mathematical metric on multitarget states.

###### Remark 2

In objection to Item 1, it could be argued that the GLMB filter’s labeling
scheme is vulnerable to possible statistical bias. This is not the case. As
will be noted in Section III-A, this scheme assigns labels of the form
$\ell_{1}=(k,1),...,\ell_{n_{k}}=(k,n_{k})$ where $t_{k}$ is the time that an
ensemble of $n_{k}$ targets appeared and where the natural numbers
$1,2,...,n_{k}$ distinguish those targets from each other. But here is the
crucial point: It is not assumed that the list $1,...,n$ (and therefore also
$\ell_{1},...,\ell_{n_{k}}$) is ordered. The theoretical foundation of modern
mathematics is Cantor’s set theory, whose primitive concept is the set.
Vectors must therefore be defined in terms of sets. The simplest such
definition is as follows: $(x_{1},...,x_{n})$ is a finite set
$\\{(x_{1},1),...,(x_{n},n)\\}$ that has been endowed with the ordering
relation $(x_{i},i)<(x_{j},j)$ if and only if $i<j$. If no such relation has
been stipulated (as in the GLMB scheme) then the list $1,...,n$ (and therefore
also $\ell_{1},...,\ell_{n_{k}}$) has no inherent ordering. Indeed, Greek
letters, or any other arbitrary symbols in any order, could have been used
instead. A vector representation, on the other hand, is not possible unless
precisely this ordering relation has been explicitly imposed on the collection
$x_{1},...,x_{n}$.

##  III Mathematical Representation of Trajectories

As noted in the Introduction, two mathematical representations of evolving
multitarget populations have been proposed: labeled RFS’s (LRFS’s) and
trajectory RFS’s (TRFS’s). The purpose of this section is to summarize and
contrast the two. It is organized as follows: LRFS’s (Section III-A); TRFS’s
(Section III-B); comparison of LRFS’s and TRFS’s (Section III-C);
counterexamples (Section III-D); and the trajectory PHD/CPHD filters (Section
III-E).

###  III-A Labeled RFS’s

From its inception in 1997, the RFS approach has included uniquely identifying
target identities or labels as target state variables—see [11], pp.135,196-197
and [3], pp. 505-507. Because of computational considerations, however, the
first implementations of RFS filters mostly did not address track labeling;
and, when they did, employed computationally expensive techniques such as
track-to-track association. Later implementations (for example, those based on
Gaussian mixture or particle-system approximation) addressed trajectories in a
computationally tractable manner via heuristic label-propagation schemes—see,
e.g., [8], p. 244-250.

The labeled RFS (LRFS) theory of B.-T. Vo and B.-N. Vo [5], introduced in 2011
[4], is the first systematic, theoretically rigorous formulation of true
multitarget tracking. Their provably Bayes-optimal GLMB filter is the
currently most sophisticated LRFS tracking algorithm. As previously noted, its
latest implementations can simultaneously track over one million targets in
significant clutter in real time using off-the-shelf computing equipment [6].

This section summarizes LRFS theory, following the discussion in Chapter 15 of
[8].

As in [11], pp.135,196-197, the state of a point target is
$(\mathbf{x},\ell)\in\mathfrak{X}=\mathfrak{X}_{0}\times\mathfrak{L}$ where
$\mathfrak{X}_{0}$ is the kinematic state space and $\mathfrak{L}$ is a
countable space of labels $\ell$. As was noted in Remark 2, GLMB filter labels
have the form $(k,i)$ where $k\geq 0$ denotes the time $t_{k}$ that the target
first appeared and where $i\geq 1$ distinguishes it from all others born at
the same time. As noted in [12], labels can be extended to contain target-type
or target-identity information, thus permitting simultaneous target tracking
and classification/identification.

A finite subset
$X=\\{(\mathbf{x}_{1},\ell_{1}),...,(\mathbf{x}_{n},\ell_{n})\\}\subseteq\mathfrak{X}$
is said to be labeled if $|X_{\mathfrak{L}}|=|X|$ where
$X_{\mathfrak{L}}=\\{\ell_{1},...,\ell_{n}\\}$ is its set of labels. That is:
every target is assumed to have a unique identifying label. If all
instantiations of an RFS $\Xi\subseteq\mathfrak{X}$ are labeled, then $\Xi$ is
an LRFS.

###### Remark 3

Note that labeled sets are allowed to contain pairs of the form
$(\mathbf{x},\ell_{1})$, $(\mathbf{x},\ell_{2})$ with $\ell_{1}\neq\ell_{2}$.
This is not a conceptual flaw. It is physically possible, for example, for two
or more targets traveling in formation to be so close together that, within
the resolution of the sensor, they appear to have identical kinematic states
over an extended duration of time. Additionally, because point targets are
mathematical idealizations that do not have a physical extent, it is possible
for two different point targets to (for example) have the same position.

Bayes-optimal multitarget tracking is accomplished via the labeled multitarget
recursive Bayes filter

$...\rightarrow f_{k-1}(X|Z_{1:k-1})\rightarrow f_{k}(X|Z_{1:k-1})\rightarrow
f_{k}(X|Z_{1:k})\rightarrow...$

where $Z_{1:k}:Z_{1},...,Z_{k},...$ is the time-sequence of measurement-sets
collected by a single sensor at times $t_{1},...,t_{k},...$ and
$f_{k}(X|Z_{1:k})$ is a probability distribution on
$X\subseteq\mathfrak{X}_{0}\times\mathfrak{L}$. It must be the case that
$f_{k}(X|Z_{1:k})=0$ if $X$ is not labeled—i.e., if $X$ is physically
impossible. Stated differently, $f_{k}(X|Z_{1:k})$ is an “LRFS distribution.”
Since targets evolve in four-dimensional space-time, their states have the
form
$(\mathbf{x},\ell,t)\in\mathfrak{X}=\mathfrak{X}_{0}\times\mathfrak{L}\times\mathbb{R}^{+}$
where $t$ is a known constant. Since time is assumed to belong to a discrete
sequence $t_{1},...,t_{k},...$, abbreviate $(\mathbf{x},\ell,t_{k})$ as
$(\mathbf{x},\ell,k)\in\mathfrak{X}_{0}\times\mathfrak{L}\times\mathbb{N}$.

The labeled multi-Bernoulli (LMB) distribution is a simple example of an LRFS
distribution. It has the form

$\displaystyle f_{J}(X)$ $\displaystyle=$
$\displaystyle\delta_{|X|,|X_{\mathfrak{L}}|}\left(\prod_{\ell\in
J-X_{\mathfrak{L}}}(1-q_{\ell})\right)\left(\prod_{(\mathbf{x,}\ell)\in
X}\mathbf{1}_{J}(\ell)\cdot q_{\ell}s_{\ell}(\mathbf{x})\right)$

where $J$ is a finite subset of $\mathfrak{L}$; and where $q_{\ell}$ and
$s_{\ell}(x)$ are, respectively, the existence probability and spatial
distribution of the target with label $\ell\in J$. Note that $f_{J}(X)=0$
unless $|X|=|X_{\mathfrak{L}}|$ and $X_{\mathfrak{L}}\subseteq J$.

At time $t_{k}$, the multitarget state-set is estimated from
$f_{k}(X|Z_{1:k})$ using a Bayes-optimal multitarget state estimator, e.g.,
the joint multitarget (JoM) or marginal multitarget (MaM) estimator—see [3].
If

$\hat{X}^{k}=\\{(\mathbf{\hat{x}}_{k}^{1},\hat{\ell}_{k}^{1},k),...,(\mathbf{\hat{x}}_{k}^{\hat{n}_{k}},\hat{\ell}_{k}^{\hat{n}_{k}},k)\\}$

with $|\hat{X}^{k}|=\hat{n}_{k}$ then, at time $t_{k}$, $\hat{n}_{k}$ is the
estimated number of targets and
$\hat{\ell}_{k}^{1},...,\hat{\ell}_{k}^{\hat{n}_{k}}$ are their estimated
labels. If $\hat{X}^{1},...,\hat{X}^{k}$ is the time-sequence of multitarget
state-estimates from time $t_{1}$ to time $t_{k}$, define

$\hat{X}_{\ell}^{i}=\left\\{\begin{array}[]{ccc}\\{(\mathbf{x},\ell,i)\\}&\text{if}&(\mathbf{x},\ell,i)\in\hat{X}^{i}\text{
\ for some \ }\mathbf{x}\in\mathfrak{X}_{0}\\\
\emptyset&\text{if}&\text{otherwise}\end{array}\right..$ (4)

The $\ell$-trajectory (a.k.a. $\ell{}$-track) is the time-sequence
$\hat{X}_{\ell}^{1}...,\hat{X}_{\ell}^{k},...$ of singleton or empty sets
(which thereby accounts for the acquisition, dropouts, and reacquisitions of
the target with label $\ell$). The time-consecutive nonempty subsequences of
an $\ell$-trajectory are its track segments.

It follows that, in the LRFS framework, a track segment can be represented as
a vector of the form

$\left((\mathbf{x}^{1},\ell,k),(\mathbf{x}^{2},\ell,k+1),...,(\mathbf{x}^{i},\ell,k+i-1)\right)$

where $t_{k}$ is the segment’s initial time, $i\geq 1$ is its length, and
$\mathbf{x}^{1},...,\mathbf{x}^{i}$ are its kinematic states at times
$t_{k},...,t_{k+i-1}$.

Now let “$A\approx B$” abbreviate the phrase “$A$ is notationally equivalent
to $B$” (in the sense that $\ A$ and $B$ are characterized by the same
parameters). Then we can successively re-notate the track segment as follows:

$\displaystyle\left((\mathbf{x}^{1},\ell,k),(\mathbf{x}^{2},\ell,k+1),...,(\mathbf{x}^{i},\ell,k+i-1)\right)$
$\displaystyle\approx$
$\displaystyle(\ell,(\mathbf{x}^{1},k),(\mathbf{x}^{2},k+1),...,(\mathbf{x}^{i},k+i-1))$
$\displaystyle\approx$
$\displaystyle(\ell,k,\mathbf{x}^{1},\mathbf{x}^{2},...,\mathbf{x}^{i})$
$\displaystyle\approx$ $\displaystyle(\ell,k,\mathbf{x}^{1:i}).$

That is: the track segment can be equivalently notated as
$T_{\ell}=(\ell,k,\mathbf{x}^{1:i})$ where $0\leq k\leq k_{\max}$ and $1\leq
i\leq k_{\max}-k+1$; and where $t_{k_{\max}}$ is the end-time of the scenario.

###  III-B Trajectory Random Finite Sets

The TRFS framework was introduced in 2014 in [7] and subsequently elaborated
in [13], [14], [15], [16], and [17]. There it was claimed that LRFS labels are
deficient because:

  1. 1.

they are “non-physical” ([7], Abstract);

  2. 2.

they have ”…no direct and unambiguous connection to the physical phenomena
under observation…” ([7], p. 2, column 2);

  3. 3.

they “…do…not represent an underlying physical reality…” ([7], p. 3, top of
column 1); and

  4. 4.

a “…multitude of labeling [sic] can be developed…[but] there is no general way
of distinguishing the merits of a given scheme…”; which “…contravene[s]…the
usual notion of there being a ‘one-to-one correspondence between physical
states and their mathematical representations’…” ([7], p. 2, column 2), here
citing p. 405 of [3].

In addition, it was claimed in [7] that the example in Figure 2 of four
slightly different scenarios with “…two targets approaching on the real line,
pausing and then separating illustrates the appeal of using RFS trajectories
[rather than labels]…” ([7], column 1).

“Trajectory random finite sets” (TRFS’s) were therefore proposed as a
replacement for LRFS’s. As described in pp. 1-2 of [13], a “trajectory” is
what we earlier called a track segment. It has the form
$T=(k,\mathbf{x}^{1:k})$ where $0\leq k\leq k_{\max}$ is the trajectory’s
initial time, $1\leq i\leq k_{\max}-k+1$ is its length, and
$\mathbf{x}^{1},...,\mathbf{x}^{i}$ are its kinematic states at times
$t_{k},...t_{k+i-1}$. A finite set of trajectories (SoT) is, therefore,
$\mathbf{T}=\\{T_{1},...,T_{n}\\}$ where $T_{1},...,T_{n}$ are trajectories. A
TRFS is a random variable on the class of SoT’s.

It was also claimed that the TRFS approach subsumes the LRFS approach as a
special case because
$\mathbf{T}=\\{(k,\mathbf{x}_{1}),...,(k,\mathbf{x}_{n})\\}$ is an equivalent
representation of a set $X_{k}=\\{\mathbf{x}_{1},...,\mathbf{x}_{n}\\}$ of
targets at time $t_{k}$.

The TRFS framework subsequently provided the basis for the trajectory PHD
(TPHD) filter [13]; the trajectory CPHD (TCPHD) filter [14]; and the
“trajectory Poisson multi-Bernoulli mixture trajectory filter” [16], [17]. The
trajectory PHD and CPHD filters will be discussed in detail in Section III-E.

###  III-C Comparison of the LRFS and TRFS Frameworks

The four enumerated criticisms of the LRFS framework in the previous section
have already been rebutted in Section II-B. To reiterate: Neither the
provisionality nor the infinitude of track labels means that they are “non-
physical.” Rather, they are stand-ins for the unique identities of actual
physical objects. As such, they are no more non-physical than any other
signifier for those objects.

As for the argument relating to Figure 2 of [7], it appears to involve an
apples-with-oranges comparison. It was implicitly assumed there that the four
trajectories were all being considered as entireties—that is, the four
scenarios ended before measurement processing commenced. However, it is well
known that a smoother algorithm will typically outperform a filter algorithm,
because the former processes both past and future measurements whereas the
latter can process past measurements only. Stated differently, the smoother is
a batch-processing algorithm whereas the filter cannot discern the future and
thus is, in this sense, “real-time.” TRFS algorithms, such as the TPHD and
TCPHD filters discussed in Section III-E, are also of the smoother type since,
at any given time $t_{k}$, all trajectories prior to $t_{k}$ must be taken
into consideration.

It might thereby be argued that the TRFS framework is still valid within the
context of multitarget smoothing. But as we will shortly see, this is not the
case.

Let us now turn to a more detailed comparison of the LRFS and TRFS frameworks.
In the former, a “trajectory” (track segment) has the form
$T_{\ell}=(\ell,k,\mathbf{x}^{1:i})$; whereas in the latter it has the form
$T=(k,\mathbf{x}^{1:i})$. Since a SoT has the form
$\mathbf{T}=\\{T_{1},...,T_{n}\\}$, it must therefore be the case that
$T_{j}=(k_{j},\mathbf{x}_{j}^{1:i_{j}})$ for some $k_{j}$, $i_{j}$, and
$\mathbf{x}_{j}^{1},...,\mathbf{x}_{j}^{i_{j}}$.

That is: the trajectory $T_{j}$ has been implicitly assigned the integer label
$j$—which is then ignored (“stripped off”). But as was noted in Section II-B,
when the signifier of an entity is jettisoned, critical information about it
is jettisoned as well. As the following subsection demonstrates, this loss of
information results in numerous and serious difficulties.

###  III-D Counterexamples

Counterexample 1: The LRFS framework is not a special case of the TRFS
framework. Let $\mathbf{T}=\\{(k,\mathbf{x}_{1}),...,(k,\mathbf{x}_{n})\\}$
with $\mathbf{x}_{1},...,\mathbf{x}_{n}$ distinct. Then this is mathematically
equivalent to the LRFS representation
$X_{k}=\\{(1,k,\mathbf{x}_{1}),...,(n,k,\mathbf{x}_{n})\\}$. From this one
might conclude that the TRFS framework includes the LRFS framework as a
special case. But this is not so. In Remark 3 it was noted that a labeled set
of the form $X=\\{(\mathbf{x},\ell_{1}),(\mathbf{x},\ell_{2})\\}$ with
$\ell_{1}\neq\ell_{2}$ is possible. Thus consider the case
$\mathbf{x}_{1}=...=\mathbf{x}_{n}=\mathbf{x}$, in which case
$\mathbf{T}=\\{(k,\mathbf{x})\\}$ whereas
$X_{k}=\\{(1,k,\mathbf{x}),...,(n,k,\mathbf{x})\\}$ is a valid labeled finite
set. That is: there is no way to represent such labeled multitarget states in
the TRFS framework. And this is not the only possible such anomaly—see
Counterexample 3.

Counterexample 2: Contrary to claim, the TRFS framework contravenes the usual
notion of there being a one-to-one correspondence between physical states and
their mathematical representations. Consider $\mathbf{T}_{0}=\\{T_{0}\\}$ and
$\mathbf{T}_{1}=\\{T_{1},T_{2},T_{3}\\}$ where
$T_{0}=(k,\mathbf{x},\mathbf{x}^{1},\mathbf{x}^{2})$, $T_{1}=(k,\mathbf{x})$,
$T_{2}=(k+1,\mathbf{x}^{1})$, $T_{3}=(k+2,\mathbf{x}^{2})$. Then because
$(k,\mathbf{x},\mathbf{x}^{1},\mathbf{x}^{2})$ is an abbreviation of
$((k,\mathbf{x}),(k+1,\mathbf{x}^{1}),(k+2,\mathbf{x}^{2}))$, it follows that
$\mathbf{T}_{0}$ and $\mathbf{T}_{1}$ are mathematically distinct
representations of the same physical trajectory $(k,\mathbf{x})$,
$(k+1,\mathbf{x}^{1})$, $(k+2,\mathbf{x}^{2})$. Now restore the implicit
labels that have been stripped off:
$T_{0}=(0,k,\mathbf{x},\mathbf{x}^{1},\mathbf{x})$, $T_{1}=(1,k,\mathbf{x})$,
$\ T_{2}=(2,k+1,\mathbf{x}^{1})$, $T_{3}=(3,k+2,\mathbf{x}^{2})$. Then the
difficulty vanishes because $\mathbf{T}_{0}$ represents the trajectory of a
single physical target with label $0$; whereas $\mathbf{T}_{1}$ represents the
trajectories of three successively appearing and disappearing targets with
respective labels $1$, $2$, $3$.

Counterexample 3: Impossible scenarios can be represented in the TRFS
framework even while valid ones cannot. Consider
$\mathbf{T}_{2}=\\{T_{1},T_{2}\\}$ where $T_{1}=(k,\mathbf{x},\mathbf{x}^{1})$
and $T_{2}=(k,\mathbf{x},\mathbf{x}^{2})$ with
$\mathbf{x},\mathbf{x}^{1},\mathbf{x}^{2}$ distinct. Then $\mathbf{T}_{2}$ is
physically impossible since a single target $\mathbf{x}$ at time $t_{k}$
cannot evolve to two different states $\mathbf{x}^{1}$ and $\mathbf{x}^{2}$ at
time $t_{k+1}$. Now restore the stripped labels:
$T_{1}=(1,k,\mathbf{x},\mathbf{x}^{1})$, $\
T_{2}=(2,k,\mathbf{x},\mathbf{x}^{2})$. Then $\mathbf{T}_{2}$ represents a
target separation (e.g., a target-spawning event): targets $1,2$ had identical
states $\mathbf{x}$ at time $t_{k}$, at which point they separated and evolved
respectively to $\mathbf{x}^{1}$ and $\mathbf{x}^{2}$ at time $t_{k+1}$.

Counterexample 4: Contrary to claim, stripping labels from states increases
tracking uncertainty. Consider $\mathbf{T}_{3}=\\{T_{1},T_{2}\\}$ where
$T_{1}=(k,\mathbf{x}^{1:5})$ and $T_{2}=(k+10,\mathbf{y}^{1:5})$. Then there
is an ambiguity: Does $\mathbf{T}_{3}$ represent a single dropped and then
reacquired track, or two successively appearing and disappearing tracks? This
ambiguity is resolved if we restore stripped labels: either
$T_{1}=(1,k,\mathbf{x}^{1:5})$ and $T_{2}=(1,k+10,\mathbf{x}^{1:5})$ (if
restored to a single reacquired track) or $T_{1}=(1,k,\mathbf{x}^{1:5})$ and
$T_{2}=(2,k+10,\mathbf{y}^{1:5})$ (if restored to two consecutive tracks).

###  III-E Trajectory PHD and CPHD Filters

These are not the only difficulties with the TRFS framework. As noted earlier,
the TPHD/TCPHD filters were introduced in [13] and [15], [14], respectively.
The purpose of this subsection is to demonstrate that they are theoretically
problematic. It is organized as follows: C/PHD filters (Section III-E1);
multitarget state estimation for C/PHD filters (Section III-E2); the TPHD
filter (Section III-E3); multitarget state estimation for the TPHD filter
(Section III-E4); and the theoretical basis of the TPHD filter (Section
III-E5).

####  III-E1 The C/PHD Filters

The conventional PHD filter [3] has the form

$...\rightarrow D_{k-1}(\mathbf{x}|Z_{1:k-1})\rightarrow
D_{k}(\mathbf{x}|Z_{1:k-1})\rightarrow
D_{k}(\mathbf{x}|Z_{1:k})\rightarrow...$

Here, $D_{k}(\mathbf{x}|Z_{1:k})$ with $\mathbf{x}\in\mathfrak{X}_{0}$ is the
first-order statistical moment (a.k.a. PHD or “intensity density”) of
$f_{k}(X|Z_{1:k})$ with $X\subseteq\mathfrak{X}_{0}$, which in turn is assumed
to be the distribution of a Poisson RFS with PHD $D_{k}(\mathbf{x}|Z_{1:k})$.

The CPHD filter [3] propagates the cardinality distribution $p_{k}(n|Z_{1:k})$
(i.e., the probability that there are $n$ targets present at time $t_{k}$) in
addition to the PHD $D_{k}(\mathbf{x}|Z_{1:k})$. It is based on i.i.d.c. RFS’s
(which are generalizations of Poisson RFS’s).

###### Remark 4

Poisson RFS’s on $\mathfrak{X}_{0}\times\mathfrak{L}$ are not LRFS’s because
their distributions have the form

$f(X)=e^{-\sum_{\ell}\int
D(\mathbf{x},\ell)d\mathbf{x}}\prod_{(\mathbf{x},\ell)\in
X}D(\mathbf{x},\ell).$ (5)

Suppose that $Y=\\{(\mathbf{x}_{1},\ell),(\mathbf{x}_{2},\ell)\\}$ for some
$\mathbf{x}_{1}\neq\mathbf{x}_{2}$ such that $\ D(\mathbf{x}_{1},\ell)>0$,
$D(\mathbf{x}_{2},\ell)>0$. Then $Y$ is physically impossible since $|Y|=2\neq
1=|Y_{\mathfrak{L}}|$. Yet $f(Y)\propto D(\mathbf{x}_{1},\ell)\cdot
D(\mathbf{x}_{2},\ell)\neq 0$—i.e., $f(X)$ is not an LRFS distribution.

####  III-E2 Multitarget State Estimation for the PHD Filter

This proceeds as follows. First, compute

$\bar{N}_{k}=\int D_{k}(\mathbf{x}|Z_{1:k})d\mathbf{x,}$ (6)

which is the expected number of targets in the multitarget population at time
$t_{k}$. Second, round $\bar{N}_{k}$ off to the nearest integer $\hat{n}_{k}$.
Third, determine the states
$\mathbf{\hat{x}}_{1},...,\mathbf{\hat{x}}_{\hat{n}_{k}}$ such that
$D_{k}(\mathbf{\hat{x}}_{1}|Z_{1:k})$,…,$D_{k}(\mathbf{\hat{x}}_{\hat{n}_{k}}|Z_{1:k})$
are the heights of the $\hat{n}_{k}$ tallest “peaks” of the graph of the
function $D_{k}(\mathbf{x}|Z_{1:k})$.

State estimation for the CPHD filter differs only in that

$\hat{n}_{k|k}=\arg\sup_{n\geq 0}p_{k}(n|Z_{1:k}).$ (7)

####  III-E3 The TPHD Filter

In [13] it was claimed that the PHD filter can be directly generalized from
RFS’s to TRFS’s. This “trajectory PHD filter” (TPHD filter) has the form

$...\rightarrow\vec{D}_{k-1}(T|Z_{1:k-1})\rightarrow\vec{D}_{k}(T|Z_{1:k-1})\rightarrow\vec{D}_{k}(T|Z_{1:k})\rightarrow...$

where (in the case of $\vec{D}_{k}(T|Z_{1:k})$)
$T=(k^{\prime},\mathbf{x}^{1:i})$ for all $0\leq k^{\prime}\leq k$, $1\leq
i\leq k-k^{\prime}+1$, and $\mathbf{x}^{1:i}\in\mathfrak{X}^{i}$. This means
that all trajectories prior to time $t_{k}$—i.e., all
$(k^{\prime},\mathbf{x}^{1:i})$ with $0\leq k^{\prime}\leq k-1$ and $1\leq
i\leq k-k^{\prime}$—must be taken into consideration. Consequently,
calculation of the TPHD $\vec{D}_{k}(T|Z_{1:k})$ for all $T$ is significantly
more computationally intensive than calculation of the corresponding PHD
$D_{k}(\mathbf{x}|Z_{1:k})$ for all $\mathbf{x}$.

####  III-E4 Multitarget State Estimation for the TPHD Filter

This is claimed to have exactly the same form as before, i.e.: (a) compute
([13], Eq. (1))

$\displaystyle\bar{N}_{k}$ $\displaystyle=$
$\displaystyle\int\vec{D}_{k}(T|Z_{1:k})dT$ (8) $\displaystyle=$
$\displaystyle\sum_{k^{\prime}=0}^{k}\sum_{i=1}^{k-k^{\prime}+1}\vec{D}_{k}(k^{\prime},\mathbf{x}^{1:i}|Z_{1:k})d\mathbf{x}^{1:i};$
(9)

(b) round off $\bar{N}_{k}$ to $\hat{n}_{k}$; and (c) determine the locations
$\hat{T}_{1},...,\hat{T}_{\hat{n}_{k}}$ of the $\hat{n}_{k}$ largest peaks of
the graph of $\vec{D}_{k}(T|Z_{1:k})$.

This TPHD/TCPHD estimation procedure is mathematically undefined. For, let
$\iota$ be the unit of measurement of the single-target state space
$\mathfrak{X}$. Then the unit of measurement of a trajectory
$(k^{\prime},\mathbf{x}^{1:i})$ is $\iota^{i}$ and so the unit of
$\vec{D}_{k}(k^{\prime},\mathbf{x}^{1:i}|Z_{1:k})$ is $\iota^{-i}$. Because it
is impossible to numerically compare
$\vec{D}_{k}(k^{\prime},\mathbf{x}^{1:i}|Z_{1:k})$ to
$\vec{D}_{k}(k^{\prime\prime},\mathbf{x}^{1:i^{\prime}}|Z_{1:k})$ when $i\neq
i^{\prime}$, it is impossible to determine
$\hat{T}_{1},...,\hat{T}_{\hat{n}_{k}}$.

This remains true when the TPHD/TPHD filters are implemented using Gaussian
mixture approximations. These have the form ([13], Eqs. (16,17)):

$\vec{D}_{k}(k^{\prime},\mathbf{x}^{1:i})\cong\sum_{j=1}^{N_{k}}w_{k,j}\cdot\vec{N}_{\vec{P}_{k,j}^{1:i}}((k^{\prime},\mathbf{x}^{1:i});(k_{k,j}^{\prime},\mathbf{x}_{k,j}^{1:i_{k,j}}))$
(10)

where $w_{k,j}\geq 0$; where

$\vec{N}_{\vec{P}_{0}^{1:i_{0}}}((k^{\prime},\mathbf{x}^{1:i});(k_{0},\mathbf{x}_{0}^{1:i_{0}}))=\delta_{k^{\prime},k_{0}}\delta_{i,i_{0}}\cdot
N_{\vec{P}_{0}^{1:i_{0}}}(\mathbf{x}^{1:i_{0}}-\mathbf{x}_{0}^{1:i_{0}})$ (11)

is a probability distribution on trajectories
$T=(k^{\prime},\mathbf{x}^{1:i})$; and where
$N_{\vec{P}_{0}^{1:i}}(\mathbf{x}^{1:i})$ denotes a zero-mean Gaussian
distribution in the variable
$\mathbf{x}^{1:i}=(\mathbf{x}^{1},...,\mathbf{x}^{i})$ with covariance matrix
$\vec{P}_{0}^{1:i}$.

We may assume that $w_{k,j}>0$ for all $j$, which forces $i_{k,j}=i$ for all
$j$ if the summation in (10) is to be mathematically well-defined. Thus at its
most general, the GM in (10) must have the form

$\vec{D}_{k}(k^{\prime},\mathbf{x}^{1:i})\cong\bar{N}_{k}\sum_{j=1}^{N_{k}}w_{k,k^{\prime},i,j}\cdot\vec{N}_{\vec{P}_{k,j}^{1:i}}(\mathbf{x}^{1:i}-\mathbf{x}_{k,k^{\prime},i,j}^{1:i})$
(12)

where $\bar{N}_{k}>0$ and where $w_{k,k^{\prime},i,j}>0$ are such that

$\sum_{k^{\prime}=0}^{k}\sum_{i=1}^{k-k^{\prime}+1}\sum_{j=1}^{N_{k}}w_{k,k^{\prime},i,j}=1,$
(13)

from which follows $\int\vec{D}_{k}(T)dT\cong\bar{N}_{k}$. Since
$\vec{D}_{k}(k^{\prime},\mathbf{x}^{1:i})$ and
$\vec{D}_{k}(k^{\prime\prime},\mathbf{x}^{1:i^{\prime}})$ are numerically
incommensurable when $i\neq i^{\prime}$, it follows that the inequality
$w_{k,k^{\prime},i,j}>w_{k,k^{\prime\prime},i^{\prime},j^{\prime}}$ cannot
compel us to conclude that GM component $\mathbf{x}_{k,k^{\prime},i,j}^{1:i}$
has a higher “peak” than GM component
$\mathbf{x}_{k,k^{\prime\prime},i^{\prime},j^{\prime}}^{1:i^{\prime}}$. That
is: it is not true that “…the estimated set of trajectories corresponds to…the
components with highest weights…” (as was asserted in regard to Eq. (21) of
[13]).

####  III-E5 Theoretical Basis of the TPHD Filter

The TPHD filter is inherently theoretically erroneous because it requires
“Poisson TRFS’s”—which, like Poisson LRFS’s, do not exist. For, according to
([13], Eq. (7)) the distribution of such a TRFS has the form

$f(\mathbf{T})=e^{-\int\vec{D}(T)dT}\prod_{T\in\mathbf{T}}\vec{D}(T).$ (14)

Let $\mathbf{T}_{01}=\mathbf{T}_{0}\uplus\mathbf{T}_{1}$ where
$\mathbf{T}_{0},\mathbf{T}_{1}$ were defined in Counterexample 2 of Section
III-D. Then $\mathbf{T}_{01}$ is a physically impossible SoT since it contains
two distinct instances of the same physical trajectory. If $f(\mathbf{T})$ is
a TRFS distribution then it must vanish on impossible SoT’s—in particular, it
must be the case that $f(\mathbf{T}_{01})=0$. But

$f(\mathbf{T}_{01})\propto\vec{D}(T_{0})\cdot\vec{D}(T_{1})\cdot\vec{D}(T_{2})\cdot\vec{D}(T_{3})\neq
0,$ (15)

where the four factors on the right can be nonzero since
$T_{0},T_{1},T_{2},T_{3}$ are, individually, valid trajectories.

The same comments apply to the trajectory Poisson multi-Bernoulli mixture
trajectory filter [16], [17] since it also requires non-existent Poisson
TRFS’s. The TCPHD filter is similarly erroneous since it requires i.i.d.c.
TRFS’s—which do not exist for the same reason that Poisson TRFS’s do not
exist.

##  IV Conclusions

This paper described and compared two proposed mathematical representations of
multiple-target trajectories: the LRFS vs. TRFS frameworks. It was shown that
the latter is questionable in multiple and serious respects, whereas the
claimed deficiencies of the former are mistaken. This was accomplished via a
systematic, step-by-step analysis beginning with phenomenological and
epistemological basics—in particular, the semiotic concepts of signified vs.
signifier.

## References

  * [1] D. B. Reid, “An algorithm for tracking multiple targets,” IEEE Trans. Auto. Contr., vol. AC-24 no. 6, pp. 843-854, 1979.
  * [2] B.-N. Vo, M. Mallick, Y. Bar-Shalom, S. Coraluppi, R. Osborne III, R. Mahler, and B.-T. Vo, “Multitarget Tracking,” in J. Webster (ed.), Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley, New York, 2015.
  * [3] R. Mahler, Statistical Multisource-Multitarget Information Fusion, Artech House, Norwood, MA, 2007.
  * [4] B.-T. Vo and B.-N. Vo, “A random finite set conjugate prior and application to multi-target tracking,” Proc. 2011 Int’l Conf. on Intelligent Sensors, Sensor Networks, and Information Processing (ISSNIP2011), Adelaide, Australia, Dec. 6-9, 2011.
  * [5] B.-T. Vo and V.-N. Vo, “Labeled random finite sets and multi-object conjugate priors,” IEEE Trans. Sign. Proc., Vol. 61, No. 13, pp. 3460-3475, 2013.
  * [6] M. Beard, B.-T. Vo, and B.-N. Vo, “A solution for large-scale multi-object tracking,” IEEE Trans. Sign. Proc., 68: 2754-2769, 2020.
  * [7] L. Svensson and M. Morelande, “Target tracking based on estimation of sets of trajectories,” Proc. 17th Int’l Conf. on Information Fusion, Salamanca, Spain, July 7-10, 2014.
  * [8] R. Mahler, Advances in Statistical Multisource-Multitarget Information Fusion, Artech House, Norwood, MA, 2014.
  * [9] Á. García-Fernández, J. Williams, K. Granström, and L. Svensson, “Poisson multi-Bernoulli mixture filter: Direct derivation and implementation,” IEEE Trans. Aerospace & Electronic Sys, vol. 54, no. 4, pp. 1883-1901, 2018.
  * [10] R. Mahler, “‘Statistics 103’ for multitarget tracking,” Sensors, 19(1) 202, 2019, open source: https://doi.org/10.3390/s19010202.
  * [11] I. R. Goodman, R. P. S. Mahler, and H. T. Nguyen, Mathematics of Data Fusion, Kluwer Academic Publishers, New York, 1997.
  * [12] B.-T. Vo and B.-N. Vo, “Tracking, identification and classification with random finite sets,” Proc. SPIE, Vol. 8745, 2013.
  * [13] Á. García-Fernández and L. Svensson, “Trajectory probability hypothesis density filter,” Proc. 21st Int’l Conf. on Information Fusion, Cambridge, UK, pp. 1442-1449, 2018.
  * [14] Á. García-Fernández and L. Svensson, “Trajectory PHD and CPHD filters,” IEEE Trans. Sign. Proc., 67(22): ???, 2019\.
  * [15] Á. García-Fernández and L. Svensson, “Trajectory PHD and CPHD filters,” arXiv, version 3, 2019, 1811.08820v3.
  * [16] K. Granström, L. Svensson, J. Wiliams, and Á. García-Fernández, “Poisson multi-Bernoulli mixture trackers: continuity through random finite sets of trajectories,” Proc. 21st Int’l Conf. on Information Fusion, Cambridge, UK, pp.986-994, 2018.
  * [17] Xuxuan Xia, K. Granström, L. Svensson, and Á. García-Fernández, “An implementation of the Poisson multi-Bernoulli mixture trajectory filter via dual decomposition,” Proc. 21st Int’l Conf. on Information Fusion, Cambridge, UK, pp. 2457-2464, 2018.


# On the edge-Erdős-Pósa property of walls

Henning Bruhn and Raphael Steck

###### Abstract

We show that walls of size at least $6\times 4$ do not have the edge-Erdős-
Pósa property.

##  1 Introduction

The Erdős-Pósa property provides a duality between packing and covering in
graphs. We say that a class $\mathcal{F}$ has the _edge-Erdős-Pósa property_
if there exists a function $f:\mathbb{N}\rightarrow\mathbb{R}$ such that for
every graph $G$ and every integer $k$, there are $k$ edge-disjoint subgraphs
of $G$ each isomorphic to some graph in $\mathcal{F}$ or there is an edge set
$X\subseteq E(G)$ of size at most $f(k)$ meeting all subgraphs of $G$
isomorphic to some graph in $\mathcal{F}$. In this article, we focus on graph
classes that arise from taking minors. For a graph $H$, we define the set of
_$H$ -expansions_ as $\mathcal{F}_{H}=\\{G\,|\,H\text{ is a minor of }G\\}.$

While for all non-planar graphs $H$, $\mathcal{F}_{H}$ does not have the edge-
Erdős-Pósa property (see for example [4]), there are only some very simple
planar graphs for which $\mathcal{F}_{H}$ is known to have the edge-Erdős-Pósa
property such as long cycles[2] or $K_{4}$[1]. For most planar graphs, it is
open whether they have the edge-Erdős-Pósa property or not.

In this article, we show that

######  Theorem 1.

For every wall $B$ of size at least $6\times 4$, the class of $B$-expansions
does not have the edge-Erdős-Pósa property.

###  1.1 Condensed Wall

The main gadget used for proving that walls do not have the edge-Erdős-Pósa
property is a wall-like structure called _condensed wall_ introduced by Bruhn
et. al. [3], see Figure 1.

$c^{*}$$d^{*}$$a$$b$ Figure 1: A condensed wall of size 5.

A condensed wall $W$ of size $r\in\mathbb{N}$ is the graph consisting of the
following:

  * •

For every $j\in[r]$, let $P^{j}={u^{j}}_{1},\ldots,{u^{j}}_{2r}$ be a path of
length $2r-1$ and for $j\in\\{0\\}\cup[r]$, let $z_{j}$ be a vertex. Moreover,
let $a$, $b$ be two further vertices.

  * •

For every $i,j\in[r]$, add the edges
$z_{j-1}{u^{j}}_{2i-1},z_{j}{u^{j}}_{2i},z_{i-1}{z_{i}},a{u^{j}}_{1}$ and
$b{u^{j}}_{2r}$.

We define $c=z_{0}$ and $d=z_{r}$ and refer to

$W_{j}=W[\\{{u^{j}}_{1},\ldots,{u^{j}}_{2r},z_{j-1},z_{j}\\}]$

as the _j-th layer of W_. Note that the layers of $W$ are precisely the blocks
of $W-\\{a,b\\}$. We will refer to the vertices $a,b$ quite often, and
whenever we write $a$ or $b$ in this article, we refer to those vertices in a
condensed wall. The vertices connecting the layers of $W$ are
$z_{i},i\in\\{0\\}\cup[r]$, and we will call those _bottleneck vertices_. This
includes the vertices $c$ and $d$. The edges $z_{i-1}z_{i},i\in[r]$ are called
_jump-edges_.

For vertices $a,b,c,d$, an _( $a$-$b$, $c$-$d$)-linkage_ is the vertex-
disjoint union of an $a$-$b$-path with a $c$-$d$-path.

######  Lemma 2 (Bruhn et. al. [3]).

There are no two edge-disjoint ($a$-$b$, $c$-$d$)-linkages in a condensed
wall.

###  1.2 Modification of the condensed wall

A _modified condensed wall_ is a condensed wall without jump-edges
$z_{i-1}z_{i}$ for all $i\in[r]$. Throughout, let $W$ be a condensed wall and
let $W^{-}$ be a modified condensed wall that does not contain jump-edges
$z_{i-1}z_{i}$.

###  1.3 Definition of Walls

For $m,n\in\mathbb{N}$, an _elementary grid_ of size $m\times n$ is a graph
with vertices $v_{i,j}$ for all $i\in[m],j\in[n]$ and edges
$v_{i,j}v_{i+1,j}\,\,\forall i\in[m-1],j\in[n]$ as well as
$v_{i,j}v_{i,j+1}\,\,\forall i\in[m],j\in[n-1]$. A _grid_ is a subdivision of
an elementary grid.

A wall is the subcubic variant of a grid. We define an _elementary wall_ as an
elementary grid with every second vertical edge removed. That is, an
elementary wall of size $m\times n$ is an elementary grid of size $m+1\times
2n+2$ with every edge $v_{i,2j}v_{i+1,2j}\,,i\in[m],i\text{ is odd},j\in[n+1]$
and every edge $v_{i,2j-1}v_{i+1,2j-1}\,,i\in[m],i\text{ is even},j\in[n+1]$
being removed. Additionally, we remove all vertices of degree $1$ and their
incident edge. The _$i^{\text{th}}$ row_ of an elementary wall is the induced
subgraph on $v_{i,1},\ldots,v_{i,2n+2}$ for $i\in[m+1]$ (ignore the vertices
that have been removed); this is a path. There are exactly $n+1$ disjoint
paths between the first row and the $(m+1)^{\text{th}}$ row. These are the
_columns_ of an elementary wall. The _boundary_ of an elementary wall is the
union of the first and last row together with the first and last column. The
_bricks_ of an elementary wall are its $6$-cycles. (See Figure 2)

$1$st rowcolumnrowbrick Figure 2: An elementary wall of size $8\times 8$.

A _wall_ is defined as the subdivision of an elementary wall. The definition
of rows, columns, boundary and bricks in an elementary wall carries over to a
wall in a natural way (with some truncation of the first and last row and
column). For brevity of notation, we define an _$n$ -wall_ as a wall of size
at least $n\times n$.

Figure 3: Three bricks that might be part of a wall. Left, you see a plain
drawing with bricks in the form of rectangles. Right, you see the same part of
a wall but with bricks in the form of honeycombs. In this article, we will
draw walls as on the right side to underline symmetry.

When analyzing small parts of walls, we will not only count the number of
bricks they contain, but also specify how the bricks are connected. To this
end, we define $B_{1},B_{2},\ldots,B_{10}$ to be subdivisions of the graphs
shown in Figure 4.

$B_{1}$$B_{2}$$B_{3}$$B_{4}$$B_{5}$$B_{6}$$B_{7}$$B_{8}$$B_{9}$$B_{10}$ Figure
4: Up to isomorphism, these graphs are defined to be the only elementary
$B_{n}$ for $n\leq 10$.

##  2 Construction

For every graph $G$ and every $r\in\mathbb{N}$, an $r$-fold $G$ is a graph
$G^{\prime}$ where every edge in $G$ is replaced by $r$ edge-disjoint paths of
length $2$.

Given a size $f(2)$ of some hypothetical hitting set, we choose
$r\in\mathbb{N}$ with $r>f(2)$. Let $B$ be a wall of size at least $6\times
4$. Note that for every wall, there are exactly two bricks which are adjacent
to only two other bricks, while all others are adjacent to at least three
bricks. We define the _body_ of $B$ to be the minimal subgraph of $B$ that
contains all bricks with at least three adjacent bricks in $B$. In other
words, the body of $B$ contains everything but the two less connected bricks
in the corners of $B$.

In the body of $B$, we pick two edges $e_{1},e_{2}$ on the outer face of $B$
such that every $e_{1}$-$e_{2}$ path $P$ in $B$ is incident with at least $7$
bricks of $B$ aside from the ones containing $e_{1}$ or $e_{2}$. This is
possible since $B$ has size at least $6\times 4$, so there are at least $16$
bricks adjacent to the outer face of $B$.

Now we define $G^{*}$ to be the graph consisting of the union of an $r$-fold
$B-\\{e_{1},e_{2}\\}$ and a condensed wall $W$ of size $r$ whose terminals
$a,b,c$ and $d$ are identified with the endvertices of $e_{1}$ and $e_{2}$
such that $a$ and $b$ are incident with the same edge and every $ac$-path in
$G^{*}-(W-\\{a,b,c,d\\})$ disconnects $b$ from $d$ in
$G^{*}-(W-\\{a,b,c,d\\})$.

##  3 Results

###  3.1 Strategy

First we check that the construction of $G^{*}$ does not allow for an edge
hitting set of size less than $r$.

######  Lemma 3.

For every set $F\subseteq E(G^{*})$ with $|F|\leq r-1$, $G^{*}-F$ contains a
$B$-expansion.

###### Proof.

By construction, $G^{*}-W^{0}$ contains an $r$-fold $B-\\{e_{1},e_{2}\\}$, so
$G^{*}-W^{0}-F$ still contains an embedding of $B-\\{e_{1},e_{2}\\}$.
Furthermore, $W-F$ contains an ($a$–$b$, $c$–$d$) linkage. Together, this
yields a $B$-expansion in $G^{*}-F$. ∎

This allows us to prove the first half of Theorem 1.

###### Proof.

Let $B$ be a wall of size $6\times 4$, and let $G^{*}$ be as described above.
By Lemma 3, there is no edge hitting set. We thus only have to show that there
can be no two edge-disjoint embeddings of $B$ in $G^{*}$

Now let $U$ be an arbitrary embedding of $B$ in $G^{*}$. Suppose we were able
to show that $U$ must contain an ($a$–$b$, $c$–$d$) linkage in $W$. By Lemma 2
there can be no two edge-disjoint linkages in $W$, implying there can be no
two edge-disjoint embeddings $U_{1},U_{2}$ of $B$ in $G^{*}$. This implies
that $B$ does not have the edge-Erdős-Pósa property, which finishes our proof.
∎

For the remainder of this chapter, let $U$ be a fixed embedding of $B$ in
$G^{*}$. It remains to show that:

######  Lemma 4.

$U$ contains an ($a$–$b$, $c$–$d$) linkage in $W$.

###  3.2 Embedding Walls in a Heinlein Wall

To be able to control the embedding of $U$, we need to make sure that no large
part of it can be embedded in $W$. To this end, we study which small walls are
too large to fit in $W$. For our first lemmas, we will label some parts of a
$B_{3}$ (see Figure 5). Let $x$ be the unique vertex in $B_{3}$ whose
neighbors (in an elementary wall) have degree $3$. Let the other vertices with
degree three be called $w,y$ and $z$. Let the brick that is not incident with
$w$ be called $C_{1}$. Let $P_{1},P_{2}$ and $P_{3}$ be the $yz$-, $zw$\- and
$wy$-paths not crossing $x$.

$x$$w$$y$$z$$C_{1}$$P_{1}$$P_{2}$$P_{3}$ Figure 5: A $B_{3}$ with labels.

######  Lemma 5.

For every $B_{3}$ in $W-\\{a,b\\}$, $x$ is a bottleneck vertex.

###### Proof.

Suppose $x$ would not be a bottleneck vertex. Then $x$ must be on the row
$R_{i}$ in some layer $W_{i}$, and thus $x$ has only degree $3$ in $W$. We
observe that $x$ is adjacent with a bottleneck vertex, say $z_{i}$. Therefore,
one of the edges incident with $x$ is also incident with $z_{i}$. Therefore,
we can assume that one of $w,y$ and $z$ (say $w$) is identical to $z_{i}$ or
$z_{i}$ lies on the $wx$-path not crossing $y$ or $z$. In any case, $z_{i}$ is
not part of the brick $C_{1}$.

As $C_{1}$ contains $x$ and is a cycle, it must also contain $z_{i-1}$.
Additionally, $y$ and $z$ lie on $C_{1}$ but cannot both be incident with
$z_{i}$ as otherwise there would be only one instead of three (or more)
vertices between them. Say $y$ is not incident with $z_{i}$. Then both
neighbors of $y$ on $R_{i}$ lie on $C_{1}$. But $y$ also has a connection
$P_{3}$ of length at least three to $w$ that is internally disjoint from
$C_{1}$. However, $P_{3}$ may only contain the edge $yz_{i}$, which is too
short. ∎

We could directly apply Lemma 5 to see that a $5$-brick wall $B_{5}$ cannot be
embedded in $W-\\{a,b\\}$, because it would contain three different vertices
that are a central vertex $x$ in a $B_{3}$, but there are only two bottleneck
vertices in a layer of $W$. We will later see that we can even exclude a
$4$-brick wall $B_{4}$, but for this we will need to see how a $3$-brick wall
$B_{3}$ can be embedded in $W-\\{a,b\\}$.

######  Lemma 6.

For all integers $r$ and $n$, a condensed wall without jump-edges $W^{-}$ of
size $r+n$ contains $n$ edge-disjoint embeddings of $B_{3}$ in
$W^{-}-\\{a,b\\}$, even with $r$ edges being deleted.

###### Proof.

Obviously, there still exist $n$ complete layers of $W^{-}$. In each, we will
place one $B_{3}$ as in Figure 6, so they are all edge-disjoint because the
layers of $W^{-}$ are. ∎

Figure 6: A $B_{3}$ in a layer of a modified condensed wall $W^{-}$ without
jump-edges.

######  Lemma 7.

There exists no $B_{4}$ in $W-\\{a,b\\}$.

###### Proof.

First, we focus on a fixed $B_{3}$ which is a subgraph of every $B_{4}$. By
Lemma 5, we know that $x$ must be a bottleneck vertex, say $z_{i-1}$. As a
wall is $2$-connected, we conclude that the rest of $B_{3}$ must be in the
same layer $W_{i}$ of $W$ as $x$. Where are $w,y$ and $z$?

$w,y$ and $z$ could all lie on the row $R_{i}$ of $W_{i}$. The outer two (say
$w$ and $y$) must then be connected via the path $P_{3}$ that uses $z_{i}$.
This implies that $P_{1}$ and $P_{2}$ must be entirely contained in $R_{i}$.
Now there is no connection between any two of $P_{1},P_{2}$ and $P_{3}$ in
$W_{i}-B_{3}$, which implies there can no $B_{4}$ in $W-\\{a,b\\}$ which
contains a $B_{3}$ that is embedded as above.

The only alternative for a $B_{3}$ would be to use $z_{i}$ for one of $w,y$
and $z$, say $w$. But then $z$ and $y$ are still on $R_{i}$. As both
bottleneck vertices are blocked, $P_{1}$ must be entirely contained in
$R_{i}$, too. Now $y$ and $z$ separate $P_{1},P_{2}$ and $P_{3}$ in $R_{i}$,
so there cannot be any path connecting any two of them in $W-\\{a,b\\}$
without using $z_{i-1}$ or $z_{i}$, which are blocked by $x$ and $w$. Again,
we conclude that there cannot be a $B_{4}$. ∎

######  Lemma 8.

There exists no $B_{4}$ in $W^{-}$ that contains a $B_{3}$ in $W-\\{a,b\\}$.
The same holds true for a $B_{5}$ in $W$.

###### Proof.

In the proof of Lemma 7, we have seen that there are only two possibilities to
embed a $B_{3}$ in $W-\\{a,b\\}$. Let us start with the first one, i. e. $w,y$
and $z$ are all on the same row $R_{i}$, and $P_{3}$ connects $w$ and $y$ via
$z_{i}$. Then there is no path between $P_{1}$ or $P_{2}$ and a vertex outside
of $R_{i}$ that does not cross $B_{3}$, which implies $W$ cannot contain a
$B_{4}$.

So let us assume $w$ is identical to $z_{i}$ instead. In $W^{-}-\\{a,b\\}$,
the subdivision of edge $1$ crosses $R_{i}$, so both $y$ and $z$ must be on
the same side of it. But then $B_{3}$ can have only one path connecting it to
a vertex outside of $W_{i}$ via either $u^{i}_{1}$ or $u^{i}_{2r}$, but two
such connections would be needed to form an additional cycle and thus a
$B_{4}$. In $W$ (instead of $W^{-}$), there can be both connections, but this
only enables a $B_{4}$ and not a $B_{5}$. ∎

The last lemma shows that no large wall can contain a $B_{3}$ in
$W-\\{a,b\\}$. Next, we will see what happens for a $B_{2}$.

######  Lemma 9.

Every $B_{2}$ in $W-\\{a,b\\}$ that is part of a $B_{3}$ in $W$ contains a
bottleneck vertex as a vertex of degree $3$.

###### Proof.

As $B_{2}$ is $2$-connected, $B_{2}$ must be contained in a single layer
$W_{i}$ of $W$. We start by labeling our $B_{2}$ as in Figure 7. Let $C_{1}$
and $C_{2}$ be the two bricks of $B_{2}$, and let $x$ and $y$ be the vertices
of degree $3$. Let $Q$ be the $xy$-path belonging to both $C_{1}$ and $C_{2}$,
and let $P_{1}$ be the $xy$-path which is unique to $C_{1}$, while $P_{2}$ is
the $xy$-path that lies only in $C_{2}$. Finally, let $P_{3}$ be the path in
$B_{3}-B_{2}$ connecting $P_{1}$ and $P_{2}$. Suppose $x$ and $y$ would both
not be a bottleneck vertex. Then $x$ and $y$ lie both on the row $R_{i}$.
Additionally, by Lemma 5, the $B_{3}$ cannot be entirely contained in
$W-\\{a,b\\}$.

$x$$y$$Q$$P_{3}$$P_{1}$$P_{2}$ Figure 7: A $B_{2}$ with labels. The grey path
$P_{3}$ belongs to the $B_{3}$.

Case 1: $Q$ contains no bottleneck vertex

Suppose $Q$ would not contain a bottleneck vertex. Then $Q$ is entirely
contained in $R_{i}$. As $x$ and $y$ have degree $3$ in $B_{2}$, as is the
maximum degree in $R_{i}$, every edge incident with $x$ or $y$ in $W$ must
also be used for $B_{2}$. In particular, the paths $P_{1}$ and $P_{2}$ use the
edges connecting $x$ and $y$ with $z_{i-1}$ and $z_{i}$. From those bottleneck
vertices, $P_{1}$ and $P_{2}$ must use an edge to $R_{i}$, and from there on
they can only contain a path connecting them to $x$ or $y$ on $R_{i}$. Now the
only possibilities to connect $P_{1}$ or $P_{2}$ to a vertex outside of
$W_{i}$ would be to use the bottleneck vertices, which are the first vertex on
$P_{1}$ after $x$ and $y$, or the very next vertex which they hit on the row,
which comes second on $P_{1}$ and $P_{2}$. However, none of $P_{1}$ and
$P_{2}$ can have a connection via its third (or a later) vertex. Note that we
counted the vertices for both $P_{1}$ and $P_{2}$ in the same order (e. g.
clockwise).

When looking at how a $B_{2}$ can be extended to a $B_{3}$, we notice that the
first branch vertex of $P_{1}$ must be connected with the third branch vertex
of $P_{2}$, or vice versa. This is impossible as we observed above, a
contradiction.

Case 2: $Q$ contains a bottleneck vertex

Suppose $Q$ would contain at least one bottleneck vertex, say $z_{i}$. As we
required $x$ and $y$ not to be a bottleneck vertex, we conclude that $z_{i}$
is an interior vertex of $Q$. Now $P_{1}$ and $P_{2}$ must connect $x$ and $y$
in $W_{i}$ without using $z_{i}$. Therefore, one of them (say $P_{1}$) must be
entirely contained in $R_{i}$. Furthermore, $P_{2}$ and $Q$ separate $P_{1}$
from $W-W_{i}$. This implies $B_{2}$ cannot be extended to a $B_{3}$, a
contradiction. ∎

######  Lemma 10.

Let $G$ be a subcubic subgraph of a condensed wall $W$ that contains a $B_{2}$
in $W-\\{a,b\\}$ (which implies $B_{2}$ is contained in a single layer $W_{i}$
of $W$). Then there are at most $3$ disjoint paths in $G$ connecting $B_{2}$
to $W-W_{i}$, and at most one of them may use a bottleneck vertex of $W_{i}$.

###### Proof.

By Lemma 9, we know that $B_{2}$ must already contain one of the bottleneck
vertex as a vertex of degree $3$. As $G$ is subcubic, this vertex cannot be
used for a connection of $B_{2}$ to $W-W_{i}$. This leaves only one bottleneck
vertex and $a$ and $b$ for such connections. ∎

######  Definition 11.

A $B_{1}^{2}$ is the union of two disjoint $B_{1}$ ($H_{1}$, $H_{2}$), and two
disjoint paths ($P_{1},P_{2}$) each connecting $H_{1}$ with $H_{2}$, i.e.
$B_{1}^{2}:=H_{1}\cup H_{2}\cup P_{1}\cup P_{2}$.

######  Lemma 12.

In a $B_{7}$, let $Q$ be a disjoint (and possibly empty) union of paths $P$ in
$B_{7}$, such that all interior vertices of $P$ have degree at most $2$ in
$B_{7}$, and let $P$ have only bottleneck vertices and at least one of $a$ and
$b$ as endvertices. Then there is no embedding of $B_{7}-Q$ in a condensed
wall $W$.

###### Proof.

Suppose $B_{7}-Q$ would be in $W$. First, we notice that every $B_{2}$ in
$B_{7}-Q$ has at least four disjoint connections to $B_{7}-B_{2}$. Therefore,
we conclude with Lemma 10 that no $B_{2}$ can be contained in $W-\\{a,b\\}$.

Next, we observe that each of $a$ and $b$ can be only situated on at most two
of the six outer bricks of $B_{7}$. This implies $B_{7}-\\{a,b\\}-Q$ contains
at least two disjoint $B_{1}$, call them $H_{1}$ and $H_{2}$. Additionally, we
can conclude that $H_{1}$ and $H_{2}$ were on opposite sides of $B_{7}$,
otherwise we would get a $B_{2}$ in $W-\\{a,b\\}$. Furthermore, $H_{1}$ and
$H_{2}$ were connected by four disjoint paths in $B_{7}$, meaning there are
still at least two disjoint paths $P_{1}$, $P_{2}$ connecting $H_{1}$ and
$H_{2}$ in $B_{7}-\\{a,b\\}-Q$. (Note that all paths in $Q$ begin or end in
either $a$ or $b$.)

Now $U=H_{1}\cup H_{2}\cup P_{1}\cup P_{2}$ is a $B_{1}^{2}$ in $W-\\{a,b\\}$.
First, we notice that $U$ is $2$-connected, which implies that $U$ is
contained in a single layer $W_{i}$ of $W$. Next, we observe that there are
$6$ connections of $U$ to $a$ and $b$ in $B_{7}$. Therefore, $U$ must have $6$
connecting vertices (i.e. bottleneck vertices or vertices adjacent to $a$ or
$b$). However, there can be at most $4$ connecting vertices, a contradiction.
∎

######  Lemma 13.

For every $n,r\in\mathbb{N}$, in every condensed wall without jump-edges
$W^{-}$ of size $3\cdot(n+r)$, there are $n$ edge-disjoint $B_{6}$ in $W^{-}$,
even with $r$ edges of $W^{-}$ being deleted.

###### Proof.

Even with $r$ edges of $W^{-}$ being deleted, there are still at least $n$
untouched edge-disjoint chunks of $W^{-}$ that each contain three consecutive
layers of $W^{-}$ and which all have an edge to both $a$ and $b$. In each of
them, we can find a $B_{6}$ as in Figure 9. ∎

$a$$b$$a$$b$ Figure 8: Left: A $B_{6}$ as we would like to embed it in a
condensed wall, with positions of $a$ and $b$. Right: An isomorphic graph that
reflects our acutal embedding of $B_{6}$ in $W^{-}$ as in Figure 9. $a$$b$
Figure 9: A $B_{6}$ in three layers of a modified condensed wall $W^{-}$ (i.e.
without jump-edges) of size $6$. For more details on the embedding, see Figure
8.

######  Lemma 14.

For every $n,r\in\mathbb{N}$, let $G$ be the graph consisting of a condensed
wall without jump-edges $W^{-}$ of size $5\cdot(n+r)$ and $n+r$ edge-disjoint
paths $P$ (all internally disjoint from $W$) connecting $c$ with $d$. Then
there are $n$ edge-disjoint $B_{7}$ in $G$, even with $r$ edges of $G$ being
deleted.

###### Proof.

Even with $r$ edges of $W^{-}$ being deleted, there are still at least $n$
untouched edge-disjoint chunks of $W^{-}$ that each contain five consecutive
layers of $W^{-}$ and which all have an edge to both $a$ and $b$. In each of
them, we can find a $B_{7}^{-}$ (that only misses one $z_{i}$-$z_{j+1}$-path)
as in Figures 10 and 11. Clearly, we can find edge-disjoint paths from each
chunk to $c$ and $d$ in $W-\\{a,b\\}$, which together with a path $P$ outside
of $W$ yields the desired $z_{i}$-$z_{j+1}$-path. Together, they form $n$
edge-disjoint $B_{7}$. ∎

$d$$c$$a$$b$ Figure 10: A $B_{7}$ as we embed it in Figure 11. $a$$b$ Figure
11: A $B_{7}$ of which all but one edge fit into a condensed wall of size $5$.
A schematic drawing of what is embedded here can be found in Figure 10.

######  Proposition 15.

A condensed wall $W$ (or its modified counterpart $W^{-}$) with some
connections of its terminals cannot serve as a counterexample to prove that a
$B_{7}$ does not have the edge-Erdős-Pósa property.

###### Proof.

Let $G$ be our counterexample graph, i. e. a condensed wall $W$ (or its
modified counterpart $W^{-}$) with some connections of its terminals. Let $U$
be a $B_{7}$ in $G$. Let $U_{out}$ be the subgraph of $U$ in
$G-(W-\\{a,b\\})$, while $U_{in}$ is the subgraph of $U$ in $G$. In Lemma 12,
we have seen that a $B_{7}$ cannot be found in any condensed wall $W$. As a
$B_{7}$ is $2$-connected, we thus need at least two terminals of $W$ to be
connected outside of $W$. However, Lemma 14 shows that we must not connect $c$
with $d$, as we would otherwise find arbitrarily many $B_{7}$. This limits us
to at most three connections, which in turn implies that $U_{out}$ is
connected.

If $U_{out}$ has only $2$ connections to $W$, then $U_{out}$ only contains a
single path with at least one of $a$ and $b$ as an endvertex. We can again
conclude with Lemma 12 that we cannot find a $B_{7}$ in $G$. It remains to
check what happens if $U_{out}$ uses three connections, namely $a,b$ and
exactly one of $c$ and $d$. Then $U_{out}$ contains a single vertex $v$ of
degree $3$ in $B_{7}$ and possibly some paths incident with it. This implies
that there is no vertex of degree $3$ in $B_{7}$ between $a,b$ and $v$.
Therefore, $U_{out}$ is only incident with at most $4$ of the outer bricks of
$B_{7}$, and those are adjacent to each other. This implies that there is a
$B_{2}$ in $W-\\{a,b\\}$, a contradiction to Lemma 10. ∎

###  3.3 Main Proof

Let us now come back to proving our main lemma.

######  Lemma 4.

$U$ contains an ($a$–$b$, $c$–$d$) linkage in $W$.

###### Proof.

$U$ can not be entirely contained in $W$ due to Lemma 12. Cleary, it can not
be entirely contained in $G^{*}-(W-\\{a,b,c,d\\})$ (the graph which contains
all edges of $G^{*}$ that are not in $W$) either, as there are two edges
missing there. Therefore, $U$ must have edges in both $W$ and
$G^{*}-(W-\\{a,b,c,d\\})$. This motivates the following definitions:

Let $U_{in}$ be the subgraph of $U$ in $W$, and let $U_{out}$ be the subgraph
of $U$ in $G^{*}-(W-\\{a,b,c,d\\})$. Note that $U_{in}$ and $U_{out}$ are
edge-disjoint, $U_{in}+U_{out}=U$ and the only vertices that can be shared by
$U_{in}$ and $U_{out}$ are $a,b,c$ and $d$. Therefore, we define a _connecting
vertex_ as a vertex of $U$ that is incident with edges of both $U_{in}$ and
$U_{out}$.

Case 1: Every component of $U_{in}$ contains at most three connecting
vertices.

As $U$ is $2$-connected, every component of $U_{in}$ must contain at least two
connecting vertices. Of the body of $U$, one of $U_{in}$ or $U_{out}$ contains
all but at most one vertex of degree $3$ (the _large component_), while the
other may only contain either one or two subgraphs of maximum degree $2$ (i.e.
paths) or a single subgraph with one single vertex of degree $3$ and possibly
some incident paths.

Suppose the large component is in $W$. Since $B$ is a wall of size at least
$6\times 4$, the body of $B$ contains a $B_{10}$. (Actually, it is
considerably larger, but a $B_{10}$ will suffice to obtain a contradiction in
this case.) If $U_{out}$ only contains paths, we know by Lemma 12 that if
every one of those paths has $a$ or $b$ as one endvertex, we would not be able
to embed a $B_{7}$ in $W\cup U_{out}$, lest there cannot be a $B_{10}$ or the
entire body of $U$ in $G^{*}$. Therefore, we conclude that $U_{out}$ must
either contain a vertex of degree $3$ or a $cd$-path (and possibly also an
$ab$-path).

Next, we note that the eight outer bricks of the $B_{10}$ are arranged in a
cycle, which we call _grand cycle_. This grand cycle contains two disjoint
cycles that are incident with all eight bricks of the grand cycle, which we
call _large cycles_. $U_{in}$ still contains most of this grand cycle, except
for one or two small subgraphs as described above. Each vertex can be part of
at most two bricks in the grand cycle. Additionally, it can be part of at most
one of the large cycles.

If there is a vertex $v$ of degree $3$ or a $cd$-path $P$ in $U_{out}$,
$W-\\{a,b\\}$ still contains at least all but three vertices of degree $3$ in
the grand cycle and all the paths between them that are not incident with a
missing vertex. This implies $W-\\{a,b\\}$ contains at least two bricks. If
those are adjacent, there is a $B_{2}$ in $W-\\{a,b\\}$, a contradiction to
Lemma 10. If every two bricks in $W-\\{a,b\\}$ are not adjacent, we have a
look at how many bricks in $W-\\{a,b\\}$ are left. If there are exactly two,
each of $a,b$ and $v$ (or $P$) must be incident with two bricks, and those
bricks are pairwise different for each vertex. We conclude that we can still
find a cycle in $W-\\{a,b\\}$ that is incident with all bricks of the grand
cycle. Together with the two bricks in $W-\\{a,b\\}$, this yields a
$B_{1}^{2}$ in $W-\\{a,b\\}$. As a $B_{1}^{2}$ is $2$-connected, it is
contained in a single layer of $W$. However, it has two disjoint connections
to each of $a,b$ and $v$ (or $P$) in $U$, which means there must be six
pairwise disjoint paths connecting $B_{1}^{2}$ with vertices outside of its
layer, which is clearly not possible.

What happens if there are more than two bricks left in $W-\\{a,b\\}$? Then, as
no two of them are adjacent, there are exactly three bricks in $W-\\{a,b\\}$
and exactly one of $a,b$ and $v$ (or $P$) lies between every two of them.
Clearly, we can again find a $B_{1}^{2}$ in $W-\\{a,b\\}$ and arrive at a
contradiction as we did above.

It remains to check what happens if the large component $C$ is contained in
$U_{out}$. We claim that if there is an embedding of $C$ in
$G^{*}-(W-\\{a,b,c,d\\})$, then there is also an embedding of $C$ in the body
of $G^{*}-(W-\\{a,b,c,d\\})$. We observe that no brick of $C$ can be entirely
contained in an arm of $G^{*}-(W-\\{a,b,c,d\\})$ by definition of the body. If
there is a brick $B_{1}$ of $C$ that is only partly contained in an arm of
$G^{*}-(W-\\{a,b,c,d\\})$, then the other part of $B_{1}$ is contained in the
body of $G^{*}-(W-\\{a,b,c,d\\})$. In particular, there is a path $P$ (the
border between body and arm) such that $B_{1}\cup P$ is a $B_{2}$. But of this
$B_{2}$ exactly one brick is entirely contained in the arm while the other is
entirely contained in the body of $G^{*}-(W-\\{a,b,c,d\\})$. Replacing $B_{1}$
with the latter and doing the same for all bricks of $C$ that are not entirely
contained in $G^{*}-(W-\\{a,b,c,d\\})$ yields an embedding of $C$ in
$G^{*}-(W-\\{a,b,c,d\\})$.

The body of $G^{*}-(W-\\{a,b,c,d\\})$ is missing two edges ($e_{1}$ and
$e_{2}$), so the body of $U$ cannot be entirely contained there. To see that
connecting $a$ or $b$ with $c$ or $d$ would not help to embed the body of $U$,
we count bricks. $G^{*}$ misses $e_{1},e_{2}$, so it contains two bricks less
than $B$. A cycle that uses exactly one new $\\{a,b\\}-\\{c,d\\}$ path would
be incident with at least seven bricks, meaning the cycle can not constitute a
new brick since every brick can only be incident with at most 6 other bricks.
Now let $K$ be a cycle that uses both new $\\{a,b\\}-\\{c,d\\}$ paths and is
incident with at most $6$ bricks. Then it is incident with all three bricks
that are adjacent to the brick containing $e_{1}$, and also incident with the
three bricks adjacent to the brick containing $e_{2}$. But those two groups of
three bricks each are not adjacent to each other, which is impossible for the
neighbourhood of a brick. We conclude that $K$ may not constitute a new brick,
either. We conclude that connecting $a$ or $b$ with $c$ or $d$ does not allow
for an embedding the body of $U$.

Therefore, the only possibility is to add an $a$-$b$ path and a $c$-$d$ path
in $W$. Those paths must be disjoint, as otherwise the two bricks repaired by
using them would be adjacent, which is impossible since their neighbourhood is
not. Thus $U$ contains an $a-b,c-d$-linkage, which was what we wanted.

Case 2: There are exactly four connecting vertices in one component of
$U_{in}$.

By definition, there can be at most four connecting vertices in total, so this
case covers everything not handled in Case 1. In particular, both $U_{in}$ and
$U_{out}$ are connected.

If $U_{in}$ does not contain a single brick, it contains no cycle and is
therefore a tree with exactly four leaves and exactly two vertices of degree
$3$. If $U_{in}$ contains an $a-b$,$c-d$-linkage, there is nothing left to
show. Otherwise, it looks as the red part in Figure 12.

$a$$b$$d$$c$ Figure 12: $G^{*}-W^{0}+U_{in}$ when $U_{in}$ contains neither a
brick nor a linkage.

To show that $G^{*}-W^{0}+U_{in}$ does not contain an embedding of $B$ in this
case (see Figure 12), we count the bricks in the body of $B$ again. Since
$G^{*}$ is missing $e_{1}$ and $e_{2}$, its body is missing two bricks. We
have seen before that no cycle that contains exactly one
$\\{a,b\\}$-$\\{c,d\\}$ path may constitute a new brick since it it incident
with at least seven other bricks.

$G^{*}-W^{0}+U_{in}$ may contain exactly one new brick that contains an
$a$-$b$ path or a $c$-$d$-path in $U_{in}$. However, if there were two such
bricks, they were adjacent to each other, which is impossible since their
other neighbours are those bricks that were adjadent to the bricks containing
$e_{1}$ and $e_{2}$, respectively. This would imply that each of the two new
bricks’ neighbourhood would be disconnected, which is impossible. We conclude
that the body of $G^{*}-W^{0}+U_{in}$ contains one brick less than the body of
$B$, a contradiction.

As $U_{in}$ contains at least one brick, there is a cycle $C$ in $U_{in}$ that
contains all bricks of $U_{in}$ on its inner face. In particular, the four
paths connecting $a,b,c$ and $d$ all end in $C$ in pairwise different vertices
$v_{a},v_{b},v_{c}$ and $v_{d}$. If there is a $v_{a}v_{b}$-path in $C$
disjoint from $v_{c}$ and $v_{d}$, then there is also a (disjoint)
$v_{c}v_{d}$-path in $C$ disjoint from $v_{a}$ and $v_{b}$. Together, they
yield an $a-b$,$c-d$-linkage in $W$. We may therefore assume that every
$v_{a}v_{b}$-path on $C$ is incident with $v_{c}$ or $v_{d}$. This implies
that out of the four paths connecting $U_{in}$ and $U_{out}$, the two
containing $a$ and $b$ do not lie next to each other, but instead alternate
with the ones containing $c$ and $d$.

Now we can study $U_{out}$. As $U_{in}$ cannot contain a $B_{7}$, there are
some bricks left in $U_{out}$ and four paths connecting it to $U_{in}$. The
border to the outer face of the bricks in $U_{out}$ forms a cycle $C$ that is
incident with all paths that connect $U_{in}$ with $U_{out}$. Therefore, $C$
must be incident with $a,b,c$ and $d$ in $U_{out}$. We have seen that the
connecting paths containing $a$ and $b$ alternate with those containing $c$
and $d$. Therefore, there must be an $ac$-path and a disjoint $bd$ path in
$U_{out}$. This is impossible by construction. ∎

##  4 Discussion

In Theorem 1, we have seen that the expansions of every wall of size at least
$6\times 4$ do not have the edge-Erdős-Pósa property. Is $6\times 4$ optimal?

When studying the proof of Lemma 4, one will notice that a size of $6\times 4$
was only needed to get an easier argument for why adding an
$\\{a,b\\}$-$\\{c,d\\}$ path (that is, a path connecting vertices that are far
away from each other) does not help to create new bricks. However, I believe
that with a more careful argument (for example counting the neighbours of
every brick), the same result can be obtained for smaller walls such as a
$B_{10}$. In particular, you may have noticed that those parts of the proof of
Lemma 4 that referred to embedding a large part of a wall into the Heinlein
Wall already made do with a $B_{10}$. Can we do even better?

In Proposition 15, we showed that a condensed wall cannot be used to prove
that a $B_{7}$ does not have the edge-Erdős-Pósa property, even though it is
not a minor of it as seen in Lemma 12. What about a $B_{8}$ or $B_{9}$? I
believe that a Heinlein Wall cannot be used to prove that they do not have the
edge-Erdős-Pósa property, either. I did not prove that, but I found evidence
in the form of constructions that place most bricks of a $B_{8}$ or $B_{9}$ in
a (modified) Heinlein Wall $W^{-}$ while needing only one or two bricks
outside of it with three or four connections to $W^{-}$.

######  Lemma 16.

For every $n,r\in\mathbb{N}$, let $G$ be the graph consisting of a Heinlein
Wall without jump-edges $W^{-}$ of size $3\cdot(n+r)$ and a $n+r$-fold brick
$B_{1}$ with three adjacent branch vertices being connected to $d,b$ and $c$
(in this order when counting clockwise) by $n+r$-fold paths (all internally
disjoint from $W$, $B_{1}$ and each other). Then there are $n$ edge-disjoint
$B_{8}$ in $G$, even with $r$ edges of $G$ being deleted.

###### Proof.

Even with $r$ edges of $G$ being deleted, there are still at least $n$
untouched edge-disjoint chunks of $W^{-}$ that each contain three consecutive
layers of $W^{-}$ and which all have an edge to both $a$ and $b$. In each of
them, we can find a $B_{8}^{-}$ (that only misses one brick and three
connecting paths) as in Figures 13 and 14. Clearly, we can find edge-disjoint
paths from each chunk to $c$ and $d$ in $W^{-}-\\{a,b\\}$, which together with
a brick and three connections outside of $W^{-}$ yield the desired $B_{8}$.
Together, they form $n$ edge-disjoint $B_{8}$. ∎

$c$$b$$d$$a$ Figure 13: A $B_{8}$ as we embed it in Figure 14. $a$$b$ Figure
14: A $B_{8}$ embedded in three layers of a Heinlein Wall. A schematic drawing
of what is embedded here can be found in Figure 13.

######  Lemma 17.

For every $n,r\in\mathbb{N}$, let $G$ be the graph consisting of a Heinlein
Wall without jump-edges $W^{-}$ of size $3\cdot(n+r)$ and a $n+r$-fold $B_{2}$
with four branch vertices being connected to $a,b,c$ and $d$ by $n-r$-fold
paths (all internally disjoint from $W$, $B_{2}$ and each other and such that
a $B_{9}$ can be formed, see Figure 16). Then there are $n$ edge-disjoint
$B_{9}$ in $G$, even with $r$ edges of $G$ being deleted.

###### Proof.

Even with $r$ edges of $G$ being deleted, there are still at least $n$
untouched edge-disjoint chunks of $W^{-}$ that each contain three consecutive
layers of $W^{-}$ and which all have an edge to both $a$ and $b$. In each of
them, we can find a $B_{9}^{-}$ (that only misses two bricks and four
connecting paths) as in Figures 15 and 16. Clearly, we can find edge-disjoint
paths from each chunk to $c$ and $d$ in $W^{-}-\\{a,b\\}$, which together with
two bricks and four connections outside of $W^{-}$ yield the desired $B_{9}$.
Together, they form $n$ edge-disjoint $B_{9}$. ∎

$c$$b$$d$$a$ Figure 15: A $B_{9}$ as we embed it in Figure 16. $a$$b$ Figure
16: A $B_{9}$ embedded in three layers of a condensed wall. A schematic
drawing of what is embedded here can be found in Figure 15.

## References

  * [1] Henning Bruhn and Matthias Heinlein, _$K_{4}$ -subdivisions have the edge-Erdős-Pósa property_, SIAM Journal on Discrete Mathematics 35 (2021), no. 1, 392–430.
  * [2] Henning Bruhn, Matthias Heinlein, and Felix Joos, _Long cycles have the edge-Erdős-Pósa property_ , Combinatorica 39 (2019), 1–36.
  * [3] Henning Bruhn, Matthias Heinlein, and Felix Joos, _The edge-Erdős-Pósa property_ , Combinatorica 41 (2020), 147 – 173\.
  * [4] Jean-Florent Raymond and Dimitrios M. Thilikos, _Recent techniques and results on the Erdős–Pósa property_ , Discrete Applied Mathematics 231 (2017), 25 – 43, Algorithmic Graph Theory on the Adriatic Coast.