# Growable Realizations: a Powerful Approach to the Buratti-Horak-Rosa
Conjecture

M. A. Ollis  Marlboro Institute for Liberal Arts and Interdisciplinary
Studies, Emerson College, Boston, MA 02116, USA  Anita Pasotti  DICATAM, Sez.
Matematica, Università degli Studi di Brescia, Via Branze 43, I 25123 Brescia,
Italy  Marco A. Pellegrini  Dipartimento di Matematica e Fisica, Università
Cattolica del Sacro Cuore, Via Musei 41, I 25121 Brescia, Italy  John R.
Schmitt  Mathematics Department, Middlebury College, Middlebury, VT 05753, USA

###### Abstract

Label the vertices of the complete graph $K_{v}$ with the integers
$\\{0,1,\ldots,v-1\\}$ and define the length of the edge between $x$ and $y$
to be $\min(|x-y|,v-|x-y|)$. Let $L$ be a multiset of size $v-1$ with
underlying set contained in $\\{1,\ldots,\lfloor v/2\rfloor\\}$. The Buratti-
Horak-Rosa Conjecture is that there is a Hamiltonian path in $K_{v}$ whose
edge lengths are exactly $L$ if and only if for any divisor $d$ of $v$ the
number of multiples of $d$ appearing in $L$ is at most $v-d$.

We introduce “growable realizations,” which enable us to prove many new
instances of the conjecture and to reprove known results in a simpler way. As
examples of the new method, we give a complete solution when the underlying
set is contained in $\\{1,4,5\\}$ or in $\\{1,2,3,4\\}$ and a partial result
when the underlying set has the form $\\{1,x,2x\\}$. We believe that for any
set $U$ of positive integers there is a finite set of growable realizations
that implies the truth of the Buratti-Horak-Rosa Conjecture for all but
finitely many multisets with underlying set $U$.

MSC: 05C38, 05C78.

##  1 Introduction

Let $K_{v}$ be the complete graph on $v$ vertices, labeled with the integers
$\\{0,1,\ldots,v-1\\}$. For two vertices $x$ and $y$, define the length of the
edge between them to be

$\ell(x,y)=\min(|x-y|,\ v-|x-y|),$

which is an integer in the range $1\leq\ell(x,y)\leq\lfloor v/2\rfloor$.

A Hamiltonian path ${\bm{h}}=[h_{1},h_{2},\ldots,h_{v}]$ in $K_{v}$ uses $v-1$
edges and gives a multiset $L=\\{\ell(h_{i},h_{i+1}):1\leq i\leq v-1\\}$ of
edge-lengths. Call ${\bm{h}}$ a realization of $L$ or say that ${\bm{h}}$
realizes $L$. For example, with $v=7$ the Hamiltonian path $[0,5,1,2,6,3,4]$
has edge-length sequence $[2,3,1,3,3,1]$ and hence realizes the multiset
$\\{1^{2},2,3^{3}\\}$ (where exponents indicate multiplicity).

Given a multiset $L$, its underlying set is given by $U=\\{x:x\in L\\}$.

The focus of our inquiry is the Buratti-Horak-Rosa Conjecture, or BHR
Conjecture:

######  Conjecture 1.1.

Let $L$ be a multiset of size $v-1$ with underlying set $U$ contained in
$\\{1,\ldots,\lfloor v/2\rfloor\\}$. Then there is a realization of $L$ in
$K_{v}$ if and only if for any divisor $d$ of $v$ the number of multiples of
$d$ in $L$ is at most $v-d$.

When $v$ is prime, in which case the condition on divisors is always
satisfied, we have the original Buratti Conjecture, see [1, 11]. Horak and
Rosa [5] generalize this to composite $v$ and show that the condition on
divisors is necessary; Pasotti and Pellegrini [10] reformulate Horak and
Rosa’s statement into the one in Conjecture 1.1.

Call a multiset $L$ of size $v-1$ admissible if it has underlying set
$U\subseteq\\{1,\ldots,\lfloor v/2\rfloor\\}$ and it satisfies the divisor
condition of the BHR conjecture. Denote the BHR Conjecture for $L$ by
$\mathop{\rm BHR}(L)$.

Much work has been done on the BHR Conjecture. Theorem 1.2 captures the main
progress that has been made to date.

######  Theorem 1.2.

Let $L$ be a multiset of size $v-1$ with underlying set $U$. In each of the
following cases, if $L$ is admissible, then it is realizable.

  1. 1.

$|U|\leq 2$ [3, 5],

  2. 2.

$U=\\{1,2,4\\},\\{1,2,6\\},\\{1,2,8\\}$ [9],

  3. 3.

$U\subseteq\\{1,2,3,5\\}$ [2, 10],

  4. 4.

$L=\\{1^{a},2^{b},3^{c},4^{d}\\}$ with either $a\geq 3$ and $c,d\geq 1$ or
$a=2$ and $b,c,d\geq 1$ [8],

  5. 5.

$L=\\{1^{a},2^{b},x^{c}\\}$ when $x$ is even and $a+b\geq x-1$ [9],

  6. 6.

$L=\\{1^{a},x^{b},(x+1)^{c}\\}$ when $x$ is odd and either
$a\geq\min(3x-3,b+2x-3)$ or $a\geq 2x-2$ and $c\geq 4b/3$ [8],

  7. 7.

$L=\\{1^{a},x^{b},(x+1)^{c}\\}$ when $x$ is even and either
$a\geq\min(3x-1,c+2x-1)$ or $a\geq 2x-1$ and $b\geq c$ [8],

  8. 8.

$U\subseteq\\{1,2,4,\ldots,2x\\}$ and $\\{1^{2x-1},2x\\}\subseteq L$ [8],

  9. 9.

$U\subseteq\\{1,2,4,\ldots,2x,2x+1\\}$ and $\\{1^{6x-1},2x+1\\}\subseteq L$
[8],

  10. 10.

$L=\\{1^{a_{1}},2^{a_{2}},\ldots,x^{a_{x}}\\}$ with $a_{1}\geq
a_{2}\geq\cdots\geq a_{x}$ [7, 8],

  11. 11.

$L=M\cup\\{1^{a}\\}$ for any multiset $M$ and $a>a_{M}$, where $a_{M}$ is a
constant that depends on $M$ [5],

  12. 12.

$v\leq 19$ or $v=23$ [6].

After proving Theorem 1.2.11, Horak and Rosa observe that “to get an explicit
bound… one only needs refer to lemmas used in the proof” [5]. It turns out
that their methodology can be used to give a bound that is linear in the
elements of the underlying set and independent of their multiplicities,
neither of which is clear from the statement of the result. We believe that
this is of interest and so give an explicit bound with these properties in
Theorem 1.3.

######  Theorem 1.3.

Let $M$ be a multiset with underlying set $U=\\{x_{1},\ldots,x_{k}\\}$, where
$1<x_{1}<\cdots<x_{k}$. Then $L=M\cup\\{1^{s}\\}$ is realizable for any $s\geq
3x_{k}-5+\sum_{i=1}^{k}x_{i}$.

###### Proof Outline.

We give the steps required to establish the bound, referring to [5] for the
specific details.

In the notation of [5, Theorem 3.4], we partition $M$ as $L_{1}\cup L_{2}\cup
L_{3}\cup L_{4}$ in a certain way and then $M\cup\\{1^{s}\\}$ is realizable
for all $s\geq s_{1}+s_{2}+s_{3}+s_{4}-1$, where each $s_{i}$ is dependent on
$L_{i}$ for $1\leq i\leq 4$. Let $U_{i}$ be the underlying set of $L_{i}$ for
$1\leq i\leq 4$.

By [5, Lemma 3.12], we may take $s_{1}=1-2|U_{1}|+\sum_{x\in U_{1}}x$; hence
$s_{1}\leq\left(\sum_{i=1}^{k}x_{i}\right)-1$. By [5, Lemma 3.9], we may take
$s_{2}=\max(U_{2})-1$; hence $s_{2}\leq x_{k}-1$. By [5, Lemma 3.7], we may
take $s_{3}=\max(U_{3})-1$; hence $s_{3}\leq x_{k}-1$. By [5, Lemma 3.13], we
may take $s_{4}=\max(U_{4})-|U_{4}|$; hence $s_{4}\leq x_{k}-1$.

Combining these bounds we find that $L$ is realizable for all $s\geq
3x_{k}-5+\sum_{i=1}^{k}x_{i}$. ∎

The BHR Conjecture has close connections to many other problems and
conjectures concerning sequences with distinct partial sums or subgraphs of
$K_{v}$ other than paths; see [8] for more discussion of this. A recent paper
also makes a connection between the BHR Conjecture and the Traveling Salesman
Problem [4].

We are frequently concerned with the congruence classes of multiple elements
with respect to multiple integers. The following notation is useful for these
situations: if $x_{i}\equiv y_{i}\pmod{z_{i}}$ for $1\leq i\leq k$, then write

$(x_{1},\ldots,x_{k})\equiv(y_{1},\ldots,y_{k})\pmod{(z_{1},\ldots,z_{k})}.$

We also need the notion of a translation of a sequence
${\bm{h}}=[h_{1},\ldots,h_{v}]$ by an integer $m$:

${\bm{h}}+m=[h_{1}+m,\ldots,h_{v}+m].$

The translation of a sequence produces the same multiset of absolute
differences as the original sequence.

We require a lot of small examples of realizations for particular multisets.
These were mostly found using a heuristic algorithm implemented in GAP. Given
a target multiset $L$ of size $v-1$, the algorithm starts from a random
Hamiltonian path in $K_{v}$ and keeps trying to move to a Hamiltonian path
that is “closer” to realizing $L$—in the sense of trying to increase $|L\cap
L^{\prime}|$, where $L^{\prime}$ is the multiset realized by the path under
consideration—by removing an edge from the path and reconnecting the two
resulting paths in a different way. If it gets stuck before finding a
realization of $L$, then it tries again from a different starting path. For
the fairly small values of $v$ in which we are interested, this simple
algorithm is sufficient to find the desired realizations quickly. The programs
are available on the ArXiv page for this paper.

The most far-reaching components of Theorem 1.2 were proved using “linear”
realizations. A Hamiltonian path ${\bm{h}}=[h_{1},h_{2},\ldots,h_{v}]$ of
$K_{v}$ defines a multiset of absolute differences $L=\\{|h_{i}-h_{i+1}|:1\leq
i\leq v-1\\}$ with underlying set contained in $\\{1,\ldots,v-1\\}$. In this
situation, ${\bm{h}}$ is a linear realization of $L$. If $h_{1}=0$, then the
linear realization is standard; if $h_{1}=0$ and $h_{v}=v-1$, then the linear
realization is perfect. To emphasize the distinction between linear
realizations and realizations, realizations as defined above are sometimes
referred to as cyclic realizations.

Linear realizations are closely related to cyclic realizations. For example,
if each element in a multiset $L$ of size $v-1$ is at most $\lfloor
v/2\rfloor$, then a linear realization of $L$ is also a cyclic realization of
$L$. See [5] for further discussion.

What makes linear realizations so useful in addressing the BHR Conjecture,
standard and perfect ones especially, is their ability to be combined and
hence used in inductive arguments. This is the approach taken by Horak and
Rosa in [5] and the multisets $L$ given in Theorem 1.3 in fact have linear
realizations that are also cyclic realizations for the same $L$.

The main contribution of this work is to introduce an alternative object: the
“growable” realization, which we define in the next section. These are cyclic
realizations that can be used in inductive arguments in somewhat similar ways
to linear ones.

In Section 3 we reprove, with a much shorter proof, the result from [2] that
$\mathop{\rm BHR}(L)$ holds when $L$ has underlying set $U=\\{1,2,3\\}$ to
illustrate that this new tool is, in some ways, more powerful than existing
ones. We go on to prove instances of the BHR Conjecture that seem beyond the
reach of current techniques. In particular, we are able to add the following
items to Theorem 1.2:

  * •

$U=\\{1,4,5\\}$ (Section 3),

  * •

$U\subseteq\\{1,2,3,4\\}$ (Section 4),

  * •

$L=\\{1^{a},x^{b},(2x)^{c}\\}$ when $a\geq x-2$, $c$ is even and $b\geq
5x-2+c/2$ (Section 5),

  * •

$L=\\{1^{a},3^{b},6^{c}\\}$ when $c$ is odd and $b\geq 18+(c-1)/2$ (Section
5).

##  2 Growable Realizations

Growable realizations will let us move from solving $\mathop{\rm BHR}(L)$ to
$\mathop{\rm BHR}(L\cup\\{x^{x}\\})$ under certain circumstances. When this
can be done for multiple choices of $x$, this is a powerful tool.

Take $x$ with $0<x\leq v/2$. For a given $m$, with $0\leq m<v$, we shall embed
$K_{v}$ into $K_{v+x}$ as follows:

$y\mapsto\begin{cases}y\hskip 5.69054pt\text{when }y\leq m,\\\ y+x\hskip
5.69054pt\text{otherwise.}\end{cases}$

This embedding preserves some edge lengths and increases others.

######  Definition 2.1.

Let ${\bm{h}}=[h_{1},\ldots,h_{v}]$ be a cyclic realization of a multiset $L$.
Take $x$ and $m$ with $0<x\leq v/2$ and $0\leq m<v$. If each $y$ with
$m-x<y\leq m$ is incident with exactly one edge whose length is increased by
the embedding and there is no other edge whose length is increased, then say
that ${\bm{h}}$ is $x$-growable at $m$.

######  Example 2.2.

It is easy to see that the sequence $[6,4,3,0,7,1,5,2,8]$ is a cyclic
realization of $\\{1,2^{2},3^{4},4\\}$ and that it is $3$-growable at $2$. In
fact, we can represent this Hamiltonian path of $K_{9}$ writing in bold the
vertices not involved by the embedding $K_{9}\hookrightarrow K_{12}$, and
using the symbol $-$ for each edge whose length does not change and the symbol
$\cdots$ for each edge whose length increases by $3$:

$6-4-3\cdots\bm{0}-7-\bm{1}\cdots 5\cdots\bm{2}-8.$

Note that every vertex in bold is incident with exactly one edge $\cdots$.
Also, note that the edges $0-7$, $7-1$ and $2-8$ do not change length, since
their absolute differences are greater than
$\left\lfloor\frac{9}{2}\right\rfloor$.

Theorem 2.3 and its immediate consequence Theorem 2.5 are the core results for
using growable realizations.

######  Theorem 2.3.

Suppose a multiset $L$ has an $X$-growable realization. Then for each $x\in
X$, the multiset $L\cup\\{x^{x}\\}$ has an $X$-growable realization.

###### Proof.

Let ${\bm{g}}=[g_{1},\ldots,g_{v}]$ be an $X$-growable realization of a
multiset $L$. Take $x\in X$ and $m$ such that ${\bm{g}}$ is $x$-growable at
$m$. Each element $y$ with $m-x<y\leq m$ is adjacent to exactly one element
$z$ such that the edge between them is lengthened by the embedding of $K_{v}$
into $K_{v+x}$.

Applying the embedding we obtain a sequence
${\bm{h}^{\prime}}=[h_{1},\ldots,h_{v}]$ in $K_{v+x}$. Each adjacent pair
$y,z$ in ${\bm{g}}$ as above becomes a subsequence $(y,z+x)$ or $(z+x,y)$ in
${\bm{h}^{\prime}}$. Obtain a new sequence ${\bm{h}}$ in $K_{v+x}$ by
replacing each subsequence $(y,z+x)$ with $(y,y+x,z+x)$ and each subsequence
$(z+x,y)$ with $(z+x,y+x,y)$. As there is one pair for each $y$ in the range
$m-x<y\leq m$, this adds the elements $m+1,\ldots,m+x$ to the sequence and
hence ${\bm{h}}$ is a Hamiltonian path in $K_{v+x}$.

Now, ${\bm{h}}$ has the desired lengths because each pair of adjacent elements
in ${\bm{g}}$ whose length was fixed by the embedding are still adjacent in
${\bm{h}}$ and each adjacent pair $y,z$ whose length was not fixed is replaced
by a triple whose lengths are the original length and $x$. There are $x$ such
pairs.

If ${\bm{g}}$ is $x^{\prime}$-growable at $m^{\prime}$, then ${\bm{h}}$ is
$x^{\prime}$-growable at $m^{\prime}$ if $m^{\prime}\leq m$ and
$x^{\prime}$-growable at $m^{\prime}+x$ if $m^{\prime}>m$. ∎

######  Example 2.4.

Applying the embedding $K_{9}\hookrightarrow K_{12}$ to the $3$-growable
realization of Example 2.2 we obtain the sequence

$9-7-6\cdots 0-10-1\cdots 8\cdots 2-11.$

Now, following the proof of Theorem 2.3, we insert the vertices $3,4,5$,
replacing the edges $6\cdots 0$, $1\cdots 8$ and $8\cdots 2$ with $6-3\cdots
0$, $1\cdots 4-8$ and $8-5\cdots 2$, respectively. In this way, the sequence

$9-7-6-3\cdots 0-10-1\cdots 4-8-5\cdots 2-11$

is a cyclic realization of $\\{1,2^{2},3^{7},4\\}$, which is still
$3$-growable at $2$.

If a realization is $x$-growable for each $x\in X$ for some set $X$, then say
that it is $X$-growable.

######  Theorem 2.5.

Suppose a multiset $L$ has a realization that is
$\\{x_{1},\ldots,x_{k}\\}$-growable. Then the multiset
$L\cup\\{x_{1}^{x_{1}\ell_{1}},x_{2}^{x_{2}\ell_{2}},\ldots,x_{k}^{x_{k}\ell_{k}}\\}$
has a $\\{x_{1},\ldots,x_{k}\\}$-growable realization for any
$\ell_{1},\ell_{2},\ldots,\ell_{k}\geq 0$.

###### Proof.

Repeatedly apply Theorem 2.3. ∎

######  Example 2.6.

The sequence

$[0,3,6,2,1,13,10,11,14,12,9,8,5,4,7]$

is a cyclic realization of $L=\\{1^{4},2,3^{8},4\\}$. It is $1$-growable at
$8$ and $9$; it is $2$-growable at $3$; it is $3$-growable at $11$; and it is
$4$-growable at $5$.

If we apply Theorem 2.3 four times with $x=2$ and then three times with $x=3$
we get the sequence

$[0,3,5,7,9,11,14,10,8,6,4,2,1,30,27,24,21,18,19,$

$22,25,28,31,29,26,23,20,17,16,13,12,15]$,

which is a $\\{1,2,3,4\\}$-growable realization of
$\\{1^{4},2,3^{8},4\\}\cup\\{2^{8},3^{9}\\}=\\{1^{4},2^{9},3^{17},4\\}$.

Any standard linear realization (and hence any perfect realization) is
1-growable at 0.

Suppose we are investigating multisets that have underlying set
$U=\\{x_{1},\ldots,x_{k}\\}$. Using Theorem 2.5, a $U$-growable realization
for a multiset $L=\\{x_{1}^{a_{1}},\ldots,x_{k}^{a_{k}}\\}$ is sufficient to
cover all multisets $M=\\{x_{1}^{b_{1}},\ldots,x_{k}^{b_{k}}\\}$ with
$b_{i}\geq a_{i}$ for each $i$ and

$(b_{1},\ldots,b_{k})\equiv(a_{1},\ldots,a_{k})\pmod{(x_{1},\ldots,x_{k})}.$

This means that the task frequently breaks naturally into considering
$\prod_{i=1}^{k}x_{i}$ cases according to congruence modulo
$(x_{1},\ldots,x_{k})$.

We conclude this section with two lemmas that allow the expansion of the range
of values for which realizations are growable.

######  Lemma 2.7.

Suppose $L$ has an $X$-growable realization with $1\in X$ and $K$ has a
$Y$-growable perfect linear realization. Then $L\cup K$ has a $(X\cup
Y)$-growable realization.

###### Proof.

Suppose $|K|=k$ and let ${\bm{g}}=[g_{1},\ldots,g_{k+1}]$ be a $Y$-growable
perfect linear realization of $K$.

Apply Theorem 2.3 $k$ times with $x=1$ to the $X$-growable realization of $L$
to obtain an $X$-growable realization of $L\cup\\{1^{k}\\}$ with subsequence
$m,m+1,\ldots,m+k$. Replace this subsequence with ${\bm{g}}+m$ to obtain the
desired $(X\cup Y)$-growable realization of $L\cup K$. ∎

It is possible to take $Y$ to be the empty set in Lemma 2.7 to construct an
$X$-growable realization for $L\cup K$.

######  Lemma 2.8.

Suppose $L$ has an $X$-growable realization with $2\in X$. Let $y$ and $z$ be
even (possibly with $y=z$). Then $L\cup\\{1^{y+z-4},y^{y+1},z^{z+1}\\}$ has an
$(X\cup\\{y,z\\})$-growable realization.

###### Proof.

Apply Theorem 2.3 $y+z-1$ times with $x=2$ to the $X$-growable realization of
$L$ to obtain an $X$-growable realization of $L\cup\\{2^{2(y+z-1)}\\}$ with
the following two subsequences:

$[m,m+2,\ldots,m+2y+2z-2],[m-1,m+1,\ldots,m+2y+2z-3].$

The sequence

${\bm{g}}=[1,y+1,y+2,2,3,y+3,\ldots,y-1,2y-1,2y+z-1,2y+2z-1]$

uses the elements

$\\{1,2,\ldots,y-1,y+1,y+2,\ldots,2y-1,2y+z-1,2y+2z-1\\}$

and has edge-lengths $\\{1^{y-2},y^{y-1},z^{2}\\}$. The sequence

${\bm{h}}=[0,y,2y,2y+z,2y+z+1,2y+1,2y+2,2y+z+2,\ldots,2y+2z-2]$

uses the elements

$\\{0,y,2y,2y+1,\ldots,2y+z-2,2y+z,2y+z+1,\ldots,2y+2z-2\\},$

and has edge-lengths $\\{1^{z-2},y^{2},z^{z-1}\\}$. The elements used by
${\bm{g}}$ and ${\bm{h}}$ together are exactly those used in the two
subsequences from the realization of $L\cup\\{2^{2(y+z-1)}\\}$. Replace the
two subsequences with ${\bm{g}}+m-1$ and ${\bm{h}}+m-1$ respectively to obtain
a realization of $L\cup\\{1^{y+z-4},y^{y+1},z^{z+1}\\}$.

It is $y$-growable at $m+y-1$ because each $t$ in the range $m-1<t<m+y-1$ is
adjacent to $t+y>m+y-1$ and to $t\pm 1\leq m+y-1$, and $m+y-1$ is adjacent to
$m-1$ and $m+2y-1$. It is $z$-growable at $m+2y+z-2$ because each $t$ in the
range $m+2y-2<t<m+2y+z-2$ is adjacent to $t+z>m+2y+z-2$ and to $t\pm 1\leq
m+2y+z-2$, and $m+2y+z-2$ is adjacent to $m+2y-2$ and $m+2y+2z-2$. ∎

##  3 Complete Solutions for $U=\\{1,2,3\\}$ and $U=\\{1,4,5\\}$

Given any fixed set $U$, we may use growable realizations to try to prove
$\mathop{\rm BHR}(L)$ for all but finitely many multisets $L$ with underlying
set $U$. To do this, divide the problem into $\prod_{x\in U}x$ cases,
corresponding to the possible congruence classes of the number of occurrences
of each element $x\pmod{x}$. For each case, a finite number—possibly one—of
growable realizations can show that all but finitely many—possibly
zero—admissible $L$ matching these congruence classes has a realization. The
finitely many exceptions can then be dealt with directly. In this section we
illustrate this process for $U=\\{1,2,3\\}$ and $U=\\{1,4,5\\}$.

When $U=\\{1,2,3\\}$, the BHR Conjecture is already known to hold [2].
However, the self-contained proof given here in Theorem 3.1 is significantly
shorter, which gives an indication of the power of the method of growable
realizations compared to existing tools.

When $U=\\{1,4,5\\}$, from previous work we know that
$\\{1^{a},4^{b},5^{c}\\}$ is realizable when $a\geq 11$ or when both $a\geq 7$
and $b\geq c$ [8]. However, the proof of Theorem 3.3 does not rely on this
result.

######  Theorem 3.1.

Let $L=\\{1^{a},2^{b},3^{c}\\}$ be an admissible multiset with $a,b,c\geq 1$.
Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

We start with the $\\{1,2,3\\}$-growable cyclic realizations of
$\\{1,2^{b},3^{c}\\}$ described in the first part of Table 1, which allow to
cover all the $6$ possibilities of the congruence class combinations of
$(b,c)\pmod{(2,3)}$. Using Theorem 2.5 this proves $\mathop{\rm BHR}(L)$ for
all $a,b\geq 1$ and $c\geq 5$. To complete the case $b+c\geq 4$, we use the
$\\{1,2\\}$-growable realizations for
$(b,c)\in\\{(1,4),(2,2),(3,1),(3,2),(3,3),(4,1)\\}$ from the second part of
Table 1 and the $1$-growable realization of $\\{1,2,3^{3}\\}$, described in
Table 2.

Now, the cases when $b+c<4$ can be solved using the $1$-growable realizations
of $\\{1^{a},2^{b},3^{c}\\}$, described in Table 2. ∎

Table 1: $\\{1,2,3\\}$-growable cyclic realizations for $\\{1,2^{b},3^{c}\\}$:
they are $x$-growable at $m_{x}$. The congruence classes of $(b,c)$ are taken
modulo $(2,3)$.
$\begin{array}[]{llll}\hline\cr\text{Classes}&\text{Realizations}&(b,c)&(m_{1},m_{2},m_{3})\\\
\hline\cr(0,0)&[2,4,1,5,3,0,6]&(2,3)&(5,1,3)\\\
(0,1)&[3,6,0,5,2,1,7,4]&(2,4)&(2,3,4)\\\
(0,2)&[6,5,2,8,1,4,7,0,3]&(2,5)&(7,5,2)\\\
(1,0)&[8,5,2,3,6,0,7,1,4]&(1,6)&(1,6,3)\\\
(1,1)&[5,8,1,4,6,9,2,3,0,7]&(1,7)&(4,6,2)\\\
(1,2)&[6,1,4,7,5,0,3,2]&(1,5)&(4,1,2)\\\
\hline\cr(0,1)&[0,2,4,1,6,5,3]&(4,1)&(5,2,3)\\\
(0,2)&[3,1,4,5,2,0]&(2,2)&(4,1,-)\\\ (1,0)&[7,4,2,0,3,1,6,5]&(3,3)&(4,5,2)\\\
(1,1)&[2,5,1,3,6,0,4]&(1,4)&(1,3,-)\\\ &[4,2,5,3,1,0]&(3,1)&(1,3,-)\\\
(1,2)&[2,4,6,5,1,3,0]&(3,2)&(4,1,2)\\\ \hline\cr\end{array}$ Table 2:
$1$-growable cyclic realizations for $\\{1^{a},2^{b},3^{c}\\}$: they are
$1$-growable at $m_{1}$.
$\begin{array}[]{lll|lll}\hline\cr(a,b,c)&\text{Realizations}&m_{1}&(a,b,c)&\text{Realizations}&m_{1}\\\
\hline\cr(1,1,3)&[2,5,4,1,3,0]&4&(2,1,2)&[0,3,5,4,1,2]&3\\\
(2,2,1)&[3,1,0,5,2,4]&1&(3,1,1)&[0,5,4,1,3,2]&4\\\ \hline\cr\end{array}$

We now move on to $U=\\{1,4,5\\}$.

######  Lemma 3.2.

Let $L=\\{1^{a},4^{b},5^{c}\\}$ be an admissible multiset with $a\geq 2$. Then
$\mathop{\rm BHR}(L)$ holds.

###### Proof.

In view of Theorem 1.2.1, we may assume $b,c\geq 1$. We start with the
$\\{1,4,5\\}$-growable cyclic realizations of $\\{1^{2},4^{b},5^{c}\\}$
described in the first part of Table 4 (note that in this case $b+c\geq 7$).
These realizations allow to cover all the $20$ possibilities of the congruence
class combinations of $(b,c)\pmod{(4,5)}$. Using Theorem 2.5, this proves
$\mathop{\rm BHR}(L)$ for all $a\geq 2$, $b\geq 7$ and $c\geq 1$. The case
$2\leq b\leq 6$ with $b+c\geq 8$ can be solved using the $\\{1,5\\}$-growable
cyclic realizations of $\\{1^{2},4^{b},5^{c}\\}$ provided by Table 4, with the
exception of $(b,c)\equiv(2,4)\pmod{(4,5)}$. Furthermore, the same table gives
$5$-growable cyclic realizations of $\\{1^{2},4,5^{c}\\}$ for $c\geq 7$ with
$c\not\equiv 1\pmod{5}$. Note that the multisets $\\{1^{2},4,5^{5k+6}\\}$ are
not admissible.

To complete the case $b+c\geq 7$ we consider the $5$-growable cyclic
realization of $\\{1^{2},4^{2},5^{9}\\}$ and the $1$-growable cyclic
realizations of $\\{1^{2},4^{b},5^{7-b}\\}$, $2\leq b\leq 6$, given in Table
4, as well as the $\\{1,5\\}$-growable cyclic realization of
$\\{1^{3},4^{2},5^{9}\\}$ given in Table 3.

To conclude our proof, we use the $1$-growable cyclic realizations of
$\\{1^{a},4^{b},5^{c}\\}$ with $a+b+c=9$, described in Table 3. ∎

Table 3: $\\{1,5\\}$-growable cyclic realizations for
$\\{1^{a},4^{b},5^{c}\\}$, $a\geq 3$: they are $x$-growable at $m_{x}$.
$\begin{array}[]{llll}\hline\cr(a,b,c)&\text{Realizations}&(m_{1},m_{5})\\\
\hline\cr(3,1,6)&[6,7,2,1,5,0,10,4,9,3,8]&(9,4)\\\
(3,2,9)&[9,14,0,10,5,4,8,13,3,7,12,2,1,11,6]&(3,9)\\\
\hline\cr(3,1,5)&[8,3,2,7,1,6,5,0,9,4]&(2,-)\\\
(3,2,4)&[7,2,6,1,5,0,9,8,3,4]&(1,-)\\\ (3,3,3)&[3,2,8,4,9,0,5,1,6,7]&(8,-)\\\
(3,4,2)&[6,2,8,7,3,4,9,0,5,1]&(7,-)\\\ (3,5,1)&[5,6,2,8,9,4,0,1,7,3]&(7,-)\\\
(4,1,4)&[2,1,6,7,3,8,9,4,5,0]&(1,-)\\\ (4,2,3)&[7,8,4,9,3,2,1,6,5,0]&(4,-)\\\
(4,3,2)&[9,5,0,6,1,2,3,4,8,7]&(4,-)\\\ (4,4,1)&[0,9,4,3,7,8,2,6,5,1]&(8,-)\\\
(5,1,3)&[8,3,2,7,6,5,1,0,9,4]&(6,-)\\\ (5,2,2)&[5,4,9,0,1,2,8,3,7,6]&(8,-)\\\
(5,3,1)&[4,5,9,8,3,7,6,2,1,0]&(2,-)\\\ (6,1,2)&[3,4,8,9,0,5,6,7,2,1]&(8,-)\\\
(6,2,1)&[8,4,3,2,1,7,6,5,0,9]&(4,-)\\\ (7,1,1)&[3,2,1,0,4,9,8,7,6,5]&(8,-)\\\
\hline\cr\end{array}$ Table 4: $\\{1,4,5\\}$-growable cyclic realizations for
$\\{1^{2},4^{b},5^{c}\\}$: they are $x$-growable at $m_{x}$. The congruence
classes of $(b,c)$ are taken modulo $(4,5)$.
$\begin{array}[]{llll}\hline\cr\text{Classes}&\text{Realizations}&(b,c)&(m_{1},m_{4},m_{5})\\\
\hline\cr(0,0)&[5,9,1,6,7,2,10,3,8,4,11,0]&(4,5)&(9,4,5)\\\
(0,1)&[5,9,1,6,2,10,11,3,7,8,4,0]&(8,1)&(9,3,5)\\\
(0,2)&[5,6,1,10,9,0,4,8,12,3,7,2,11]&(8,2)&(8,3,5)\\\
(0,3)&[1,11,12,2,7,3,13,4,8,9,5,0,10,6]&(8,3)&(10,5,6)\\\
(0,4)&[1,6,7,2,9,5,0,10,3,8,4]&(4,4)&(9,3,4)\\\
(1,0)&[7,8,3,11,2,10,6,1,5,9,4,0,12]&(5,5)&(10,6,7)\\\
(1,1)&[10,1,6,2,11,12,3,7,8,4,0,9,5]&(9,1)&(9,3,5)\\\
(1,2)&[5,9,13,3,7,8,4,0,10,1,6,2,12,11]&(9,2)&(9,3,5)\\\
(1,3)&[5,9,2,7,6,1,0,4,8,3,10]&(5,3)&(9,3,5)\\\
(1,4)&[0,1,5,9,4,11,3,8,7,2,10,6]&(5,4)&(10,4,6)\\\
(2,0)&[4,9,13,0,10,5,1,11,6,2,3,8,12,7]&(6,5)&(1,4,7)\\\
(2,1)&[7,11,1,5,9,10,6,2,12,13,3,8,4,0]&(10,1)&(11,3,7)\\\
(2,2)&[1,6,2,9,5,0,10,3,7,8,4]&(6,2)&(9,3,5)\\\
(2,3)&[5,9,1,6,2,10,3,7,8,4,11,0]&(6,3)&(9,4,5)\\\
(2,4)&[5,6,1,10,9,0,8,4,12,3,7,2,11]&(6,4)&(8,4,5)\\\
(3,0)&[12,13,2,6,10,0,11,1,5,9,4,14,3,8,7]&(7,5)&(10,6,7)\\\
(3,1)&[10,3,7,8,4,0,1,6,2,9,5]&(7,1)&(9,3,5)\\\
(3,2)&[11,3,7,2,10,6,1,0,4,8,9,5]&(7,2)&(10,3,5)\\\
(3,3)&[11,12,3,8,4,0,9,5,1,10,2,7,6]&(7,3)&(9,3,6)\\\
(3,4)&[11,12,2,7,6,1,10,0,4,8,3,13,9,5]&(7,4)&(9,3,5)\\\
\hline\cr(0,1)&[12,11,3,8,4,0,5,9,1,10,2,7,6]&(4,6)&(9,5,6)\\\
(0,2)&[3,13,4,9,10,5,0,1,6,11,7,2,12,8]&(4,7)&(12,7,8)\\\
(0,3)&[12,2,6,1,11,7,3,13,8,9,14,10,0,5,4]&(4,8)&(7,3,4)\\\
(1,1)&[0,5,9,8,4,13,12,3,7,2,11,1,10,6]&(5,6)&(10,5,6)\\\
(1,2)&[4,9,5,1,12,7,2,3,8,13,14,10,0,11,6]&(5,7)&(1,5,8)\\\
(2,0)&[10,0,5,4,14,9,8,13,3,7,12,2,6,1,11]&(2,10)&(7,10,4)\\\
(2,1)&[2,7,0,6,1,8,3,4,9,10,5]&(2,6)&(1,4,5)\\\
(2,2)&[5,10,11,6,1,9,4,3,8,0,7,2]&(2,7)&(1,4,5)\\\
(2,3)&[5,10,1,6,11,12,7,2,3,8,0,9,4]&(2,8)&(1,4,5)\\\
(3,0)&[1,6,2,8,9,3,7,0,5,4,10]&(3,5)&(7,-,4)\\\
(3,1)&[2,7,0,8,3,4,9,1,5,10,11,6]&(3,6)&(1,4,6)\\\
(3,2)&[10,2,7,3,11,12,4,8,0,9,1,6,5]&(3,7)&(8,4,5)\\\
(3,3)&[4,9,0,1,10,5,6,11,2,12,7,3,13,8]&(3,8)&(3,6,8)\\\
(3,4)&[0,5,10,6,1,11,7,2,12,13,3,14,4,9,8]&(3,9)&(11,7,8)\\\
\hline\cr(1,0)&[11,2,7,12,3,8,13,4,9,10,6,1,0,5]&(1,10)&(-,9,4)\\\
(1,2)&[8,3,2,7,1,6,0,10,4,9,5]&(1,7)&(-,4,5)\\\
(1,3)&[6,11,4,9,8,1,2,7,3,10,5,0]&(1,8)&(-,5,6)\\\
(1,4)&[5,10,2,7,8,3,11,6,1,0,9,4,12]&(1,9)&(-,4,5)\\\
\hline\cr(2,4)&[6,11,2,7,12,3,8,4,5,10,1,0,9,13]&(2,9)&(-,5,6)\\\
\hline\cr(0,3)&[5,0,6,1,7,2,3,9,8,4]&(4,3)&(4,-,-)\\\
(1,2)&[4,8,3,9,5,0,6,7,1,2]&(5,2)&(4,-,-)\\\
(2,0)&[9,4,0,5,6,1,7,2,3,8]&(2,5)&(7,-,-)\\\
(2,1)&[9,3,4,0,6,5,1,7,2,8]&(6,1)&(6,-,-)\\\
(3,4)&[9,4,5,0,1,6,2,8,3,7]&(3,4)&(8,-,-)\\\ \hline\cr\end{array}$

######  Theorem 3.3.

Let $L=\\{1^{a},4^{b},5^{c}\\}$ be an admissible multiset with $a,b,c\geq 0$.
Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

By Lemma 3.2 we are left with the case $L=\\{1,4^{b},5^{c}\\}$ with $b,c\geq
1$. The multiset $L$ is admissible only if $b+c\geq 8$. Also, the following
multisets are not admissible: $\\{1,4,5^{5k+7}\\}$, $\\{1,4^{2},5^{5k+6}\\}$
and $\\{1,4^{4k+1},5\\}$. The $\\{4,5\\}$-growable cyclic realizations of
$\\{1,4^{b},5^{c}\\}$ described in the first part of Table 5 allow to cover
all the $20$ possibilities of the congruence class combinations of
$(b,c)\pmod{(4,5)}$. Using Theorem 2.5, this proves $\mathop{\rm BHR}(L)$ for
all $b\geq 2$ and $c\geq 6$. To complete the case $b=1$ we use the
$5$-growable cyclic realization of $\\{1,4,5^{11}\\}$ given in Table 5.
Finally, the case $c\leq 5$ can be solved using the $4$-growable cyclic
realizations of Table 6, as well as the cyclic realization
$[0,5,9,4,8,3,7,2,1,6]$ of $\\{1,4^{3},4^{5}\\}$. ∎

Table 5: $\\{4,5\\}$-growable cyclic realizations for $\\{1,4^{b},5^{c}\\}$:
they are $x$-growable at $m_{x}$. The congruence classes of $(b,c)$ are taken
modulo $(4,5)$.
$\begin{array}[]{llll}\hline\cr\text{Classes}&\text{Realizations}&(b,c)&(m_{4},m_{5})\\\
\hline\cr(0,0)&[4,9,5,0,1,6,10,3,7,2,8]&(4,5)&(3,4)\\\
(0,1)&[9,2,7,3,10,5,1,0,8,4,11,6]&(4,6)&(4,6)\\\
(0,2)&[4,9,1,5,0,8,12,11,6,10,2,7,3]&(4,7)&(3,4)\\\
(0,3)&[6,10,5,0,9,13,4,8,3,12,7,2,1,11]&(4,8)&(5,6)\\\
(0,4)&[3,14,4,9,5,0,10,6,1,11,12,7,2,13,8]&(4,9)&(7,8)\\\
(1,0)&[6,11,3,8,0,12,7,2,10,5,1,9,4]&(1,10)&(4,6)\\\
(1,1)&[4,9,5,0,8,3,12,7,11,10,1,6,2]&(5,6)&(3,4)\\\
(1,2)&[12,3,7,11,2,1,6,10,0,5,9,4,13,8]&(5,7)&(6,8)\\\
(1,3)&[4,9,10,3,8,2,7,1,6,0,5]&(1,8)&(3,4)\\\
(1,4)&[10,3,8,1,2,7,0,5,9,4,11,6]&(1,9)&(5,6)\\\
(2,0)&[7,2,11,6,1,10,5,0,9,13,12,3,8,4]&(2,10)&(3,4)\\\
(2,1)&[7,11,2,12,3,8,4,13,9,5,0,1,10,6]&(6,6)&(6,7)\\\
(2,2)&[1,6,0,5,10,3,7,2,8,9,4]&(2,7)&(3,4)\\\
(2,3)&[9,1,2,7,0,5,10,3,8,4,11,6]&(2,8)&(5,6)\\\
(2,4)&[9,4,12,3,8,0,1,6,11,7,2,10,5]&(2,9)&(4,5)\\\
(3,0)&[4,9,14,3,8,13,2,7,12,1,6,11,10,0,5]&(3,10)&(3,4)\\\
(3,1)&[4,9,3,8,2,6,10,0,5,1,7]&(3,6)&(3,4)\\\
(3,2)&[1,6,10,3,8,4,11,0,7,2,9,5]&(3,7)&(4,5)\\\
(3,3)&[10,5,0,4,9,1,6,11,2,3,8,12,7]&(3,8)&(6,7)\\\
(3,4)&[11,6,1,2,7,12,3,8,4,13,9,0,10,5]&(3,9)&(4,5)\\\
\hline\cr(1,1)&[1,6,10,11,2,7,12,3,8,13,4,9,0,5]&(1,11)&(9,4)\\\
\hline\cr\end{array}$ Table 6: $4$-growable cyclic realizations for
$\\{1,4^{b},5^{c}\\}$: they are $4$-growable at $m_{4}$.
$\begin{array}[]{lll}\hline\cr(b,c)&\text{Realizations}&m_{4}\\\
\hline\cr(4,4)&[7,3,8,4,9,0,5,1,6,2]&4\\\ (5,3)&[9,4,8,3,7,2,6,0,1,5]&4\\\
(5,4)&[9,10,3,7,1,5,0,6,2,8,4]&3\\\ (5,5)&[4,8,9,1,6,11,3,7,2,10,5,0]&3\\\
(6,2)&[7,3,8,4,0,9,5,1,6,2]&5\\\ (6,3)&[2,6,1,7,0,4,8,3,10,9,5]&3\\\
(6,4)&[5,6,1,9,4,0,8,3,11,7,2,10]&3\\\
(6,5)&[5,10,6,1,9,0,4,8,12,11,3,7,2]&4\\\ (7,1)&[7,3,9,4,8,2,6,0,1,5]&4\\\
(7,2)&[8,4,0,10,3,7,1,6,2,9,5]&4\\\ (7,3)&[4,8,0,1,5,9,2,6,11,7,3,10]&7\\\
(7,4)&[8,3,12,0,4,9,5,1,10,2,6,11,7]&6\\\
(7,5)&[5,10,0,9,13,4,8,7,3,12,2,6,1,11]&4\\\
(8,1)&[7,3,10,0,4,8,1,6,2,9,5]&3\\\ (8,2)&[4,8,0,5,9,1,6,2,10,11,3,7]&3\\\
(8,3)&[6,10,11,2,7,3,12,8,4,0,5,9,1]&5\\\
(9,2)&[4,9,8,12,3,7,11,2,6,10,1,5,0]&3\\\
(10,1)&[6,10,1,5,9,0,4,8,12,11,2,7,3]&3\\\ \hline\cr\end{array}$

##  4 A Complete Solution for $U\subseteq\\{1,2,3,4\\}$

In this section we prove $\mathop{\rm
BHR}\left(\\{1^{a},2^{b},3^{c},4^{d}\\}\right)$. In view of Theorem 1.2.2 and
1.2.3, we may assume $c,d\geq 1$. Also, by Theorem 1.2.4 we have as a starting
point that $\mathop{\rm BHR}(L)$ holds for $a\geq 3$ and also for $a=2$ when
$b\geq 1$. We begin by closing the case $a=2$.

######  Lemma 4.1.

Let $L=\\{1^{2},3^{c},4^{d}\\}$ be an admissible multiset with $c,d\geq 1$.
Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

First, note that $L$ is admissible only if $c+d\geq 5$. The first part of
Table 7 collects $\\{3,4\\}$-growable cyclic realizations for $L$ in each of
the $12$ possibilities of congruence class combinations of
$(c,d)\pmod{(3,4)}$. Using Theorem 2.5, this proves $\mathop{\rm BHR}(L)$
except in the following cases: $d=1,2$; $d=3$ and $c\not\equiv 0\pmod{3}$;
$d=4$ and $c\equiv 1\pmod{3}$. So, we prove the validity of $\mathop{\rm
BHR}(L)$ for these exceptional cases using the $3$-growable cyclic
realizations for the cases
$(c,d)\in\\{(4,1),(5,1),(6,1),(3,2),(4,2),(5,2),(2,3),(4,3),(4,4)\\}$ given in
Table 7. The last case left open is $L=\\{1^{2},3,4^{4}\\}$, for which we take
the following cyclic realization: $[0,4,5,1,2,6,3,7]$. ∎

Table 7: $\\{3,4\\}$-growable cyclic realizations for $\\{1^{2},3^{c},4^{d}\\}$: they are $x$-growable at $m_{x}$. The congruence classes of $(c,d)$ are taken modulo $(3,4)$. Classes | Realizations | $(c,d)$ | $(m_{3},m_{4})$ | Missing cases
---|---|---|---|---
$(0,0)$ | $[3,7,1,4,0,9,2,6,5,8]$ | $(3,4)$ | $(2,3)$ |
$(0,1)$ | $[3,7,10,2,6,5,1,9,8,4,0]$ | $(3,5)$ | $(2,5)$ | $d=1$
$(0,2)$ | $[6,9,10,2,1,5,8,0,4,7,3,11]$ | $(3,6)$ | $(5,6)$ | $d=2$
$(0,3)$ | $[1,5,6,2,8,0,3,7,4]$ | $(3,3)$ | $(3,4)$ |
$(1,0)$ | $[3,7,11,10,6,2,1,5,9,0,4,8]$ | $(1,8)$ | $(2,7)$ | $d=4$
$(1,1)$ | $[3,6,2,7,8,4,0,1,5]$ | $(1,5)$ | $(2,4)$ | $d=1$
$(1,2)$ | $[5,9,8,4,1,7,3,2,6,0]$ | $(1,6)$ | $(4,5)$ | $d=2$
$(1,3)$ | $[4,8,7,3,0,1,5,9,2,6,10]$ | $(1,7)$ | $(3,6)$ | $d=3$
$(2,0)$ | $[4,8,0,3,7,6,1,5,2]$ | $(2,4)$ | $(3,4)$ |
$(2,1)$ | $[5,9,3,6,2,8,7,4,0,1]$ | $(2,5)$ | $(4,5)$ | $d=1$
$(2,2)$ | $[4,0,10,6,9,2,5,1,8,7,3]$ | $(2,6)$ | $(2,3)$ | $d=2$
$(2,3)$ | $[8,0,4,3,11,7,6,9,1,5,2,10]$ | $(2,7)$ | $(8,3)$ | $d=3$
$(0,1)$ | $[5,8,9,2,6,3,0,1,4,7]$ | $(6,1)$ | $(4,5)$ |
$(0,2)$ | $[6,3,2,5,1,4,0,7]$ | $(3,2)$ | $(3,-)$ |
$(1,0)$ | $[8,5,6,2,10,9,1,4,0,7,3]$ | $(4,4)$ | $(2,3)$ | $(c,d)=(1,4)$
$(1,1)$ | $[2,5,6,3,7,4,1,0]$ | $(4,1)$ | $(4,-)$ |
$(1,2)$ | $[3,7,8,5,2,1,4,0,6]$ | $(4,2)$ | $(2,3)$ |
$(1,3)$ | $[2,6,3,0,9,5,1,8,7,4]$ | $(4,3)$ | $(3,5)$ |
$(2,1)$ | $[0,4,1,7,8,2,5,6,3]$ | $(5,1)$ | $(2,3)$ |
$(2,2)$ | $[5,8,1,4,7,3,2,6,9,0]$ | $(5,2)$ | $(4,5)$ |
$(2,3)$ | $[7,6,2,3,0,4,1,5]$ | $(2,3)$ | $(2,-)$ |

######  Lemma 4.2.

Let $L=\\{1,2^{b},3^{c},4^{d}\\}$ be an admissible multiset, where $b\geq 0$
is even and $c,d\geq 1$. Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

Suppose first $d\geq 5$. We start with the $\\{2,3,4\\}$-growable cyclic
realizations of $\\{1,3^{c},4^{d}\\}$ described in the first part of Table 8
(note that in this case $c+d\geq 6$). These realizations allow to cover all
the $12$ possibilities of the congruence class combinations of
$(c,d)\pmod{(3,4)}$. Using Theorem 2.5 this proves $\mathop{\rm BHR}(L)$
except when $c=1$ and $d\not\equiv 2\pmod{4}$. So, suppose $c=1$. Table 8 also
gives $\\{2,3,4\\}$-growable cyclic realizations for $d=7,8$, proving the
validity of $\mathop{\rm BHR}(L)$ for $b\geq 0$ even, $c=1$ and $d\equiv
0,3\pmod{4}$. Hence, we may assume $d\equiv 1\pmod{4}$. Note that the multiset
$L=\\{1,3,4^{4k+5}\\}$ does not satisfy the necessary condition, as
$4k+5>v-4=4k+4$. On the other hand, a $\\{2,3,4\\}$-growable cyclic
realization of $\\{1,2^{2},3,4^{5}\\}$ is given in Table 9. Next, we consider
the cases $1\leq d\leq 4$. Table 8 provides $\\{2,3\\}$-growable cyclic
realizations for $\\{1,3^{c},4^{d}\\}$, in the following cases: $d=1$ and
$5\leq c\leq 7$; $d=2$ and $4\leq c\leq 6$; $d=3,4$ and $3\leq c\leq 5$. It
also provides a $2$-growable cyclic realization for the multiset
$\\{1,3^{2},4^{4}\\}$. This completes the analysis for the admissible
multisets with $b=0$.

Now, Table 9 gives $2$-growable cyclic realizations for the multiset
$\\{1,2^{2},3^{c},4^{d}\\}$ when
$(c,d)\in\\{(1,3),(1,4),(2,2),(2,3),(3,1),(3,2),(4,1)\\}$, that is with $4\leq
c+d\leq 5$. This completes the analysis for the admissible multisets with
$b=2$. Finally, Table 9 also gives $2$-growable cyclic realizations for the
multiset $\\{1,2^{4},3^{c},4^{d}\\}$ for each $(c,d)$ in the set
$\\{(1,1),(1,2),(2,1)\\}$, concluding our proof. ∎

Table 8: $\\{2,3,4\\}$-growable cyclic realizations for $\\{1,3^{c},4^{d}\\}$: they are $x$-growable at $m_{x}$. The congruence classes of $(c,d)$ are taken modulo $(3,4)$. Classes | Realizations | $(c,d)$ | $(m_{2},m_{3},m_{4})$ | Missing cases
---|---|---|---|---
$(0,0)$ | $[3,6,1,4,0,5,2,7,8]$ | $(3,4)$ | $(6,2,3)$ |
$(0,1)$ | $[3,6,2,8,4,1,7,0,9,5]$ | $(3,5)$ | $(2,4,5)$ | $d=1$
$(0,2)$ | $[4,5,1,8,0,3,7,10,6,2,9]$ | $(3,6)$ | $(7,3,4)$ | $d=2$
$(0,3)$ | $[3,7,6,2,10,1,5,9,0,4,8,11]$ | $(3,7)$ | $(9,2,6)$ | $d=3$
$(1,0)$ | $[4,7,0,6,3,9,8,2,5,1]$ | $(4,4)$ | $(7,3,4)$ | $c=1$
$(1,1)$ | $[6,9,2,10,3,7,4,0,1,8,5]$ | $(4,5)$ | $(4,5,6)$ |  $c=1$ or $d=1$
$(1,2)$ | $[2,6,1,5,0,3,7,8,4]$ | $(1,6)$ | $(1,3,4)$ | $d=2$
$(1,3)$ | $[4,7,1,5,0,8,2,6,3]$ | $(4,3)$ | $(2,3,4)$ | $c=1$
$(2,0)$ | $[7,11,3,4,0,8,5,1,9,6,2,10]$ | $(2,8)$ | $(6,8,3)$ | $d=4$
$(2,1)$ | $[3,7,2,6,0,1,5,8,4]$ | $(2,5)$ | $(2,3,4)$ | $d=1$
$(2,2)$ | $[4,5,1,8,2,6,0,7,3,9]$ | $(2,6)$ | $(7,3,4)$ | $d=2$
$(2,3)$ | $[4,8,1,0,7,10,3,6,2,9,5]$ | $(2,7)$ | $(3,4,5)$ | $d=3$
$(1,0)$ | $[4,5,1,8,0,7,3,10,6,2,9]$ | $(1,8)$ | $(7,3,4)$ |
$(1,3)$ | $[3,7,1,4,8,2,6,0,9,5]$ | $(1,7)$ | $(2,4,5)$ |
$(0,1)$ | $[7,1,4,5,8,2,6,0,3]$ | $(6,1)$ | $(6,2,-)$ |
$(0,2)$ | $[5,6,3,9,2,8,1,4,7,0]$ | $(6,2)$ | $(4,5,-)$ |
$(0,3)$ | $[0,3,7,6,2,5,1,4]$ | $(3,3)$ | $(1,2,-)$ |
$(1,1)$ | $[5,2,9,8,1,4,7,0,6,3]$ | $(7,1)$ | $(7,4,-)$ |
$(1,2)$ | $[0,5,2,6,1,4,3,7]$ | $(4,2)$ | $(2,3,-)$ |
$(2,0)$ | $[10,9,2,6,3,0,7,4,1,8,5]$ | $(5,4)$ | $(8,4,5)$ | $(c,d)=(2,4)$
$(2,1)$ | $[2,5,0,1,6,3,7,4]$ | $(5,1)$ | $(3,4,-)$ |
$(2,2)$ | $[2,5,8,7,3,0,6,1,4]$ | $(5,2)$ | $(1,3,-)$ |
$(2,3)$ | $[3,0,6,7,1,4,8,5,2,9]$ | $(5,3)$ | $(5,2,-)$ |
$(2,0)$ | $[2,6,7,3,0,4,1,5]$ | $(2,4)$ | $(1,-,-)$ |
Table 9: $\\{2,3,4\\}$-growable cyclic realizations for $\\{1,2^{b},3^{c},4^{d}\\}$, with $b\geq 2$ even: they are $x$-growable at $m_{x}$. The congruence classes of $(c,d)$ are taken modulo $(3,4)$. Classes | Realizations | $(b,c,d)$ | $(m_{2},m_{3},m_{4})$
---|---|---|---
$(1,1)$ | $[7,8,2,6,0,4,1,9,5,3]$ | $(2,1,5)$ | $(6,2,3)$
$(0,1)$ | $[6,4,1,2,5,7,3,0]$ | $(2,3,1)$ | $(5,2,-)$
$(0,2)$ | $[4,7,5,1,8,0,3,6,2]$ | $(2,3,2)$ | $(1,3,4)$
$(1,0)$ | $[1,5,8,6,2,7,0,4,3]$ | $(2,1,4)$ | $(6,2,3)$
$(1,1)$ | $[3,6,0,4,1,8,7,5,2]$ | $(2,4,1)$ | $(6,2,3)$
$(1,3)$ | $[1,0,4,6,2,5,3,7]$ | $(2,1,3)$ | $(3,4,-)$
$(2,2)$ | $[7,6,2,4,1,5,3,0]$ | $(2,2,2)$ | $(1,3,-)$
$(2,3)$ | $[3,5,7,8,2,6,1,4,0]$ | $(2,2,3)$ | $(6,2,3)$
$(1,1)$ | $[0,3,1,7,5,4,2,6]$ | $(4,1,1)$ | $(1,2,-)$
$(1,2)$ | $[3,5,7,8,6,2,0,4,1]$ | $(4,1,2)$ | $(6,2,3)$
$(2,1)$ | $[1,3,5,8,2,4,0,7,6]$ | $(4,2,1)$ | $(6,2,-)$

######  Lemma 4.3.

Let $L=\\{1,2^{b},3^{c},4^{d}\\}$ be an admissible multiset, where $b\geq 1$
is odd and $c,d\geq 1$. Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

The first part of Table 10 gives $\\{2,3,4\\}$-growable cyclic realizations
for $\\{1,2,3^{c},4^{d}\\}$ for each of the $12$ possibilities of congruence
class combinations of $(c,d)\pmod{(3,4)}$. Note that $c+d\geq 5$. Using
Theorem 2.5, this proves $\mathop{\rm BHR}(L)$ except for the following cases:
$d=1,2$; $d=3$ and $c\not\equiv 0\pmod{3}$; $d=4$ and $c\equiv 1\pmod{3}$. So,
we prove the validity of $\mathop{\rm BHR}(L)$ for these exceptional cases
using $\\{2,3\\}$-growable cyclic realizations for $\\{1,2,3^{c},4^{d}\\}$ and
a $2$-growable cyclic realization for $\\{1,2,3,4^{4}\\}$, which can be found
in Table 10.

To conclude the proof we have to consider the cases when $c+d\leq 4$. Table 10
also provides $2$-growable cyclic realizations for $\\{1,2^{3},3^{c},4^{d}\\}$
when $(c,d)$ is in the set $\\{(1,2),(1,3),(2,1),(2,2),(3,1)\\}$, and for
$\\{1,2^{5},3,4\\}$. ∎

Table 10: $\\{2,3,4\\}$-growable cyclic realizations for $\\{1,2^{b},3^{c},4^{d}\\}$, with $b\geq 1$ odd: they are $x$-growable at $m_{x}$. The congruence classes of $(c,d)$ are taken modulo $(3,4)$. Classes | Realizations | $(b,c,d)$ | $(m_{2},m_{3},m_{4})$ | Missing cases
---|---|---|---|---
$(0,0)$ | $[9,2,6,0,4,1,7,8,5,3]$ | $(1,3,4)$ | $(6,2,3)$ |
$(0,1)$ | $[5,8,1,9,10,2,6,4,0,7,3]$ | $(1,3,5)$ | $(8,4,5)$ | $d=1$
$(0,2)$ | $[3,5,9,1,4,0,8,7,10,6,2,11]$ | $(1,3,6)$ | $(6,2,3)$ | $d=2$
$(0,3)$ | $[4,7,3,0,1,5,8,6,2]$ | $(1,3,3)$ | $(1,3,4)$ |
$(1,0)$ | $[10,6,2,11,3,7,9,1,5,4,0,8]$ | $(1,1,8)$ | $(7,8,4)$ | $d=4$
$(1,1)$ | $[2,6,7,3,0,5,1,8,4]$ | $(1,1,5)$ | $(1,3,4)$ | $d=1$
$(1,2)$ | $[3,4,0,6,2,8,1,5,9,7]$ | $(1,1,6)$ | $(6,2,3)$ | $d=2$
$(1,3)$ | $[9,2,6,5,1,10,3,7,0,8,4]$ | $(1,1,7)$ | $(8,3,5)$ | $d=3$
$(2,0)$ | $[2,6,1,4,0,8,5,7,3]$ | $(1,2,4)$ | $(1,2,3)$ |
$(2,1)$ | $[8,1,5,4,0,6,2,9,7,3]$ | $(1,2,5)$ | $(7,2,4)$ | $d=1$
$(2,2)$ | $[3,7,0,4,6,10,2,5,1,8,9]$ | $(1,2,6)$ | $(7,2,4)$ | $d=2$
$(2,3)$ | $[7,11,3,4,0,9,1,5,8,10,6,2]$ | $(1,2,7)$ | $(6,8,3)$ | $d=3$
$(0,1)$ | $[4,7,9,2,6,3,0,1,8,5]$ | $(1,6,1)$ | $(3,4,5)$ |
$(0,2)$ | $[2,5,1,0,6,3,7,4]$ | $(1,3,2)$ | $(3,4,-)$ |
$(1,0)$ | $[3,7,10,8,0,4,5,1,9,6,2]$ | $(1,4,4)$ | $(7,2,4)$ | $(c,d)=(1,4)$
$(1,1)$ | $[0,6,3,7,4,1,2,5]$ | $(1,4,1)$ | $(2,4,-)$ |
$(1,2)$ | $[3,7,6,0,4,1,8,5,2]$ | $(1,4,2)$ | $(1,2,3)$ |
$(1,3)$ | $[3,6,9,7,0,1,5,2,8,4]$ | $(1,4,3)$ | $(2,3,4)$ |
$(2,1)$ | $[3,6,7,1,4,0,2,5,8]$ | $(1,5,1)$ | $(6,2,3)$ |
$(2,2)$ | $[7,1,4,0,2,5,8,9,6,3]$ | $(1,5,2)$ | $(6,2,3)$ |
$(2,3)$ | $[4,0,3,1,5,2,6,7]$ | $(1,2,3)$ | $(1,2,-)$ |
$(1,0)$ | $[3,7,6,2,0,4,1,5]$ | $(1,1,4)$ | $(1,-,-)$ |
$(0,1)$ | $[3,6,8,7,5,2,0,4,1]$ | $(3,3,1)$ | $(6,2,3)$ |
$(1,0)$ | $[4,6,0,8,7,3,9,1,5,2]$ | $(3,1,4)$ | $(7,3,4)$ |
$(1,1)$ | $[4,2,0,8,6,3,1,5,7]$ | $(5,1,1)$ | $(6,3,-)$ |
$(1,2)$ | $[4,6,2,5,3,7,1,0]$ | $(3,1,2)$ | $(3,4,-)$ |
$(1,3)$ | $[2,6,7,0,3,5,1,8,4]$ | $(3,1,3)$ | $(1,3,4)$ |
$(2,1)$ | $[5,2,0,1,7,3,6,4]$ | $(3,2,1)$ | $(3,4,-)$ |
$(2,2)$ | $[4,6,0,2,5,1,8,7,3]$ | $(3,2,2)$ | $(2,3,4)$ |

######  Lemma 4.4.

Let $L=\\{2^{b},3^{c},4^{d}\\}$ be an admissible multiset, where $b\geq 1$ is
odd and $c,d\geq 1$. Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

The first part of Table 11 gives $\\{2,3,4\\}$-growable cyclic realizations
for $\\{2,3^{c},4^{d}\\}$ in each of the $12$ possibilities of congruence
class combinations of $(c,d)\pmod{(3,4)}$. Note that $c+d\geq 6$. Using
Theorem 2.5, this proves $\mathop{\rm BHR}(L)$ except for the following cases:
$d=1,2,3$; $d=4,5$ and $c\equiv 2\pmod{3}$; $c=1$ and $d\equiv 0,1\pmod{4}$.
Next, we consider the case $c\geq 2$ and $1\leq d\leq 5$, using
$\\{2,3\\}$-growable cyclic realizations for $\\{2,3^{c},4^{d}\\}$. For the
exceptional case $\\{2,3^{2},4^{4}\\}$ we use a $2$-growable cyclic
realization. Now we complete the case $c\geq 2$: Table 11 also provides
$2$-growable cyclic realization for the multisets $\\{2^{3},3^{c},4^{d}\\}$
when $(c,d)\in\\{(2,2),(2,3),(3,1),(3,2),(4,1)\\}$, and for the multiset
$\\{2^{5},3^{2},4\\}$.

Finally, we assume $c=1$. Note that the multiset $\\{2,3,4^{4k+5}\\}$ does not
satisfy the necessary condition. For the multisets $\\{2,3,4^{4k+8}\\}$ we use
the $4$-growable realization $[2,6,10,3,7,4,0,9,5,1,8]$ of $\\{2,3,4^{8}\\}$.
Table 11 gives $\\{2,4\\}$-growable cyclic realizations for the multisets
$\\{2^{3},3,4^{4}\\}$ and $\\{2^{3},3,4^{5}\\}$; it also gives $2$-growable
cyclic realizations for the multisets $\\{2^{3},3,4^{3}\\}$, $\\{2^{5},3,4\\}$
and $\\{2^{5},3,4^{2}\\}$. ∎

Table 11: $\\{2,3,4\\}$-growable cyclic realizations for $\\{2^{b},3^{c},4^{d}\\}$, with $b\geq 1$ odd: they are $x$-growable at $m_{x}$. The congruence classes of $(c,d)$ are taken modulo $(3,4)$. Classes | Realizations | $(b,c,d)$ | $(m_{2},m_{3},m_{4})$ | Missing cases
---|---|---|---|---
$(0,0)$ | $[2,6,8,5,0,4,1,7,3]$ | $(1,3,4)$ | $(1,2,3)$ |
$(0,1)$ | $[2,5,1,8,4,0,6,9,7,3]$ | $(1,3,5)$ | $(1,2,4)$ | $d=1$
$(0,2)$ | $[3,6,10,7,0,9,2,5,1,8,4]$ | $(1,3,6)$ | $(2,3,4)$ | $d=2$
$(0,3)$ | $[6,10,2,5,9,0,8,4,1,3,11,7]$ | $(1,3,7)$ | $(5,6,7)$ | $d=3$
$(1,0)$ | $[3,6,9,5,2,8,0,4,1,7]$ | $(1,4,4)$ | $(6,2,3)$ | $c=1$
$(1,1)$ | $[2,5,9,6,3,10,8,1,4,0,7]$ | $(1,4,5)$ | $(6,7,3)$ |  $c=1$ or $d=1$
$(1,2)$ | $[3,7,2,6,0,5,1,8,4]$ | $(1,1,6)$ | $(2,3,4)$ | $d=2$
$(1,3)$ | $[2,6,0,4,8,1,5,9,7,3]$ | $(1,1,7)$ | $(1,2,5)$ | $d=3$
$(2,0)$ | $[10,2,6,3,11,7,5,1,9,0,8,4]$ | $(1,2,8)$ | $(8,3,5)$ | $d=4$
$(2,1)$ | $[7,11,8,12,3,5,9,0,4,1,10,6,2]$ | $(1,2,9)$ | $(6,7,3)$ | $d=1,5$
$(2,2)$ | $[2,6,0,3,7,9,5,1,8,4]$ | $(1,2,6)$ | $(1,3,5)$ | $d=2$
$(2,3)$ | $[9,2,5,1,8,0,7,3,10,6,4]$ | $(1,2,7)$ | $(7,3,4)$ | $d=3$
$(0,1)$ | $[3,6,0,4,1,7,5,2,8]$ | $(1,6,1)$ | $(6,2,3)$ |
$(0,2)$ | $[4,7,1,5,2,9,6,3,0,8]$ | $(1,6,2)$ | $(7,3,4)$ |
$(0,3)$ | $[0,4,1,7,3,6,2,5]$ | $(1,3,3)$ | $(2,3,-)$ |
$(1,1)$ | $[3,6,9,2,5,1,8,0,7,4]$ | $(1,7,1)$ | $(7,3,4)$ |
$(1,2)$ | $[7,1,4,0,5,2,6,3]$ | $(1,4,2)$ | $(2,3,-)$ |
$(1,3)$ | $[3,6,0,4,2,7,1,5,8]$ | $(1,4,3)$ | $(6,2,3)$ |
$(2,0)$ | $[6,10,2,9,1,4,8,0,3,7,5]$ | $(1,5,4)$ | $(4,5,6)$ | $(c,d)=(2,4)$
$(2,1)$ | $[2,6,1,3,7,4,0,5,8]$ | $(1,2,5)$ | $(1,4,-)$ |
| $[1,4,7,3,6,0,5,2]$ | $(1,5,1)$ | $(2,4,-)$ |
$(2,2)$ | $[3,6,0,4,1,8,5,2,7]$ | $(1,5,2)$ | $(6,2,3)$ |
$(2,3)$ | $[9,6,2,8,1,5,3,0,7,4]$ | $(1,5,3)$ | $(7,3,4)$ |
$(2,0)$ | $[7,3,6,2,4,0,5,1]$ | $(1,2,4)$ | $(3,-,-)$ |
$(0,1)$ | $[1,6,0,2,5,3,7,4]$ | $(3,3,1)$ | $(3,4,-)$ |
$(0,2)$ | $[7,1,4,0,2,6,8,5,3]$ | $(3,3,2)$ | $(6,2,3)$ |
$(1,1)$ | $[3,6,8,2,5,7,0,4,1]$ | $(3,4,1)$ | $(6,2,3)$ |
$(2,1)$ | $[5,7,3,1,8,2,0,6,4]$ | $(5,2,1)$ | $(4,5,-)$ |
$(2,2)$ | $[2,4,1,5,7,3,0,6]$ | $(3,2,2)$ | $(1,2,-)$ |
$(2,3)$ | $[3,5,7,0,4,1,6,2,8]$ | $(3,2,3)$ | $(6,2,3)$ |
$(1,0)$ | $[3,7,5,0,4,1,8,6,2]$ | $(3,1,4)$ | $(1,2,3)$ |
$(1,1)$ | $[5,7,1,3,0,6,2,4]$ | $(5,1,1)$ | $(1,2,-)$ |
$(1,2)$ | $[4,6,8,1,5,2,0,7,3]$ | $(5,1,2)$ | $(2,3,4)$ |
$(1,3)$ | $[1,7,3,5,2,6,4,0]$ | $(3,1,3)$ | $(3,4,-)$ |
$(1,4)$ | $[5,9,1,7,3,0,8,2,6,4]$ | $(3,1,5)$ | $(3,4,5)$ |

######  Theorem 4.5.

Let $L=\\{1^{a},2^{b},3^{c},4^{d}\\}$ be an admissible multiset with
$a,b,c,d\geq 0$. Then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

By Theorem 1.2.2–4 we may assume $0\leq a\leq 2$ and $c,d\geq 1$. If $a=2$ the
result follows from Theorem 1.2.4 and Lemma 4.1. Suppose now $a=1$. If $b$ is
even we apply Lemma 4.2, otherwise we apply Lemma 4.3. Finally, assume $a=0$.
By [5] we may assume $b\geq 1$. If $b$ is odd we apply Lemma 4.4 and so, we
may also assume $b\geq 2$ is even.

We start with the $\\{2,3,4\\}$-growable cyclic realizations of
$L=\\{2^{2},3^{c},4^{d}\\}$ for each of the $12$ possibilities of congruence
class combinations of $(c,d)\pmod{(3,4)}$ described in the first part of Table
12. Note that $c+d\geq 5$. Using Theorem 2.5, this proves $\mathop{\rm
BHR}(L)$ except for the following cases: $d=1,2$; $d=3$ and $c\not\equiv
0\pmod{3}$; $d=4$ and $c\equiv 1\pmod{3}$. For these exceptions, Table 12 also
gives $\\{2,3\\}$-growable cyclic realizations when
$(c,d)\in\\{(4,1),(5,1),(6,1),(3,2),(4,2),(5,2),(2,3),(4,3),(4,4)\\}$ and a
$2$-growable cyclic realization for $\\{2^{2},3,4^{4}\\}$.

We are left to the cases $c+d\leq 4$. This table also provides a $2$-growable
cyclic realization for the multiset $\\{2^{4},3^{c},4^{d}\\}$ when
$(c,d)\in\\{(1,2),(1,3),(2,1),(2,2),(3,1)\\}$, and for the multiset
$\\{2^{6},3,4\\}$. ∎

Table 12: $\\{2,3,4\\}$-growable cyclic realizations for $\\{2^{b},3^{c},4^{d}\\}$, with $b\geq 2$ even: they are $x$-growable at $m_{x}$. The congruence classes of $(c,d)$ are taken modulo $(3,4)$. Classes | Realizations | $(b,c,d)$ | $(m_{2},m_{3},m_{4})$ | Missing cases
---|---|---|---|---
$(0,0)$ | $[2,5,9,6,8,0,4,1,7,3]$ | $(2,3,4)$ | $(1,2,3)$ |
$(0,1)$ | $[8,0,7,3,10,1,5,2,9,6,4]$ | $(2,3,5)$ | $(7,3,4)$ | $d=1$
$(0,2)$ | $[8,0,4,2,10,1,5,7,11,3,6,9]$ | $(2,3,6)$ | $(7,8,3)$ | $d=2$
$(0,3)$ | $[3,6,1,5,8,2,4,0,7]$ | $(2,3,3)$ | $(6,2,3)$ |
$(1,0)$ | $[4,8,0,2,6,10,1,9,5,3,11,7]$ | $(2,1,8)$ | $(3,6,7)$ | $d=4$
$(1,1)$ | $[4,8,5,1,6,2,0,7,3]$ | $(2,1,5)$ | $(2,3,4)$ | $d=1$
$(1,2)$ | $[4,8,0,2,6,9,5,1,7,3]$ | $(2,1,6)$ | $(2,3,5)$ | $d=2$
$(1,3)$ | $[4,8,1,5,7,0,9,2,6,3,10]$ | $(2,1,7)$ | $(8,3,5)$ | $d=3$
$(2,0)$ | $[2,6,0,3,7,5,1,8,4]$ | $(2,2,4)$ | $(1,3,4)$ |
$(2,1)$ | $[4,7,1,5,3,9,6,2,8,0]$ | $(2,2,5)$ | $(7,3,4)$ | $d=1$
$(2,2)$ | $[5,8,10,3,7,0,4,6,2,9,1]$ | $(2,2,6)$ | $(8,4,5)$ | $d=2$
$(2,3)$ | $[10,2,6,8,0,9,5,1,11,3,7,4]$ | $(2,2,7)$ | $(9,3,6)$ | $d=3$
$(0,1)$ | $[4,7,9,6,3,0,8,1,5,2]$ | $(2,6,1)$ | $(7,3,4)$ |
$(0,2)$ | $[2,5,7,3,6,0,4,1]$ | $(2,3,2)$ | $(2,3,-)$ |
$(1,0)$ | $[0,3,7,10,8,1,5,2,9,6,4]$ | $(2,4,4)$ | $(7,3,4)$ | $(c,d)=(1,4)$
$(1,1)$ | $[0,3,1,6,2,5,7,4]$ | $(2,4,1)$ | $(5,2,-)$ |
$(1,2)$ | $[3,6,1,4,0,7,5,2,8]$ | $(2,4,2)$ | $(6,2,3)$ |
$(1,3)$ | $[8,1,5,2,0,7,3,9,6,4]$ | $(2,4,3)$ | $(7,3,4)$ |
$(2,1)$ | $[7,5,2,8,1,4,0,6,3]$ | $(2,5,1)$ | $(6,2,3)$ |
$(2,2)$ | $[9,1,5,2,8,6,3,0,7,4]$ | $(2,5,2)$ | $(7,3,4)$ |
$(2,3)$ | $[7,3,6,4,0,2,5,1]$ | $(2,2,3)$ | $(3,4,-)$ |
$(1,0)$ | $[0,4,2,6,1,5,3,7]$ | $(2,1,4)$ | $(3,-,-)$ |
$(0,1)$ | $[2,5,7,0,4,1,8,6,3]$ | $(4,3,1)$ | $(6,2,3)$ |
$(1,1)$ | $[7,5,2,0,4,6,8,1,3]$ | $(6,1,1)$ | $(6,2,-)$ |
$(1,2)$ | $[7,1,3,5,2,6,4,0]$ | $(4,1,2)$ | $(3,4,-)$ |
$(1,3)$ | $[3,7,0,4,6,8,1,5,2]$ | $(4,1,3)$ | $(1,2,4)$ |
$(2,1)$ | $[1,3,0,6,2,4,7,5]$ | $(4,2,1)$ | $(5,2,-)$ |
$(2,2)$ | $[8,6,2,0,4,1,7,5,3]$ | $(4,2,2)$ | $(6,2,3)$ |

The success in proving these small cases leads us to make the following
conjecture, which says that the method of the previous section and this one is
always successful.

######  Conjecture 4.6.

For any fixed set $U$, there is a finite set of growable realizations with
underlying set $U$ that implies the existence of realizations for all but
finitely many admissible multisets $L$ that have underlying set $U$.

If Conjecture 4.6 is true, then the BHR Conjecture for any given underlying
set can be proved with a finite set of realizations.

##  5 A Partial Solution for $U=\\{1,x,2x\\}$

In previous sections we have seen how it is possible to completely prove the
BHR Conjecture for a fixed $U$ by the construction of one or more base case
realizations for each of $\prod_{x\in U}x$ cases. In this section we develop
ways to produce general results with fewer base cases.

Our main goal is Theorem 5.10, which says that $\mathop{\rm BHR}(L)$ holds for
$L=\\{1^{a},x^{b},(2x)^{c}\\}$ when $a\geq x-2$, $c$ is even, and $b\geq
5x-2+c/2$. When $x$ is even, this covers many instances not covered by Theorem
1.2.8. When $x$ is odd, the instances covered are all new.

######  Lemma 5.1.

Suppose $L$ has an $X$-growable realization and take $x\in X$. Take $i$ with
$1\leq i\leq x$. Then $L\cup\\{x^{3x-2i},(2x)^{2i}\\}$ has an $X$-growable
realization.

###### Proof.

Apply Theorem 2.3 three times to the $x$-growable realization of $L$ to obtain
an $X$-growable realization of $L\cup\\{x^{3x}\\}$ with each of the
subsequences

$[m,m+x,m+2x,m+3x],[m-1,m-1+x,m-1+2x,m-1+3x],\ldots,$

$[m-x+1,m+1,m+1+x,m+1+2x]$

appearing, possibly reversed. Each subsequence has differences $\\{x^{3}\\}$.
Take $i$ of the subsequences and in each switch the middle two elements (so,
for example, the first would become $[m,m+2x,m+x,m+3x]$). Each time we perform
this operation we obtain a subsequence with differences $\\{x,(2x)^{2}\\}$
instead of $\\{x^{3}\\}$. After performing it $i$ times the new differences
are $\\{x^{3x-2i},(2x)^{2i}\\}$.

These operations do not interfere with growability: if the original
realization is $y$-growable at $m^{\prime}$, then the new realization is
$y$-growable at $m^{\prime}$ if $m^{\prime}\leq m$ and at $m^{\prime}+3x$
otherwise. ∎

Let $L=\\{1^{a},x^{b},(2x)^{c}\\}$. When $x=1$ or 2 $\mathop{\rm BHR}(L)$
follows from Theorem 1.2.1 or 1.2.2 respectively, so $x=3$ is the first open
case. We treat the $x=3$ case first both as an illustration of the general
method and because some of the later constructions require $x>3$.

######  Lemma 5.2.

Let $L=\\{1^{a},3^{b},6^{c}\\}$. If $c$ is even and $b\geq 13+c/2$, then
BHR($L$) holds; if $c$ is odd and $b\geq 18+(c-1)/2$, then BHR($L$) holds.

###### Proof.

By Theorem 1.2.1 we may assume that $a,b,c\geq 1$. The multiset $L$ is not
admissible when $a=1$ and $b+c\equiv 1\pmod{3}$.

Table 13 gives $\\{1,3\\}$-growable realizations for

$(a,b,c)\in\\{(2,4,0),(1,5,0),(1,6,0),(1,10,1),(1,11,1),(2,9,1)\\}.$

First we use Lemma 5.1 along with the realizations of Table 13 to obtain a
$\\{1,3\\}$-growable realization of
$L^{\prime}=\\{1^{a^{\prime}},3^{b^{\prime}},6^{c^{\prime}}\\}$ with
$a^{\prime}\in\\{1,2\\}$, $b^{\prime}\equiv b\pmod{3}$ and $c^{\prime}\leq 5$
such that $c^{\prime}\equiv c\pmod{6}$. We have to distinguish cases according
to the congruence class of $c$ modulo $6$.

Table 13: $\\{1,3\\}$-growable realizations of $\\{1^{a},3^{b},6^{c}\\}$.
Where they are $1$\- or $3$-growable is indicated by $(m_{1},m_{3})$.
$\begin{array}[]{llll}\hline\cr\text{name}&\text{realization}&(a,b,c)&(m_{1},m_{3})\\\
\hline\cr{\bm{g}_{1}}&[6,5,1,4,0,3,2]&(2,4,0)&(4,2)\\\
{\bm{g}_{2}}&[3,0,6,2,5,1,4]&(1,5,0)&(5,2)\\\
{\bm{g}_{3}}&[5,2,7,0,3,6,1,4]&(1,6,0)&(6,2)\\\
{\bm{g}_{4}}&[2,12,9,6,3,0,10,7,4,5,8,1,11]&(1,10,1)&(3,5)\\\
{\bm{g}_{5}}&[5,2,13,10,7,8,11,0,3,6,9,12,4,1]&(1,11,1)&(6,8)\\\
{\bm{g}_{6}}&[9,6,3,0,10,7,8,11,1,4,5,12,2]&(2,9,1)&(6,8)\\\
\hline\cr\end{array}$

When $c$ is even, we start with ${\bm{g}_{1}}$, ${\bm{g}_{2}}$ or
${\bm{g}_{3}}$. If $c\equiv 0\pmod{6}$, then start by taking ${\bm{g}_{1}}$,
${\bm{g}_{2}}$ or ${\bm{g}_{3}}$ according to whether $b$ is congruent to 1, 2
or $0\pmod{3}$ respectively. If $c\equiv 2\pmod{6}$, then start by taking
${\bm{g}_{1}}$, ${\bm{g}_{2}}$ or ${\bm{g}_{3}}$ according to whether $b$ is
congruent to 2, 0 or $1\pmod{3}$ respectively and apply Lemma 5.1 with $i=1$.
If $c\equiv 4\pmod{6}$, then start by taking ${\bm{g}_{1}}$, ${\bm{g}_{2}}$ or
${\bm{g}_{3}}$ according to whether $b$ is congruent to 0, 1 or $2\pmod{3}$
respectively and apply Lemma 5.1 with $i=2$.

When $c$ is odd, we start with ${\bm{g}_{4}}$, ${\bm{g}_{5}}$ or
${\bm{g}_{6}}$. If $c\equiv 1\pmod{6}$, then start by taking ${\bm{g}_{4}}$,
${\bm{g}_{5}}$ or ${\bm{g}_{6}}$ according to whether $b$ is congruent to 1, 2
or $0\pmod{3}$ respectively. If $c\equiv 3\pmod{6}$, then start by taking
${\bm{g}_{4}}$, ${\bm{g}_{5}}$ or ${\bm{g}_{6}}$ according to whether $b$ is
congruent to 2, 0 or $1\pmod{3}$ respectively and apply Lemma 5.1 with $i=1$.
If $c\equiv 5\pmod{6}$, then start by taking ${\bm{g}_{4}}$, ${\bm{g}_{5}}$ or
${\bm{g}_{6}}$ according to whether $b$ is congruent to 0, 1 or $2\pmod{3}$
respectively and apply Lemma 5.1 with $i=2$.

In each case we obtain the required realization of $L^{\prime}$. Next, apply
Lemma 5.1 $(c-c^{\prime})/6$ times with $x=i=3$ to obtain a
$\\{1,3\\}$-growable realization of
$\\{1^{a^{\prime}},3^{b^{\prime}+(c-c^{\prime})/2},6^{c}\\}$. Finally,
complete to the required realization using $a-a^{\prime}$ applications of
Theorem 2.3 with $x=1$ and $\frac{b-b^{\prime}}{3}-\frac{c-c^{\prime}}{6}$
applications with $x=3$.

When $c$ is even, the method requires up to six 3’s in the ${\bm{g}_{i}}$, up
to seven 3’s to adjust the congruency class of the number of 6’s, and then
$c/2$ 3’s to obtain the correct number of 6’s. Hence it always works for
$b\geq 6+7+c/2=13+c/2$. When $c$ is odd, the method requires up to eleven 3’s
in the ${\bm{g}_{i}}$, up to seven 3’s to adjust the congruency class of the
number of 6’s, and then up to $(c-1)/2$ 3’s to obtain the correct number of
6’s. Hence it always works for $b\geq 11+7+(c-1)/2=18+(c-1)/2$. ∎

######  Example 5.3.

Let $L=\\{1^{3},3^{18},6^{10}\\}$. Since $b\equiv 0\pmod{3}$ and $c\equiv
4\pmod{6}$, we start applying Lemma 5.1 with $i=2$ to ${\bm{g}_{1}}$. In this
way we obtain the realization

$[15,14,1,\textrm{7},\textrm{4},10,13,0,\textrm{6},\textrm{3},9,12,11,8,5,2]$

of the multiset $\\{1^{2},3^{9},6^{4}\\}$. Now we apply Lemma 5.1 once with
$i=x=3$ to this new multiset and we get a realization of
$\\{1^{2},3^{12},6^{10}\\}$:

$[24,23,1,7,4,10,\textrm{16},\textrm{13},19,22,0,6,3,9,\textrm{15},\textrm{12},18,21,20,17,14,11,\textrm{5},\textrm{8},2].$

We now apply Theorem 2.3 twice with $x=3$ to get a realization of
$\\{1^{2},3^{18},6^{10}\\}$ and then once with $x=1$ to get a realization of
$L$:

$[31,30,1,4,7,13,10,16,22,19,25,28,29,0,3,6,12,$

$9,15,21,18,24,27,26,23,20,17,11,14,8,5,2].$

To use the method of proof of Lemma 5.2 for $x>3$ we require
$\\{1,x\\}$-growable realizations for $\\{1^{a},x^{b}\\}$ for $a$ as small as
possible and for a $b$ in each congruence class modulo $x$. Lemmas 5.4, 5.6
and 5.8 provide these. Each of the constructions has at least one subsequence
consisting of multiple instances of pairs $[t,t+x]$, triples $[t,t+x,t+2x]$ or
their reverses; we indicate these pairs and triples with underbraces to help
illuminate the overall structure.

######  Lemma 5.4.

Let $x\geq 4$. The multisets $\\{1^{x-1},x^{x+1}\\}$, $\\{1^{x-2},x^{x+2}\\}$
and $\\{1^{x-2},x^{2x}\\}$ have $\\{1,x\\}$-growable realizations.

###### Proof.

First, we cover $\\{1^{x-1},x^{x+1}\\}$, in which case $v=2x+1$. When $x$ is
even, the sequence

$[1,x+1,0,2x,x,\underbrace{x-1,2x-1},\underbrace{2x-2,x-2},\underbrace{x-3,2x-3},\ldots,\underbrace{x+2,2}]$

has edge-lengths $[x,x,1,x,1,x,\ldots,1,x]$ and so realizes
$\\{1^{x-1},x^{x+1}\\}$. It is 1-growable at 1 and $x$-growable at $x$. When
$x$ is odd, the sequence

$[x,x+1,1,0,2x,x-1,2x-1,\underbrace{x-2,2x-2},\underbrace{2x-3,x-3},\underbrace{x-4,2x-4},\ldots,\underbrace{x+2,2}]$

has edge-lengths $[1,x,1,1,x,x,x,x,1,x,\ldots,1,x]$ and so realizes
$\\{1^{x-1},x^{x+1}\\}$. It is 1-growable at $2x-1$ and $x$-growable at $x-1$.

Next, consider $\\{1^{x-2},x^{x+2}\\}$ and so $v=2x+1$. When $x$ is even, the
sequence

$[x,2x,0,x+1,1,x+2,2,\underbrace{3,x+3},\underbrace{x+4,4},\underbrace{5,x+5},\ldots,\underbrace{x-1,2x-1}]$

has edge-lengths $[x,1,x,x,x,x,1,x,1,x,\ldots,1,x]$ and so realizes
$\\{1^{x-2},x^{x+2}\\}$. It is 1-growable at 1 and $x$-growable at $x$. When
$x$ is odd, the sequence

$[0,x,x-1,2x,2x-1,x-2,2x-2,\underbrace{x-3,2x-3},\underbrace{2x-4,x-4},\underbrace{x-5,2x-5},\ldots,\underbrace{x+1,1}]$

has edge-lengths $[x,1,x,1,x,x,x,x,1,x,1,x,\ldots,1,x]$ so this realizes
$\\{1^{x-2},x^{x+2}\\}$. It is 1-growable at $2x-2$ and $x$-growable at $x-1$.

Finally, consider $\\{1^{x-2},x^{2x}\\}$ and so $v=3x-1$. When $x$ is even,
the sequence

$[\underbrace{0,x,2x},\underbrace{2x+1,x+1,1},\underbrace{2,x+2,2x+2},\ldots,\underbrace{x-4,2x-4,3x-4},$

$x-3,2x-3,2x-2,x-2,3x-3,3x-2,x-1,2x-1]$

has edge-lengths $[x,x,1,x,x,1,\ldots,1,x,x,x,x,1,x,x,1,x,x]$ and so realizes
$\\{1^{x-2},x^{2x}\\}$. It is 1-growable at $3x-3$ and $x$-growable at $x-1$.
When $x$ is odd the sequence

$[3x-2,x-1,2x-1,\underbrace{2x,x,0},\underbrace{1,x+1,2x+1},\underbrace{2x+2,x+2,2},\ldots,$

$\underbrace{x-4,2x-4,3x-4},x-3,2x-3,2x-2,x-2,3x-3]$

has edge-lengths $[x,x,1,x,x,1,x,x,\ldots,1,x,x,x,x,1,x,x]$ and so realizes
$\\{1^{x-2},x^{2x}\\}$. It is 1-growable at $3x-4$ and $x$-growable at $x$. ∎

######  Example 5.5.

Let $x=8$. Lemma 5.4 gives the $\\{1,8\\}$-growable realizations

$[1,9,0,16,8,7,15,14,6,5,13,12,4,3,11,10,2],$
$[8,16,0,9,1,10,2,3,11,12,4,5,13,14,6,7,15],$
$[0,8,16,17,9,1,2,10,18,19,11,3,4,12,20,5,13,14,6,21,22,7,15]$

of $\\{1^{7},8^{9}\\}$, $\\{1^{6},8^{10}\\}$ and $\\{1^{6},8^{16}\\}$
respectively.

Let $x=9$. Lemma 5.4 gives the $\\{1,9\\}$-growable realizations

$[9,10,1,0,18,8,17,7,16,15,6,5,14,13,4,3,12,11,2],$
$[0,9,8,18,17,7,16,6,15,14,5,4,13,12,3,2,11,10,1],$
$[25,8,17,18,9,0,1,10,19,20,11,2,3,12,21,22,13,4,5,14,23,6,15,16,7,24]$

of $\\{1^{8},9^{10}\\}$, $\\{1^{7},9^{11}\\}$ and $\\{1^{7},9^{18}\\}$
respectively.

######  Lemma 5.6.

Let $x\geq 4$ be even. There is a $\\{1,x\\}$-growable realization for
$\\{1^{x-2},x^{b}\\}$ for $b$ in range $x+3\leq b\leq 2x-1$.

###### Proof.

We consider odd $b$ and even $b$ separately, starting with odd $b$.

Take $r$ in the range $0\leq r\leq(x-4)/2$. Write $x=2r+2s+4$ for some $s\geq
0$. We construct a realization for

$L=\\{1^{2r+2s+2},x^{4r+2s+7}\\}=\\{1^{x-2},x^{x+2r+3}\\}.$

We have $v=(2r+2s+2)+(4r+2s+7)+1=6r+4s+10$.

We build the required realization by concatenating three sequences. First:

$[\underbrace{2r+1,4r+2s+5},\underbrace{4r+2s+6,2r+2},\underbrace{2r+3,4r+2s+7},\ldots,\underbrace{4r+4s+6,2r+2s+2}],$

which has $2s+2$ pairs and produces edge-lengths $\\{1^{2s+1},x^{2s+2}\\}$.
Second:

$[\underbrace{6r+4s+8,4r+2s+4,2r},\underbrace{2r-1,4r+2s+3,6r+4s+7},$

$\underbrace{6r+4s+6,4r+2s+2,2r-2},\ldots,\underbrace{4r+4s+8,2r+2s+4,0}],$

which has $2r+1$ triples and produces $\\{1^{2r},x^{4r+2}\\}$. Third:

$[6r+4s+9,2r+2s+3,4r+4s+7]$

which produces $\\{x^{2}\\}$.

Upon concatenation we have a difference of $x$ where the first and second
sequences join and a difference of 1 where the second and third join. Hence we
have a realization of

$L=\\{1^{2s+1},x^{2s+2}\\}\cup\\{1^{2r},x^{4r+2}\\}\cup\\{x^{2}\\}\cup\\{1,x\\}=\\{1^{x-2},x^{x+2r+3}\\}.$

It is 1-growable at $v-2=6r+4s+8$: when embedding with $m=6r+4s+8$, the only
lengthened edge is $(2r+2s+2,6r+4s+8)$. It is $x$-growable at $x-1=2r+2s+3$:
when embedding with $m=2r+2s+3$ the lengthened edges are $(i,i+x)$ for $0\leq
i\leq x-1$.

For the case with $b$ even, first note that when $x=4$ there are no values of
$b$ to be considered. Let $x\geq 6$ be even and take $r$ in the range $0\leq
r\leq(x-6)/2$. Write $x=2r+2s+6$ for some $s\geq 0$. We construct a
realization for

$L=\\{1^{2r+2s+4},x^{4r+2s+10}\\}=\\{1^{x-2},x^{x+2r+4}\\}.$

We have $v=(2r+2s+4)+(4r+2s+10)+1=6r+4s+15$.

We build the required realization by concatenating three sequences. First:

$[\underbrace{4r+2s+11,2r+5},\underbrace{2r+6,4r+2s+12},$

$\underbrace{4r+2s+13,2r+7},\ldots,\underbrace{4r+4s+11,2r+2s+5}]$,

which has $2s+1$ pairs and produces the edge-lengths $\\{1^{2s},x^{2s+1}\\}$.
Second:

$[2r+2s+6,4r+4s+12,4r+4s+13,2r+2s+7,1,4r+2s+10,2r+4,2r+3,4r+2s+9,0]$

which produces $\\{1^{2},x^{7}\\}$. Third:

$[\underbrace{6r+4s+14,4r+2s+8,2r+2},\underbrace{2r+1,4r+2s+7,6r+4s+13},$

$\underbrace{6r+4s+12,4r+2s+6,2r},\ldots,\underbrace{4r+4s+14,2r+2s+8,2}],$

which has $2r+1$ triples and produces $\\{1^{2r},x^{4r+2}\\}$.

Upon concatenation we have a difference of $1$ at each of the joins. Hence we
have a realization of

$L=\\{1^{2s},x^{2s+1}\\}\cup\\{1^{2},x^{7}\\}\cup\\{1^{2r},x^{4r+2}\\}\cup\\{1^{2}\\}=\\{1^{x-2},x^{x+2r+4}\\}.$

It is 1-growable at $1$: when embedding with $m=1$, the only lengthened edge
is $(1,2r+2s+7)$. It is $x$-growable at $x=2r+2s+6$: when embedding with
$m=2r+2s+6$ the lengthened edges are $(i,i+x)$ for $1\leq i\leq x$. ∎

######  Example 5.7.

To construct a $\\{1,8\\}$-growable realization of $\\{1^{6},8^{13}\\}$ using
the proof of Lemma 5.6 we take $r=s=1$ to obtain

$[3,11,12,4,5,13,14,6,18,10,2,1,9,17,16,8,0,19,7,15],$

which is $1$-growable at $18$ and $8$-growable at $7$.

To construct a $\\{1,10\\}$-growable realization of $\\{1^{8},10^{16}\\}$ we
take $r=s=1$ to obtain

$[17,7,8,18,19,9,10,20,21,11,1,16,6,5,15,0,24,14,4,3,13,23,22,12,2]$

which is $1$-growable at $1$ and $10$-growable at $10$.

######  Lemma 5.8.

Let $x\geq 5$ be odd. There is a $\\{1,x\\}$-growable realization for
$\\{1^{x-2},x^{b}\\}$ for $b$ in range $x+3\leq b\leq 2x-1$.

###### Proof.

The constructions are similar to those of Lemma 5.6 in that they each are
built from the concatenation of three sequences and we need to consider odd
and even $b$ separately. We start with odd $b$.

Take $r$ in the range $0\leq r\leq(x-5)/2$. Write $x=2r+2s+5$ for some $s\geq
0$. We construct a realization for

$L=\\{1^{2r+2s+3},(2r+2s+5)^{4r+2s+9}\\}=\\{1^{x-2},x^{x+2r+4}\\}.$

We have $v=(2r+2s+3)+(4r+2s+9)+1=6r+4s+13$.

The first sequence is

$[\underbrace{6r+4s+10,4r+2s+5,2r},\underbrace{2r-1,4r+2s+4,6r+4s+9},$

$\underbrace{6r+4s+8,4r+2s+3,2r-2},\ldots,\underbrace{4r+4s+10,2r+2r+5,0}]$.

There are $2r+1$ triples, so this sequence produces edge-lengths
$\\{1^{2r},x^{4r+2}\\}$. The second sequence is

$[6r+4s+12,2r+2s+4,4r+4s+9,4r+4s+8,2r+2s+3,6r+4s+11].$

This has internal differences $[2r+2s+5,2r+2s+5,1,2r+2s+5,2r+2s+5]$ and so
produces $\\{1,x^{4}\\}$. The third sequence is

$[\underbrace{4r+2s+6,2r+1},\underbrace{2r+2,4r+2s+7},\underbrace{4r+2s+8,2r+3},\ldots,\underbrace{2r+2s+2,4r+4s+7}].$

There are $2s+2$ pairs, so this sequence produces $\\{1^{2s+1},x^{2s+2}\\}$.

Upon concatenation, we have a difference of 1 generated where the first and
second sequences join and a difference of $2r+2s+5=x$ where the second and
third join. Hence we have a realization of

$L=\\{1^{2r},x^{4r+2}\\}\cup\\{1,x^{4}\\}\cup\\{1^{2s+1},x^{2s+2}\\}\cup\\{1,x\\}=\\{1^{x-2},x^{x+2r+4}\\}.$

The realization is 1-growable at $v-2=6r+4s+11$: when embedding with
$m=6r+4s+11$, the only lengthened edge is $(2r+2s+3,6r+4s+11)$. It is
$x$-growable at $x-1=2r+2s+4$: when embedding with $m=2r+2s+4$ the lengthened
edges are $(i,i+x)$ for $0\leq i\leq x-1$.

Moving to even $b$, take $r$ in the range $0\leq r\leq(x-5)/2$ and write
$x=2r+2s+5$ for some $s\geq 0$. We construct a realization for

$L=\\{1^{2r+2s+3},(2r+2s+5)^{4r+2s+8}\\}=\\{1^{x-2},x^{x+2r+3}\\}.$

We have $v=(2r+2s+3)+(4r+2s+8)+1=6r+4s+12$.

The first sequence is

$[\underbrace{4r+2s+6,2r+1},\underbrace{2r+2,4r+2s+7},\underbrace{4r+2s+8,2r+3},\ldots,\underbrace{4r+4s+8,2r+2s+3}].$

There are $2s+3$ pairs, so this sequence produces edge-lengths
$\\{1^{2s+2},x^{2s+3}\\}$. The second sequence is the same as the first
sequence of the previous construction:

$[\underbrace{6r+4s+10,4r+2s+5,2r},\underbrace{2r-1,4r+2s+4,6r+4s+9},$

$\underbrace{6r+4s+8,4r+2s+3,2r-2},\ldots,\underbrace{4r+4s+10,2r+2r+5,0}]$.

As before, there are $2r+1$ triples, so this sequence produces
$\\{1^{2r},x^{4r+2}\\}$. The third sequence is

$[6r+4s+11,2r+2s+4,4r+4s+9]$

which has internal differences $[2r+2s+5,2r+2s+5]$ and so produces
$\\{x^{2}\\}$.

Upon concatenation, we have a difference of $2r+2s+5=x$ generated where the
first and second sequences join and a difference of 1 where the second and
third join. Hence we have a realization of

$L=\\{1^{2s+2},x^{2s+3}\\}\cup\\{1^{2r},x^{4r+2}\\}\cup\\{x^{2}\\}\cup\\{1,x\\}=\\{1^{x-2},x^{x+2r+3}\\}.$

The realization is 1-growable at $v-2=6r+4s+10$: when embedding with
$m=6r+4s+10$, the only lengthened edge is $(2r+2s+3,6r+4s+10)$. It is
$x$-growable at $x-1=2r+2s+4$: when embedding with $m=2r+2s+4$ the lengthened
edges are $(i,i+x)$ for $0\leq i\leq x-1$. ∎

######  Example 5.9.

To construct a $\\{1,13\\}$-growable realization of $\\{1^{11},13^{21}\\}$
using the proof of Lemma 5.8 we take $r=s=2$ to obtain

$[30,17,4,3,16,29,28,15,2,1,14,27,26,13,0,$

$32,12,25,24,11,31,18,5,6,19,20,7,8,21,22,9,10,23]$,

which is $1$-growable at $31$ and $13$-growable at $12$.

To construct a $\\{1,13\\}$-growable realization of $\\{1^{7},9^{14}\\}$ we
take $r=s=1$ to obtain

$[12,3,4,13,14,5,6,15,16,7,20,11,2,1,10,19,18,9,0,21,8,17]$

which is $1$-growable at $20$ and $9$-growable at $8$.

We can now prove the main result of the section.

######  Theorem 5.10.

Let $L=\\{1^{a},x^{b},(2x)^{c}\\}$. If $a\geq x-2$, $c$ is even and $b\geq
5x-2+c/2$, then $\mathop{\rm BHR}(L)$ holds.

###### Proof.

If $x\leq 2$, then $\mathop{\rm BHR}(L)$ holds without restriction and the
case $x=3$ is covered in Lemma 5.2, so assume $x\geq 4$. We follow the method
of proof of Lemma 5.2, with Lemmas 5.4, 5.6 and 5.8 providing the realizations
to get started.

Take $i$ in the range $0\leq i<c/2$ such that $2i\equiv c\pmod{2x}$.

To construct the required realization for $L$, start with the realization of
$\\{1^{a^{\prime}},x^{b^{\prime}}\\}$ that has $b^{\prime}\equiv b+2i\pmod{x}$
given by Lemma 5.4, 5.6 or 5.8. So $a^{\prime}=x-2$, except when $b+2i\equiv
1\pmod{x}$ and admissibility forces us to use $a^{\prime}=x-1$.

If $c\not\equiv 0\pmod{2x}$, then apply Lemma 5.1 using $i$ to give a
realization whose number of occurrences $c^{\prime}$ of $2x$ differs from $c$
by a multiple of $2x$ and whose number of occurrences of $x$ differs from $b$
by a multiple of $x$. (If $c\equiv 0\pmod{2x}$, then this is already the
case.)

Apply Lemma 5.1 a further $(c-c^{\prime})/2x$ times with $i=x$ to obtain a
$\\{1,x\\}$-growable realization of
$\\{1^{a^{\prime}},x^{b^{\prime\prime}},(2x)^{c}\\}$ where
$b^{\prime\prime}\equiv b\pmod{x}$. Complete to the required realization using
the appropriate number of applications of Theorem 2.3 with $1$ and $x$.

The method requires up to $2x$ occurrences of $x$ in the initial realization,
up to $3x-2$ occurrences of $x$ to adjust the congruency class of the number
of occurrences of $2x$, and $c/2$ occurrences of $x$ to obtain the correct
number of occurrences of $2x$. Hence it always works for $b\geq
2x+3x-2+c/2=5x-2+c/2$. ∎

When $c$ is odd, we are not aware of any reason why the same approach will not
work. However, without new ideas, it will take more work to get weaker results
than in the even case. This is because the starter realizations now need to be
for $\\{1^{x-2},x^{b},2x\\}$, which means that we must have $v\geq 4x$,
compared to the constructions here which all have $v<3x$. As well as being
larger, using the same approach as Lemmas 5.6 and 5.8 would probably take more
cases to cover all required values of $b$. Some of these issues are already
apparent in Lemma 5.2.

Lemma 5.1 can be thought of as combining the notion of growability with that
of a particular perfect realization. This can be generalized to other perfect
realizations, which we now do.

For a multiset $L$, define $sL=\\{sy:y\in L\\}$. When we apply Theorem 2.3 $k$
times to an $x$-growable realization we produce a realization with the $x$
subsequences

$[m+1-x,m+1,m+1+x,\ldots,m+1+(k-1)x]+t$

for $0\leq t\leq x-1$. If we have a perfect linear realization of length $k$
of a multiset $L$, then we can multiply each element by $x$ to get a sequence
that realizes $xL$ and then take a translate of it to replace a subsequence of
the above form.

Lemma 5.1 uses this process with the perfect linear realization $[0,2,1,3]$ of
$\\{1,2^{2}\\}$. In general the approach gives the following lemma.

######  Lemma 5.11.

Let $L$ have an $X$-growable realization with $x\in X$. Let
$L_{1},\ldots,L_{x}$ be multisets of size $k-1$ that have perfect linear
realizations. Then

$L\cup xL_{1}\cup\cdots\cup xL_{x}$

has an $X$-growable realization.

If we use the perfect linear realization $[0,1]$ of $\\{1\\}$ in Lemma 5.11,
then we end up back at Theorem 2.3.

######  Example 5.12.

Let $x\geq 3$. In this section we have constructed $\\{1,x\\}$-growable
realizations of the multisets $\\{1^{x-1},x^{x+1}\\}$ and
$\\{1^{x-2},x^{b}\\}$ for $x+2\leq b\leq 2x$. Let $c,d,e,f,g\geq 0$ with
$c+d+e+f+g\equiv 0\pmod{x}$. Take $c$ copies of the perfect linear realization
$[0,1,2,3,4,5]$ of $\\{1^{5}\\}$, $d$ copies of the perfect realization
$[0,2,1,3,4,5]$ of $\\{1^{3},2^{2}\\}$, $e$ copies of the perfect linear
realization $[0,3,1,2,4,5]$ of $\\{1^{2},2^{2},3\\}$, $f$ copies of the
perfect linear realization $[0,3,1,4,2,5]$ of $\\{2^{2},3^{3}\\}$, and $g$
copies of the perfect linear realization $[0,2,4,1,3,5]$ of $\\{2^{4},3\\}$.
Lemma 5.11 proves $\mathop{\rm BHR}(L)$ for

$L=\\{1^{a},x^{b+5c+3d+2e},(2x)^{2d+2e+2f+4g},(3x)^{e+3f+g}\\}$

for $a\geq x-2$ and $b\geq x+1$.

## Acknowledgements

The second and the third author were partially supported by INdAM-GNSAGA.

## References

  * [1] M. Buratti and F. Merola, Dihedral Hamiltonian cycle systems of the cocktail party graph. J. Combin. Des., 21 (2013) 1–23.
  * [2] S. Capparelli and A. Del Fra, Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3, Electron. J. Combin. 17 (2010) R44, 13pp.
  * [3] J. H. Dinitz and S. R. Janiszewski, On Hamiltonian paths with prescribed edge lengths in the complete graph, Bull. Inst. Combin. Appl. 57 (2009) 42–52.
  * [4] S. C. Gutekunst and D. P. Williamson, The circlet inequalities: a new, circulant-based facet-defining inequality for the TSP, arXiv:2012.12363.
  * [5] P. Horak and A. Rosa, On a problem of Marco Buratti, Electron. J. Combin. 16 (2009) R20, 15pp.
  * [6] M. Meszka, Private communication, reported in [5].
  * [7] F. Monopoli, Absolute differences along Hamiltonian paths, Electron. J. Combin. 22 (2015) P3.20, 20pp.
  * [8] M. A. Ollis, A. Pasotti, M. A. Pellegrini and J. R. Schmitt, New methods to attack the Buratti-Horak-Rosa Conjecture, submitted, arXiv:1912.07377.
  * [9] A. Pasotti and M. A. Pellegrini, On the Buratti-Horak-Rosa Conjecture about Hamiltonian paths in complete graphs, Electron. J. Combin. 21 (2014) P2.30.
  * [10] A. Pasotti and M. A. Pellegrini, A new result on the problem of Buratti, Horak and Rosa, Discrete Math. 319 (2014) 1–14.
  * [11] D. B. West, Buratti’s Conjecture (2007),
https://faculty.math.illinois.edu/$\sim$west/regs/buratti.html, accessed
January 22, 2021.