casectr [1]casectrblue#1black

reductctr

# The Automorphism Conjecture for Ordered Sets of Width $\leq 11$

Bernd S. W. Schröder
School of Mathematics and Natural Sciences
The University of Southern Mississippi
118 College Avenue, #5043
Hattiesburg, MS 39406

###### Abstract

We prove the automorphism conjecture for ordered sets of width less than or
equal to $11$. The proof supports the meta conjecture that a large number of
automorphisms is achievable only as some type of product of independent
automorphisms on highly symmetric subsets.

AMS subject classification (2010): 06A07, 06A06
Key words: Ordered set; automorphism; endomorphism; width

##  1 Introduction

An ordered set consists of an underlying set $P$ equipped with a reflexive,
antisymmetric and transitive relation $\leq$, the order relation. An order-
preserving self-map, or, an endomorphism, of an ordered set $P$ is a self map
$f:P\to P$ such that $p\leq q$ implies $f(p)\leq f(q)$. Consistent with
standard terminology, endomorphisms with an inverse that is an endomorphism,
too, are called automorphisms. The set of endomorphisms is denoted ${\rm
End}(P)$ and the set of automorphisms is denoted ${\rm Aut}(P)$. Rival and
Rutkowski’s automorphism problem (see [13], Problem 3) asks the following.

###### Open Question 1.1

(Automorphism Problem.) Is it true that

$\lim_{n\to\infty}\max_{|P|=n}{|{\rm Aut}(P)|\over|{\rm End}(P)|}=0?$

The Automorphism Conjecture states that the Automorphism Problem has an
affirmative answer. In light of the facts that, for almost every ordered set,
the identity is the only automorphism (see [12], Corollary 2.3a), and that
every ordered set has at least $2^{{2\over 3}n}$ endomorphisms (see [6],
Theorem 1), this conjecture is quite natural. Indeed, if, for ordered sets
with “many” automorphisms, we could show that there are “enough” endomorphisms
to guarantee the ratio’s convergence to zero (for examples of this technique,
see [8, 9], or Proposition 8.6 here), the conjecture would be confirmed.
However, the Automorphism Conjecture has been remarkably resilient against
attempts to prove it in general.

Recall that an antichain is an ordered set in which no two elements are
comparable and that the width $w(P)$ of an ordered set $P$ is the size of the
largest antichain contained in $P$. The Automorphism Conjecture for ordered
sets of small width has recently gathered attention in [3]. It is easy to
slightly improve Theorem 1 in [6] for ordered sets of bounded width, see Lemma
8.1. With such lower bounds available, it is natural to also consider upper
bounds on the number of automorphisms. We will see here that the search for
upper bounds on the number of automorphisms is linked with numerous insights
on the connection between the combinatorial structure of an ordered set and
the structure of its automorphism group.

We start our investigation with ordered sets that have a lot of local symmetry
in Section 2. Lemma 2.11 essentially shows that, if too much local symmetry is
allowed, then, for any automorphism, the remainder of the ordered set is
locked into following the automorphism’s action on a small subset. Section 3
provides an overall framework in which this “transmission of local actions of
automorphisms” can be investigated. Proposition 3.10 shows that the actions of
automorphisms within different parts of such a framework, called
interdependent orbit unions, are independent of each other. Section 4 then
provides the framework for the investigation of “transmission of local actions
of automorphisms” within such interdependent orbit unions. Theorem 4.12 is the
key to splitting the automorphism group into two parts, which can then be
analyzed separately. Bounding the number of automorphisms for the purpose of
tackling ordered sets of small width then proceeds inductively, using
estimates provided in Section 5. The base step in Section 6 reveals a number
of forbidden configurations, which however, can eventually be defused with
Proposition 8.6. The induction step in Section 7 must consider these and other
inconvenient configurations, but it ultimately succeeds in Theorem 7.4,
bounding the number of automorphisms with a product of factorials of numbers
that are at most one less than the width and whose sum is at most half of the
number of elements minus the height. (Definition 3.16 has the requisite
details.) Section 8 combines all results so far to prove the Automorphism
Conjecture for all ordered sets of width less than or equal to 11 in Theorem
8.10. Refinements and some further uses of the frameworks developed here are
discussed in Section 9.

##  2 Max-locked Ordered Sets

An ordered set with “many” automorphisms must have a high degree of symmetry.
In terms of counting techniques, this means that, even when the values of an
automorphism are known for a “large” number of points, the automorphism would
still not be uniquely determined by these values. It is thus natural to try to
identify smaller subsets $S\subset P$ such that every automorphism of the
ordered set $P$ is uniquely determined by its values on $S$.

For sets $B,T\subseteq P$, we will write $B<T$ iff every $b\in B$ is strictly
below every $t\in T$. For singleton sets, we will omit the set braces. Recall
that a nonempty subset $A\subseteq P$ is called order-autonomous iff, for all
$z\in P\setminus A$, we have that existence of an $a\in A$ with $z<a$ implies
$z<A$, and, existence of an $a\in A$ with $z>a$ implies $z>A$. An order-
autonomous subset $A\subseteq$ will be called nontrivial iff
$|A|\not\in\\{1,|P|\\}$.

Lemma 2.1 below shows the simple idea that we will iterate throughout this
paper: When there are no nontrivial order-autonomous antichains, then an
automorphism’s values on an antichain are determined by the automorphism’s
values away from the antichain. Lemma 2.1 will be generalized in parts 1 and 2
of Lemma 5.1. Recall that $\uparrow x=\\{p\in P:p\geq x\\}$ and $\downarrow
x=\\{p\in P:p\leq x\\}$.

###### Lemma 2.1

Let $P$ be an ordered set, let $A\subseteq P$ be an antichain that does not
contain any nontrivial order-autonomous antichains, and let $\Phi,\Psi\in{\rm
Aut}(P)$ be so that both $\Phi$ and $\Psi$ map $A$ to itself and
$\Phi|_{P\setminus A}=\Psi|_{P\setminus A}$. Then $\Phi=\Psi$.

Proof. Let $\Phi,\Psi\in{\rm Aut}(P)$ be so that both $\Phi$ and $\Psi$ map
$A$ to itself and $\Phi|_{P\setminus A}=\Psi|_{P\setminus A}$, and let $x\in
A$. Then $\uparrow\Phi(x)\setminus\\{\Phi(x)\\}=\Phi[\uparrow
x\setminus\\{x\\}]=\Phi|_{P\setminus A}[\uparrow
x\setminus\\{x\\}]=\Psi|_{P\setminus A}[\uparrow
x\setminus\\{x\\}]=\uparrow\Psi(x)\setminus\\{\Psi(x)\\}$, and similarly,
$\downarrow\Phi(x)\setminus\\{\Phi(x)\\}=\downarrow\Psi(x)\setminus\\{\Psi(x)\\}$.
Hence $\\{\Phi(x),\Psi(x)\\}\subseteq A$ is an order-autonomous antichain,
which, by hypothesis, implies $\Phi(x)=\Psi(x)$.

Recall that an element $x$ of a finite ordered set $P$ is said to be minimal
or of rank 0, and we set ${\rm rank}(x):=0$, iff there is no $z\in P$ such
that $z<x$. Recursively, the element $x$ is said to be of rank $k$, and we set
${\rm rank}(x):=k$, iff $x$ is minimal in $P\setminus\\{z\in P:{\rm
rank}(z)\leq k-1\\}$. It is easy to see that the rank of a point is preserved
by automorphisms.

###### Definition 2.2

Let $P$ be an ordered set. For every nonnegative integer $j$, we define
$R_{j}$ to be the set of elements of rank $j$, and we define
$\alpha(R_{k}):=|\\{\Phi|_{R_{k}}:\Phi\in{\rm Aut}(P)\\}|$ to be the number of
pairwise distinct restrictions of automorphisms to $R_{k}$. Finally, the
largest number $h$ such that $R_{h}\not=\emptyset$ is called the height of
$P$.

The largest possible value for $\alpha(R_{k})$ in an ordered set of width $w$
is $w!$. Because we are interested in bounds for the number of automorphisms,
it is natural to consider ordered sets for which $\alpha(R_{k})$ is close to
$w!$, where “close” will turn out to mean $\geq(w-1)!$, except in the case of
width $w=4$, in which it will mean $>8$. Lemma 2.11 will show that, for
ordered sets with large values $\alpha(R_{k})$, every automorphism is
determined by its values on $R_{k}$. Note that, for consideration of upper
bounds, it is also natural to exclude points that are common fixed points for
all automorphisms.

###### Definition 2.3

(See Figure 1.) For $k\geq 3$, we define $S_{k}$ to be the standard example of
a $k$-dimensional ordered set, that is, $S_{k}$ has $k$ minimal elements
$\ell_{1},,\ldots,\ell_{k}$, $k$ maximal elements $u_{1},\ldots,u_{k}$ and
$\ell_{i}<u_{j}$ unless $i=j$. For $k\geq 1$, we define $kC_{2}$ to be the
disjoint union of $k$ chains with $2$ elements each.

Figure 1: The standard example $S_{5}$ and the disjoint union $5C_{2}$ of five
$2$-chains.

###### Lemma 2.4

Let $P$ be an ordered set of width $w\geq 3$ such that no $p\in P$ is a common
fixed point for all automorphisms of $P$, such that there is a $j$ such that
$|R_{j}|=w-1$ and $\alpha(R_{j})=(w-1)!$, and such that $\\{x\in P:{\rm
rank}(x)\geq j+1\\}\not=\emptyset$ is not order-autonomous. Then $R_{j}\cup
R_{j+1}$ is isomorphic to a set $S_{w-1}$ or $(w-1)C_{2}$, and consequently
$\alpha(R_{j+1})=(w-1)!$.

Proof. First suppose, for a contradiction, that there is an $x\in P\setminus
R_{j}$ that is not comparable to any element of $R_{j}$. Then, because the
width of $P$ is $w$, we have that $x$ is the unique element in $R_{{\rm
rank}(x)}$ that is not comparable to any element of $R_{j}$. Let $\Phi$ be any
automorphism of $P$. Because automorphisms preserve the rank, we have
$\Phi[R_{j}]=R_{j}$. Now $\Phi(x)$ must be the unique element in $R_{{\rm
rank}(x)}$ that is not comparable to any element of $R_{j}=\Phi[R_{j}]$. Hence
$\Phi(x)=x$, a contradiction to there not being any common fixed points for
all automorphisms. Hence every element $x\in P\setminus R_{j}$ is comparable
to at least one element of $R_{j}$.

Suppose, for a contradiction, that $R_{j+1}>R_{j}$. Let $p\in P$ be an element
of rank less than $j$ and let $z\in\\{x\in P:{\rm rank}(x)\geq j+1\\}$. By the
above, there is a $y\in R_{j}$ such that $p<y\in R_{j}<R_{j+1}$. Moreover,
$z$, being of rank at least $j+1$, is greater than or equal to some element of
$R_{j+1}$. Hence $p<z$. However, this means that $\\{x\in P:{\rm rank}(x)\geq
j+1\\}\not=\emptyset$ is order-autonomous, a contradiction. Therefore, there
is an $x\in R_{j+1}$ such that $|\downarrow x\cap
R_{j}|\in\\{1,\ldots,w-2\\}$.

Let $x\in R_{j+1}$ be so that $\ell:=|\downarrow x\cap
R_{j}|\in\\{1,\ldots,w-2\\}$. Let $S$ be any $\ell$-element subset of $R_{j}$.
Because $|R_{j}|=w-1$ and $\alpha(R_{j})=(w-1)!$, there is a $\Phi\in{\rm
Aut}(P)$ such that $\Phi[\downarrow x\cap R_{j}]=S$. Hence, there is a
$q_{S}:=\Phi(x)\in R_{j+1}$ with $\downarrow q_{S}\cap R_{j}=S$. Because there
are $\pmatrix{w-1\cr\ell\cr}$ $\ell$-element subsets of $R_{j}$ and
$\alpha(R_{j})=(w-1)!$, there are $\pmatrix{w-1\cr\ell\cr}$ pairwise distinct
elements $q_{S}\in R_{j+1}$. Because, for $\ell\not\in\\{1,w-2\\}$, we have
$\pmatrix{w-1\cr\ell\cr}>w$, we infer that $\ell\in\\{1,w-2\\}$. Without loss
of generality, we can assume that $\ell=1$.

Let $R_{j}=\\{p_{1},\ldots,p_{w-1}\\}$. The set $R_{j+1}$ contains $w-1$
pairwise distinct elements $q_{1},\ldots,q_{w-1}$ such that, for
$i=1,\ldots,w-1$, we have $\downarrow q_{i}\cap R_{j}=\\{p_{i}\\}$. In
particular, the set $\\{p_{1},\ldots,p_{w-1},q_{1},\ldots,q_{w-1}\\}$ is a set
$(w-1)C_{2}$. (Note: $\ell=w-2$ would have produced a set $S_{w-1}$.)

Finally, suppose, for a contradiction, that
$R_{j+1}\not=\\{q_{1},\ldots,q_{w-1}\\}$. Then, because the width of $P$ is
$w$, there is exactly one element $z\in
R_{j+1}\setminus\\{q_{1},\ldots,q_{w-1}\\}$. If $|\downarrow z\cap
R_{j}|\not=1$, then $z$ would be fixed by all automorphisms of $P$, which was
excluded. Hence $|\downarrow z\cap R_{j}|=1$. Without loss of generality, we
can assume $\downarrow z\cap R_{j}=\\{p_{1}\\}$. However, then, because
$\alpha(R_{j})=(w-1)!$, every $p_{i}\in R_{j}$ has at least two upper bounds
in $R_{j+1}$. This is a contradiction, because now every element of $R_{j}$
has at least two upper bounds in $R_{j+1}$ and yet, every element of $R_{j+1}$
has exactly one lower bound in $R_{j}$.

Recall that an ordered set $P$ is called coconnected iff there is no partition
into two nonempty subsets $P=B\cup T$ such that $B<T$. Also recall that a
group $G$ of automorphisms acts transitively on a set $S$ iff for all $x,y\in
S$ there is a $\Phi\in G$ with $\Phi(x)=y$.

###### Lemma 2.5

Let $P$ be a coconnected ordered set of width $w\geq 3$ such that no $p\in P$
is a common fixed point for all automorphisms of $P$, and let $k$ be such that
$\alpha(R_{k})\geq(w-1)!$. Then ${\rm Aut}(P)$ acts transitively on $R_{k}$
and $|R_{k}|=w$.

Proof. First suppose, for a contradiction, that ${\rm Aut}(P)$ does not act
transitively on $R_{k}$. Then there is a set $A\subset R_{k}$ such that, for
all $\Phi\in{\rm Aut}(P)$, we have $\Phi[A]=A$ and $\Phi[R_{k}\setminus
A]=R_{k}\setminus A$. Because no element of $P$ is a common fixed point for
all $\Phi\in{\rm Aut}(P)$, we have that $2\leq|A|\leq w-2$. However, then
$|{\rm Aut}(P)|\leq|A|!(w-|A|)!<(w-1)!$, a contradiction.

Now suppose, for a contradiction, that $|R_{k}|\not=w$. Because
$\alpha(R_{k})\geq(w-1)!$, we infer $|R_{k}|=w-1$ and then
$\alpha(R_{k})=(w-1)!$. The same argument as at the start of the proof of
Lemma 2.4 shows that every $x\in P$ is comparable to an element of $R_{k}$.

Consider the case that $\\{x\in P:{\rm rank}(x)\geq k+1\\}\not=\emptyset$.
Because $P$ is coconnected and every $x\in P$ is comparable to an element of
$R_{k}$, we have that $\\{x\in P:{\rm rank}(x)\geq k+1\\}$ is not order-
autonomous. By Lemma 2.4, we obtain that $\alpha(R_{k+1})=(w-1)!$, and that
$R_{k}\cup R_{k+1}$ is isomorphic to a set $S_{w-1}$ or $(w-1)C_{2}$.

Let $h\in{\mathbb{N}}$ be the height of $P$. By repeating the argument above,
we establish that, for every $j\in\\{k,\ldots,h-1\\}$, the set $R_{j}\cup
R_{j+1}$ is isomorphic to a set $S_{w-1}$ or $(w-1)C_{2}$. Consequently, for
every $j\in\\{k,\ldots,h\\}$, the set $R_{j}$ is also the set of elements
$R_{h-j}^{d}$ of dual rank $h-j$.

By applying the same argument to the dual of $P$, we obtain that, for every
$i\in\\{h-k,\ldots,h-1\\}$, the set $R_{i}^{d}\cup R_{i+1}^{d}$ is isomorphic
to a set $S_{w-1}$ or $(w-1)C_{2}$. Consequently, for every
$i\in\\{h-k,\ldots,h\\}$, the set $R_{i}^{d}$ is the set $R_{h-i}$. Therefore,
for every $j\in\\{0,\ldots,h-1\\}$, the set $R_{j}\cup R_{j+1}$ is isomorphic
to a set $S_{w-1}$ or $(w-1)C_{2}$. This, however, implies that the width of
$P$ is $w-1<w$, a contradiction.

###### Definition 2.6

Let $P$ be a coconnected ordered set of width $w$ such that there is no $p\in
P$ that is fixed by all automorphisms of $P$. $P$ will be called max-locked
iff one of the following hold.

  1. 1.

$w\geq 3$, $w\not=4$ and there is a rank $k$ such that
$\alpha(R_{k})\geq(w-1)!$.

  2. 2.

$w=4$ and there is a rank $k$ such that $\alpha(R_{k})>8$.

Definition 2.6 looks a little strange for the case $w=4$, but an $8$-crown
need not satisfy conclusion 1 of Lemma 2.9 below when it is topped with a
2-antichain such that each element in the antichain is above opposite maximal
elements of the 8-crown. See Definition 6.4 for more on such problematic
configurations. Width $4$ is also the reason why Theorem 7.4 uses
$\max\\{w(U),5\\}$ instead of just $w(U)$.

To prove Lemma 2.9, we need a few results on products of factorials. In this
section, Lemma 2.7 is only used to prove Lemma 2.8, but it will be used more
extensively in Section 4 and beyond, specifically in Lemmas 5.7 and 6.6.

###### Lemma 2.7

Let $(b_{1},\ldots,b_{m})$ be a vector of $m>1$ integers greater than $1$,
sorted in nondecreasing order, that is not equal to any of the vectors $(2,n)$
with $n\geq 2$, $(3,3)$, $(3,4)$, or $(2,2,2)$. Then
$\prod_{j=1}^{m}b_{j}!\leq\left(\sum_{j=1}^{m}b_{j}-m\right)!$ and the
inequality is strict unless $(b_{1},\ldots,b_{m})$ is equal to $(2,2,3)$ or
$(3,5)$.

Proof. We start the proof by considering integers $b_{1},\ldots,b_{m}$ that
are greater than $1$ and which need not be sorted in any order. Note that,
trivially, because all factors are less than or equal to
$\max\\{b_{j}:j=1,\ldots,m\\}$ and because there are $m$ factors equal to $1$
in the product of the factorials, we have
$\prod_{j=1}^{m}b_{j}!=1\cdot\prod_{j=1}^{m}\prod_{k=2}^{b_{j}}k<\left(\sum_{j=1}^{m}b_{j}-(m-1)\right)!$.

Next, we establish a simple claim that will be used repeatedly in the
remainder of the proof.

Claim. Let $k\in\\{2,\ldots,m\\}$ and let $b_{j}^{\prime}$, $j=1,\ldots,k$ be
integers such that
$\prod_{j=1}^{k}b_{j}^{\prime}!\leq\left(\sum_{j=1}^{k}b_{j}^{\prime}-k\right)!$
and such that, for $j=1,\ldots,k$, we have $2\leq b_{j}^{\prime}\leq b_{j}$.
Then $\prod_{j=1}^{m}b_{j}!\leq\left(\sum_{j=1}^{m}b_{j}-m\right)!$. Moreover,
the second inequality is strict when $k<m$ or when the first inequality is
strict.

We first note the following auxiliary inequality.

$\prod_{j=1}^{k}b_{j}!=\prod_{j=1}^{k}{b_{j}!\over
b_{j}^{\prime}!}\prod_{j=1}^{k}b_{j}^{\prime}!\leq\prod_{j=1}^{k}{b_{j}!\over
b_{j}^{\prime}!}\left(\sum_{j=1}^{k}b_{j}^{\prime}-k\right)!\leq\left(\sum_{j=1}^{k}b_{j}-k\right)!$

where the last inequality stems from the fact that, for all $j$, we have that
the smallest factor $b_{j}^{\prime}+1$ of ${b_{j}!\over b_{j}^{\prime}!}$ is
at most $\left(\sum_{j=1}^{k}b_{j}^{\prime}-k\right)+1$.

Now, for $2\leq k<m$, we can use this inequality to establish the claim, where
we use the trivial observation from the start for the strict inequality below.

$\displaystyle\prod_{j=1}^{m}b_{j}!$ $\displaystyle=$
$\displaystyle\prod_{j=1}^{k}b_{j}!\prod_{j=k+1}^{m}b_{j}!\leq\left(\sum_{j=1}^{k}b_{j}-k\right)!\prod_{j=k+1}^{m}b_{j}!$
$\displaystyle<$
$\displaystyle\left(\left(\sum_{j=1}^{k}b_{j}-k\right)+\sum_{j=k+1}^{m}b_{j}-((1+(m-k))-1)\right)!=\left(\sum_{j=1}^{m}b_{j}-m\right)!$

The result is now proved via the Claim by considering the following cases.

Case 1: There are no two $i\not=k$ such that $b_{i}=b_{k}$.

In this case, assume, without loss of generality, that
$b_{1}<b_{2}<\cdots<b_{m}$.

If $m\geq 3$, we have $b_{1}\geq 2$, $b_{2}\geq 3$, $b_{3}\geq 4$. Because
$2!\cdot 3!\cdot 4!=288<720=6!=(2+3+4-3)!$, the result follows from the Claim.

This leaves the subcase $m=2$ and $b_{1}<b_{2}$. Because the vectors $(2,n)$
(with $n\geq 2$) are excluded, we only need to consider $b_{1}\geq 3$.

For $b_{1}\geq 4$, we have $b_{2}\geq 5$. Because $4!\cdot 5!=6!\cdot
4<7!=(4+5-2)!$, the result follows from the Claim.

For $b_{1}=3$, because $(3,4)$ is excluded, we have $b_{2}\geq 5$. Because
$3!\cdot 5!=6!=(3+5-2)!$, the result follows from the Claim.

Case 2: There are $i\not=k$ such that $b_{i}=b_{k}$.

Without loss of generality, resort the $b_{j}$ so that $i=1$ and $k=2$.

In case $b_{1}=b_{2}\geq 4$, because $4!\cdot 4!=4!\cdot 4\cdot
6<6!=(4+4-2)!$, the result follows from the Claim.

In case $b_{1}=b_{2}=3$, because the vector $(3,3)$ is excluded from
consideration, we must have $m\geq 3$. Because $2!\cdot 3!\cdot 3!=4!\cdot
3<5!=(2+3+3-3)!$, the result follows from the Claim.

In case $b_{1}=b_{2}=2$, because the vector $(2,2)$ is excluded from
consideration, we must have $m\geq 3$.

First consider the case that there is a $b_{i}\geq 4$. We can resort the
$b_{j}$ so that $b_{3}\geq 4$. Because $2!\cdot 2!\cdot 4!=4!\cdot
4<5!=(2+2+4-3)!$, the result follows from the Claim.

Next consider the case that all $b_{i}$ are less than $4$ and there is a
$b_{i}=3$. Trivially $2!\cdot 2!\cdot 3!=4!=(2+2+3-3)!$, and the non-strict
inequality follows from the Claim. For the strict inequality, we can focus on
the case $m\geq 4$ and we can assume (after possibly resorting) that
$b_{4}=3$. Because $2!\cdot 2!\cdot 2!\cdot 3!=4!\cdot 2<5!=(2+2+2+3-4)!$, the
result follows from the Claim.

This leaves the case that all the $b_{i}$ are equal to $2$. Because $(2,2)$
and $(2,2,2)$ are excluded from consideration, this means that $m\geq 4$. For
$m\geq 4$ we have $(2!)^{m}<(2m-m)!$, which completes the proof.

###### Lemma 2.8

Let $n\geq 6$ and let $k$ be a nontrivial divisor of $n$. Then
$k!\left(\left({n\over k}\right)!\right)^{k}<(n-1)!$.

Proof. By Lemma 2.7, we obtain

$\displaystyle k!\left(\left({n\over k}\right)!\right)^{k}$ $\displaystyle<$
$\displaystyle\left(k+k{n\over k}-(k+1)\right)!=(n-1)!$

###### Lemma 2.9

Let $P$ be a max-locked ordered set of width $w\geq 3$. In case $w\not=4$, let
$k$ be such that $\alpha(R_{k})\geq(w-1)!$. In case $w=4$, let $k$ be such
that $\alpha(R_{k})>8$. Then the following hold.

  1. 1.

If $R_{k}$ contains a non-maximal element, then no two elements of $R_{k}$
have equal sets of upper covers.

  2. 2.

If $R_{k}$ contains a non-minimal element, then no two elements of $R_{k}$
have equal sets of lower covers.

Proof. We will only prove part 1. Part 2 is proved dually. To simplify the
translation to the analogous proof for part 2, some parts of the proof below
are formulated to dualize easily.

Suppose, for a contradiction, that there are non-maximal $a,b\in R_{k}$ that
have the same strict upper bounds. Clearly, $R_{k}$ can be partitioned into
sets $A_{1},A_{2},\ldots,A_{n}$ such that, for all $\ell\in\\{1,\ldots,n\\}$
and for all $x,y\in A_{\ell}$, we have $\uparrow x\setminus\\{x\\}=\uparrow
y\setminus\\{y\\}$. Without loss of generality, we can assume $a,b\in A_{1}$.
Note that, for every $\Phi\in{\rm Aut}(P)$ and every
$\ell\in\\{1,\ldots,n\\}$, there is a $z\in\\{1,\ldots,n\\}$ such that
$\Phi[A_{\ell}]=A_{z}$.

Because $\alpha(R_{k})\geq(w-1)!$ and there is no $x\in P$ that is fixed by
all automorphisms, by Lemma 2.5, ${\rm Aut}(P)$ acts transitively on $R_{k}$.
Therefore, for all $\ell\in\\{1,\ldots,n\\}$, we have $|A_{\ell}|=|A_{1}|\geq
2$.

If $n$ were equal to $1$, then all elements of $R_{k}$ would have the same
strict upper bounds. By Lemma 2.5, we have that $|R_{k}|=w$. Because the width
of $P$ is $w$, every element of rank less than $k$ is below an element of rank
$k$, and every element of $\\{x\in P:{\rm rank}(x)>k\\}$ is above an element
of rank $k$. Because any two elements of $R_{k}$ have the same strict upper
bounds, we first infer $\\{x\in P:{\rm rank}(x)>k\\}>R_{k}$, and then $\\{x\in
P:{\rm rank}(x)>k\\}>\\{x\in P:{\rm rank}(x)\leq k\\}$, contradicting that $P$
is coconnected. Thus $n\geq 2$. We conclude that $w$ is not prime, and, in
particular, $w\not\in\\{3,5\\}$.

Because every $\Phi\in{\rm Aut}(P)$ preserves the blocks of the partition into
the $A_{j}$, we obtain that
$\alpha(R_{k})\leq\ell!\left(\left({w\over\ell}\right)!\right)^{\ell}$. By
Lemma 2.8, for $w\geq 6$, this leads to
$\alpha(R_{k})\leq\ell!\left(\left({w\over\ell}\right)!\right)^{\ell}<(w-1)!$,
which is not possible. Hence $w=4$.

Because $w=4$, we have $n=2$ and $|A_{1}|=|A_{2}|=2$. We conclude
$\alpha(R_{k})\leq 8$, a contradiction.

###### Lemma 2.10

Let $P$ be a max-locked ordered set of height $1$ and width $w\geq 3$. Then
$P$ is isomorphic to $S_{w}$ or $wC_{2}$.

Proof. By duality, without loss of generality, for $w\not=4$, we can assume
that $\alpha(R_{0})\geq(w-1)!$, and, for $w=4$, we can assume that
$\alpha(R_{0})>8$. By Lemma 2.5, $|R_{0}|=w$ and ${\rm Aut}(P)$ acts
transitively on $R_{0}$. By part 1 of Lemma 2.9, no two minimal elements of
$P$ have equal sets of strict upper bounds.

Because no two elements of $R_{0}$ have equal sets of strict upper bounds,
$R_{0}$ does not contain any order-autonomous antichains. By Lemma 2.1 (with
$A=R_{0}$), for all $\Phi,\Psi\in{\rm Aut}(P)$, we have that
$\Phi|_{R_{0}}\not=\Psi|_{R_{0}}$ implies $\Phi|_{R_{1}}\not=\Psi|_{R_{1}}$,
and hence $\alpha(R_{1})\geq\alpha(R_{0})\geq(w-1)!$. By Lemma 2.5, we obtain
that $|R_{1}|=w$ and that ${\rm Aut}(P)$ acts transitively on $R_{1}$.

Because $|R_{1}|=w$, $P$ is coconnected, and ${\rm Aut}(P)$ acts transitively
on $R_{0}$, there is a number $u<w$ such that every minimal element is below
exactly $u$ elements of $R_{1}$. Because $|R_{1}|=w=|R_{0}|$ and ${\rm
Aut}(P)$ acts transitively on $R_{1}$, every maximal element is above exactly
$u$ elements of $R_{0}$.

Because we can replace $P$ with the ordered set $P^{\prime}$ of height $1$
such that, for all elements $x\in R_{0}$ and all elements $z\in R_{1}$, we
have $x<z$ in $P^{\prime}$ iff $x\not\sim z$ in $P$, we only need to conduct
the argument for $u\in\left\\{1,\ldots,\left\lfloor{w\over
2}\right\rfloor\right\\}$.

Suppose, for a contradiction that $P$ is a max-locked ordered set of height
$1$ and width $w$ that is not isomorphic to either of $S_{w}$ or $wC_{2}$.

In case $u=1$, $P$ would be an ordered set $wC_{2}$, contradicting that $P$ is
a counterexample. Thus $u\geq 2$.

In case $u=2$, $P$ would be a pairwise disjoint union of crowns. Because
$u\leq\left\lfloor{w\over 2}\right\rfloor$, we have $w\geq 4$. For $w\geq 5$,
such unions have fewer than $(w-1)!$ automorphisms, contradicting that
$\alpha(R_{0})\geq(w-1)!$. For $w=4$, because no two minimal elements have the
same strict upper bounds, we obtain that $P$ is a crown with $8$ elements,
contradicting that, for $w=4$, we have $\alpha(R_{0})>8$. Thus
$u\in\left\\{3,\ldots,\left\lfloor{w\over 2}\right\rfloor\right\\}$.

Let $x$ be a fixed maximal element of $P$ and let $M:=\downarrow
x\setminus\\{x\\}\subset R_{0}$. Under an arbitrary automorphism of $P$, there
are $w$ possible images for $x$ (and hence for $M$), there are $\leq u!$ ways
to map $M$ to its image and there are $\leq(w-u)!$ ways to map $R_{0}\setminus
M$ to its image. Thus $(w-1)!\leq\alpha(R_{0})\leq w\cdot u!\cdot(w-u)!$. For
$w\geq 9$ and $3\leq u\leq\left\lfloor{w\over 2}\right\rfloor$, we have
$w\cdot u!=(w\cdot 3!)\cdot 4\cdots u<(w-1)(w-2)\cdot 4\cdots
u<(w-1)\cdots(w-u+1)!$ and hence $w\cdot u!\cdot(w-u)!<(w-1)!$, a
contradiction. Thus $w\leq 8$. Because $3\leq u\leq\left\lfloor{w\over
2}\right\rfloor$, we obtain $w\in\\{6,7,8\\}$.

Moreover, for $w=8$ and $u=4$, we have $8\cdot 4=32<35=7\cdot 5$, so $w\cdot
u!\cdot(w-u)!=8\cdot 4!\cdot 4!=8\cdot 4\cdot 6\cdot 4!<7\cdot 5\cdot 6\cdot
4!=7!=(w-1)!$, a contradiction. Thus, in case $w=8$, we have $u\not=4$, which
means that, in all remaining cases, we have $u=3$.

First consider the case that there are no two distinct elements $x,y\in R_{1}$
such that $|\downarrow x~{}\cap\downarrow y|>1$. Let $b\in R_{0}$ and let
$t_{1},t_{2},t_{3}\in R_{1}$ be its upper covers. Then, for any two distinct
$i,j\in\\{1,2,3\\}$, we have $|\downarrow t_{1}~{}\cap\downarrow t_{2}~{}|=1$.
Hence $|\downarrow t_{1}~{}\cup\downarrow t_{2}~{}\cup\downarrow t_{3}~{}|=7$.
In particular, $w\in\\{7,8\\}$. Let $\Phi$ be any automorphism of $P$. There
are $w$ possible images $\Phi(b)$, and this image determines the image of the
element (if there is one) of $R_{0}\setminus(\downarrow t_{1}~{}\cup\downarrow
t_{2}~{}\cup\downarrow t_{3})$. The remaining three doubletons $(\downarrow
t_{j}~{}\cap R_{0})\setminus\\{b\\}$, must be mapped to the corresponding
three doubletons $(\downarrow\Phi(t_{j})~{}\cap R_{0})\setminus\\{\Phi(b)\\}$.
There are $3!\cdot 2!\cdot 2!\cdot 2!$ ways to do this. In total,
$(w-1)!\leq\alpha(R_{0})\leq w\cdot 3!\cdot 2!\cdot 2!\cdot 2!=2\cdot w\cdot
4!$. Because $w\in\\{7,8\\}$ and $6\cdot 5>2\cdot 7$ and $7\cdot 6\cdot
5>2\cdot 8$, this is a contradiction. We conclude that there are distinct
elements $x,y\in R_{1}$ such that $|\downarrow x~{}\cap\downarrow y~{}|>1$,
and hence such that $|\downarrow x~{}\cap\downarrow y~{}|=2$.

Let $x,y\in R_{1}$ such that $|\downarrow x~{}\cap\downarrow y~{}|=2$. Let
$M:=\downarrow x\cap R_{0}$. As above, under an arbitrary automorphism $\Phi$
of $P$, there are $w$ possible images for $x$ (and hence for $M$) and there
are $\leq 3!$ ways to map $M$ to its image. Furthermore, $\Phi(y)$ must be
above the images of all elements of $\downarrow y\cap M=\\{b_{1},b_{2}\\}$
with $b_{1}\not=b_{2}$. Because $\Phi(x)>\Phi(b_{1}),\Phi(b_{2})$ and
$|\uparrow\Phi(b_{1})\cap\uparrow\Phi(b_{2})|=|\uparrow b_{1}\cap\uparrow
b_{2}|<3$, there is only a single point left for $\Phi(y)$. Hence, $\Phi(y)$
is determined by $\Phi|_{M}$, and a fortiori so is the image of the unique
point of $(\downarrow y\setminus\downarrow x)\cap R_{0}$.

The remaining $(w-4)$ points in $R_{0}$ can be mapped to their images in at
most $(w-4)!$ ways. All together, $(w-1)!\leq\alpha(R_{0})\leq w\cdot
3!\cdot(w-4)!$. However, $(w-1)(w-2)(w-3)>6w$, which is the final
contradiction that completes this proof.

###### Lemma 2.11

Let $P$ be a max-locked ordered set of width $w\geq 3$. Then, for every $j$
such that $R_{j+1}\not=\emptyset$, we have that $R_{j}\cup R_{j+1}$ is
isomorphic to $S_{w}$ or $wC_{2}$. In particular, $|{\rm Aut}(P)|=w!$

Proof. Let $k$ be such that $\alpha(R_{k})\geq(w-1)!$, and, in case $w=4$,
assume that $\alpha(R_{k})>8$. By Lemma 2.5, ${\rm Aut}(P)$ acts transitively
on $R_{k}$ and $|R_{k}|=w$.

Consider the case $R_{k+1}\not=\emptyset$. Because ${\rm Aut}(P)$ acts
transitively on $R_{k}$ and $P$ is coconnected, no element of $R_{k}$ is a
lower bound of $R_{k+1}$. Thus $R_{k}\cup R_{k+1}$ is coconnected, and hence
$R_{k}\cup R_{k+1}$ is max-locked of height $1$. By Lemma 2.10, $R_{k}\cup
R_{k+1}$ is isomorphic to $S_{w}$ or $wC_{2}$. Let $h$ be the height of $P$.
Inductively, for all $j\in\\{k,\ldots,h-1\\}$, we obtain that $R_{j}\cup
R_{j+1}$ is isomorphic to $S_{w}$ or $wC_{2}$.

Because $P$ has width $w$, every element of rank less than $k$ is comparable
to an element of rank $k$. Hence, for all $j\in\\{k,\ldots,h\\}$, the set
$R_{j}$ is equal to the set $R_{h-j}^{d}$ of elements of dual rank $h-j$.

Applying the same argument to $R_{h-k}^{d}$ in the dual ordered set of $P$
proves that, for all $j\in\\{h-k,\ldots,h-1\\}$, the set $R_{j}^{d}\cup
R_{j+1}^{d}$ is isomorphic to $S_{w}$ or $wC_{2}$. Hence, for all
$j\in\\{h-k,\ldots,h\\}$, the set $R_{j}^{d}$ is equal to the set $R_{h-j}$.
We conclude that, for all $j\in\\{k,\ldots,h-1\\}$, the set $R_{j}\cup
R_{j+1}$ is isomorphic to $S_{w}$ or $wC_{2}$.

The claim on the number of automorphisms is an easy induction on the height
$h$ of the ordered set $P$ in which the union of any two consecutive nonempty
ranks is isomorphic to $S_{w}$ or $wC_{2}$. For the base step, if $h=1$, then
$P$ is isomorphic to $S_{w}$ or $wC_{2}$ and hence $|{\rm Aut}(P)|=w!$. For
the induction step, let $h>1$ and assume the claim holds for all ordered sets
as indicated and of height less than $h$. Because $P\setminus R_{h}$ is such
that the union of any two consecutive nonempty ranks is isomorphic to $S_{w}$
or $wC_{2}$, we have $|{\rm Aut}(P\setminus R_{h})|=w!$. Because $R_{h-1}\cup
R_{h}$ is isomorphic to $S_{w}$ or $wC_{2}$, we can apply Lemma 2.1 and we
obtain that every automorphism of $P\setminus R_{h}$ has at most one extension
to $P$. Because every automorphism of $P\setminus R_{h}$ has a natural
extension to $P$, we obtain $|{\rm Aut}(P)|=|{\rm Aut}(P\setminus R_{h})|=w!$.

###### Remark 2.12

Note that ordered sets such that, for every $j$ such that
$R_{j+1}\not=\emptyset$, we have that $R_{j}\cup R_{j+1}$ is isomorphic to
$wC_{2}$ need not be unions of pairwise disjoint chains: There can be $k\geq
0$ and $\ell\geq 2$ such that $R_{k}<R_{k+\ell}$. The ordered set $2C_{3}^{*}$
from part 1 of Definition 6.2 is one such example.

###### Definition 2.13

We define coconnected ordered sets of width $2$ with exactly 2 automorphisms
to be max-locked, too.

##  3 Interdependent Orbit Unions

The proof of Lemma 2.11 shows how the action of the automorphism group on a
single set of elements of rank $k$ can, in natural fashion, “transmit
vertically” though the whole ordered set. In the situation of Lemma 2.11, the
sets $R_{k}$ happen to be orbits (see Definition 3.1 below) of $P$. In
general, the “transmission” must focus on the orbits, not the sets $R_{k}$,
and it can “transmit” the action of the automorphism group on one orbit $O$ to
orbits that have no points that are comparable to any element of $O$. It
should be noted that interdependent orbit unions (see Definition 3.5 below) in
graphs have also proven useful in the set reconstruction of certain graphs,
see [15]. Although the presentation up to Proposition 3.10 translates directly
to and from the corresponding results in [15], all proofs are included to keep
this presentation self-contained.

###### Definition 3.1

(Compare with Definition 8.1 in [15].) Let $P$ be an ordered set, let $G$ be a
subgroup of ${\rm Aut}(P)$ and let $x\in P$. Then the set $G\cdot
x:=\\{\Phi(x):\Phi\in G\\}$ is called the orbit of $x$ under the action of $G$
or the $G$-orbit of $x$. Explicit mention of $G$ or $x$ can be dropped when
there is only one group under consideration or when specific knowledge of $x$
is not needed. When no group $G$ is explicitly mentioned at all, we assume by
default that $G={\rm Aut}(P)$. The group generated by a single automorphism is
denoted $\langle\Phi\rangle$.

Note that, if a strict subset $Q\subset P$ was obtained by removing a union of
${\rm Aut}(P)$-orbits, then ${\rm Aut}(P)$-orbits that are contained in $Q$
can be strictly contained in ${\rm Aut}(Q)$-orbits: The ${\rm Aut}(P)$-orbits
of the ordered set $P$ in Figure 2 are marked by ovals. We can see that, for
$X\in\\{A,B,C,D\\}$, the ${\rm Aut}(P)$-orbits $X$ and $\widetilde{X}$ are
strictly contained in the ${\rm Aut}(P\setminus M)$-orbit
$X\cup\widetilde{X}$. For this reason (further elaborated later in Remark
3.11), dictated orbit structures will be useful for the representation of
${\rm Aut}(P)$ in Proposition 3.10 and they are vital for the induction proof
of Theorem 7.4.

###### Definition 3.2

(Compare with Definition 8.2 in [15].) Let $P$ be an ordered set and let
${\cal D}$ be a partition of $P$ into antichains. Then ${\rm Aut}_{\cal D}(P)$
is the set of automorphisms $\Phi:P\to P$ such that, for every $\Phi$-orbit
$O:=\langle\Phi\rangle\cdot x$ of $\Phi$, there is a $D\in{\cal D}$ such that
$O\subseteq D$. In this context, the partition ${\cal D}$ is called a dictated
orbit structure for $P$, and the pair $(P,{\cal D})$ is called a structured
ordered set. ${\rm Aut}_{\cal D}(P)$-orbits will, more briefly, be called
${\cal D}$-orbits.

The partition of $P$ into its ${\rm Aut}(P)$-orbits is called the natural
orbit structure of $P$, which will typically be denoted ${\cal N}$. When
working with the natural orbit structure, explicit indications of the
automorphism set, usually via subscripts or prefixes ${\cal D}$, will often be
omitted.

$A$$C$$\widetilde{A}$$\widetilde{C}$$M$$B$$D$$\widetilde{B}$$\widetilde{D}$

Figure 2: An ordered set $P$ with orbits marked with ovals.

Clearly, ${\rm Aut}_{\cal D}(P)$ is a subgroup of the automorphism group ${\rm
Aut}(P)$. Moreover, ${\rm Aut}_{\cal D}(P)\not={\rm Aut}(P)$ iff there are an
orbit $O$ of $P$ and a $D\in{\cal D}$ such that $O\cap D\not=\emptyset$ and
$O\not\subseteq D$.

The proof of Lemma 2.11 has already shown that, for an automorphism $\Phi$,
the values on a single orbit of $\Phi$ can completely determine $\Phi$. The
relation of direct interdependence in Definition 3.3 below provides a more
detailed view of this observation as well as the simple observation in Lemma
2.1.

###### Definition 3.3

(Compare with Definition 8.3 in [15].) Let $(P,{\cal D})$ be a structured
ordered set and let $C,D$ be two ${\cal D}$-orbits of $P$ such that there are
a $c_{1}\in C$ and a $d_{1}\in D$ such that $c_{1}<d_{1}$. We will write
$C\upharpoonleft_{\cal D}D$ and $D\downharpoonright_{\cal D}C$ iff there are
$c_{2}\in C$ and a $d_{2}\in D$ such that $c_{2}\not\sim d_{2}$. In case
$C\upharpoonleft_{\cal D}D$ or $C\downharpoonright_{\cal D}D$, we write
$C\upharpoonleft\\!\downharpoonright_{\cal D}D$ and say that $C$ and $D$ are
directly interdependent.

Figure 2 shows how (connection through) direct interdependence can allow one
orbit to determine the values of automorphisms on many other orbits: In the
ordered set in Figure 2, we have $A\upharpoonleft_{\cal
N}B\downharpoonright_{\cal N}M\upharpoonleft_{\cal
N}\widetilde{B}\downharpoonright_{\cal N}\widetilde{A}$ and the values of any
automorphism on $A\cup B\cup M\cup\widetilde{B}\cup\widetilde{A}$ are
determined the by automorphism’s values on $A$. Note, however, that even
direct interdependence $C\upharpoonleft\\!\downharpoonright_{\cal N}D$ does
not mean that automorphisms are determined by the values on either orbit $C$
or $D$: Consider a $6$-crown in which every element is replaced with an order-
autonomous $2$-antichain: The minimal elements form an orbit, as do the
maximal elements, the two orbits are directly interdependent, but no
automorphism is completely determined solely by its values on the minimal (or
the maximal) elements. This idea will be explored further in Section 7.

We now turn our attention to interdependent orbit unions, which are the unions
of the connected components of the orbit graph defined in Definition 3.4
below. Orbit graphs themselves will take center stage starting in Section 4.

###### Definition 3.4

Let $(P,{\cal D})$ be a structured ordered set. The orbit graph ${\cal
O}(P,{\cal D})$ of $P$ is defined to be the graph whose vertex set is the set
of all ${\cal D}$-orbits such that two ${\cal D}$-orbits $D_{1}$ and $D_{2}$
are adjacent iff $D_{1}\upharpoonleft\\!\downharpoonright_{\cal D}D_{2}$.

Although our main focus will ultimately be on orbit graphs for structured
ordered sets in which every $D\in{\cal D}$ is a ${\cal D}$-orbit, also see
part 3 of Definition 3.15 below, until that time, we must keep in mind that
the $D\in{\cal D}$ need not be orbits themselves.

###### Definition 3.5

(Compare with Definition 8.5 in [15].) Let $(P,{\cal D})$ be a structured
ordered set and let ${\cal O}(P,{\cal D})$ be its orbit graph. If ${\cal E}$
is a connected component of ${\cal O}(P,{\cal D})$, then we will call the set
$\bigcup{\cal E}\subseteq P$ an interdependent ${\cal D}$-orbit union.

###### Definition 3.6

(Compare with Definition 8.6 in [15].) Let $(P,{\cal D})$ be a structured
ordered set and let $Q\subseteq P$ such that, for all ${\cal D}$-orbits $D$,
we have $D\subseteq Q$ or $D\cap Q=\emptyset$. The dictated orbit structure
for $Q$ induced by ${\cal D}$, denoted ${\cal D}|Q$, is defined to be the set
of all ${\cal D}$-orbits that are contained in $Q$.

For the natural orbit structure ${\cal N}$ for $P$, the dictated orbit
structure for $Q$ induced by ${\cal N}$ will be called the naturally required
automorphism structure ${\cal N}|Q$.

Note that, for induced orbit structures ${\cal D}|Q$, every $D\in{\cal D}|Q$
is an orbit. Proposition 3.7 below now shows how interdependent ${\cal
D}$-orbit unions reside in an ordered set. It also lays the groundwork for
representing automorphisms through certain automorphisms on the non-singleton
interdependent orbit unions in Proposition 3.10.

###### Proposition 3.7

(Compare with Proposition 8.7 in [15].) Let $(P,{\cal D})$ be a structured
ordered set and let $U$ be an interdependent ${\cal D}$-orbit union. Then the
following hold.

  1. 1.

For all $x\in P\setminus U$ and all $C\in{\cal D}|U$, the following hold.

    1. (a)

If there is a $c\in C$ such that $c<x$, then $C<x$.

    2. (b)

If there is a $c\in C$ such that $c>x$, then $C>x$.

  2. 2.

For every $\Phi\in{\rm Aut}_{\cal D}(P)$, we have that $\Phi|_{U}\in{\rm
Aut}_{{\cal D}|U}(U)$. In particular, this means that the ${\cal D}|U$-orbits
are just the sets in ${\cal D}|U$.

  3. 3.

For every $\Psi\in{\rm Aut}_{{\cal D}|U}(U)$, the function
$\Psi^{P}(x):=\cases{\Psi(x);&if $x\in U$,\cr x;&if $x\in P\setminus U$,}$ is
an automorphism of $P$.

Proof. To prove part 1a, let $x\in P\setminus U$ and $C\in{\cal D}|U$ be so
that there is a $c\in C$ such that $c<x$. Let $X$ be the ${\cal D}$-orbit of
$x$. Because $x\not\in U$, we must have
$X\not\upharpoonleft\\!\downharpoonright_{\cal D}C$. Because $C\ni c<x\in X$,
we must have that $C<X$ and hence $C<x$.

Part 1b is proved dually.

Part 2 follows directly from the definitions.

To prove part 3, let $\Psi\in{\rm Aut}_{{\cal D}|U}(U)$. Clearly, $\Psi^{P}$
is bijective. To prove that $\Psi^{P}$ is order-preserving, let $x<y$. If
$x,y$ are both in $U$ or both in $P\setminus U$, we obtain
$\Psi^{P}(x)<\Psi^{P}(y)$. In case $x\in P\setminus U$ and $y\in U$, let
$Y\in{\cal D}|U$ be so that $y\in Y$. Then $\Psi(y)\in Y$. By part 1b, we have
that $x<Y$ and hence $\Psi^{P}(x)=x<Y\ni\Psi^{P}(y)$. The case in which $y\in
P\setminus U$ and $x\in U$ is handled dually.

###### Definition 3.8

(Compare with Definition 8.8 in [15].) Let $(P,{\cal D})$ be a structured
ordered set and let $U$ be an interdependent ${\cal D}$-orbit union. We define
${\rm Aut}_{{\cal D}|U}^{P}(U)$ to be the set of automorphisms
$\Psi^{P}\in{\rm Aut}(P)$ as in part 3 of Proposition 3.7.

Let $P$ be an ordered set, let ${\cal D}$ be a dictated orbit structure for
$P$ and let $U,U^{\prime}$ be disjoint interdependent ${\cal D}$-orbit unions.
Then, clearly, for $\Psi^{P}\in{\rm Aut}_{{\cal D}|U}^{P}(U)$ and
$\Phi^{P}\in{\rm Aut}_{{\cal D}|U^{\prime}}^{P}(U^{\prime})$, we have
$\Psi^{P}\circ\Phi^{P}=\Phi^{P}\circ\Psi^{P}$. Hence the following definition
is sensible.

###### Definition 3.9

(Compare with Definition 8.9 in [15].) Let $P$ be an ordered set and let
${\cal A}_{1},\ldots,{\cal A}_{z}\subseteq{\rm Aut}(P)$ be sets of
automorphisms such that, for all pairs of distinct $i,j\in\\{1,\ldots,z\\}$,
all $\Phi_{i}\in{\cal A}_{i}$ and all $\Phi_{j}\in{\cal A}_{j}$, we have
$\Phi_{i}\circ\Phi_{j}=\Phi_{j}\circ\Phi_{i}$. We define
$\bigcirc_{j=1}^{z}{\cal A}_{j}$ to be the set of compositions
$\Psi_{1}\circ\cdots\circ\Psi_{z}$ such that, for $j=1,\ldots,z$, we have
$\Psi_{j}\in{\cal A}_{j}$.

###### Proposition 3.10

(Compare with Proposition 8.10 in [15].) Let $P$ be an ordered set with
natural orbit structure ${\cal N}$ and let $U_{1},\ldots,U_{z}$ be the non-
singleton interdependent orbit unions of $P$. Then ${\rm
Aut}(P)=\bigcirc_{j=1}^{z}{\rm Aut}_{{\cal N}|U_{j}}(U_{j})$, and consequently
$|{\rm Aut}(P)|=\prod_{j=1}^{z}\left|{\rm Aut}_{{\cal
N}|U_{j}}^{P}(U_{j})\right|$.

Proof. The containment ${\rm Aut}(P)\supseteq\bigcirc_{j=1}^{z}{\rm
Aut}_{{\cal N}|U_{j}}^{P}(U_{j})$ follows from part 3 of Lemma 3.7.

By part 2 of Lemma 3.7, for every $\Phi\in{\rm Aut}(P)$ and every
$j\in\\{1,\ldots,z\\}$, we have that $\Phi|_{U_{j}}\in{\rm Aut}_{{\cal
N}|U_{j}}(U_{j})$. Because $\Phi$ fixes all points in
$P\setminus\bigcup_{j=1}^{z}U_{j}$, we have
$\Phi=\Phi|_{U_{1}}^{P}\circ\cdots\circ\Phi|_{U_{z}}^{P}$. Hence ${\rm
Aut}(P)\subseteq\bigcirc_{j=1}^{z}{\rm Aut}_{{\cal N}|U_{j}}^{P}(U_{j})$.

###### Remark 3.11

(Compare with Remark 8.11 in [15].) Although the naturally required
automorphism structure ${\cal N}|U$ may look more technical than natural, it
is indispensable for the representation in Proposition 3.10. Consider the
ordered set in Figure 2. The natural orbit unions in this ordered set are
$U_{1}:=A\cup B\cup M\cup\widetilde{B}\cup\widetilde{A}$ and $U_{2}:=C\cup
D\cup\widetilde{D}\cup\widetilde{C}$. However, when considering $U_{2}$ as an
ordered set by itself, the ${\rm Aut}(U_{2})$-orbits are $C\cup\widetilde{C}$
and $D\cup\widetilde{D}$, whereas the ${\rm Aut}(P)$-orbits in $U_{2}$ are
$C,D,\widetilde{C}$ and $\widetilde{D}$. Hence, we cannot use the automorphism
groups ${\rm Aut}(U_{j})$ in place of their subgroups ${\rm Aut}_{{\cal
N}|U_{j}}(U_{j})$ in Proposition 3.10.

The same effect was observed in the introduction in the case that $M$ is
removed from the ordered set. This is why dictated orbit structures are also
crucial for the induction in the proof of Theorem 7.4.

Proposition 3.10 allows us to focus our efforts to bound the number of
automorphisms on ordered sets that consist of a single interdependent orbit
union. Lemma 3.12 below makes the, admittedly simple, connection to max-locked
ordered sets.

###### Lemma 3.12

Let $P$ be an ordered set of width $\leq w$ that consists of a single ${\rm
Aut}(P)$-orbit union and which has an ${\rm Aut}(P)$-orbit $X$ such that ${\rm
Aut}(P)$ induces $N\geq(w-1)!$ permutations on $X$. In case $w=4$, assume that
${\rm Aut}(P)$ induces $N>8$ permutations on $X$. Then $P$ is max-locked.

Proof. Because $P$ consists of a single ${\rm Aut}(P)$-orbit union, $P$ is a
coconnected ordered set of width $w$ such that there is no $p\in P$ that is
fixed by all automorphisms of $P$. With $k$ such that $X\subseteq R_{k}$, the
hypothesis guarantees that $\alpha(R_{k})\geq(w-1)!$ and, in case $w=4$,
$\alpha(R_{k})>8$.

Lemma 3.13 below can be considered the prototype for the key result in this
paper, Theorem 7.4. In most interdependent orbit unions in a non-max-locked
ordered set, the upper bound on the number of automorphisms is a product of
factorials. By Lemma 2.11, the factorials cannot exceed $(w(P)-1)!$ (for
$w(P)=4$, some cases need to be handled separately), and the sum of the
numbers whose factorials are multiplied will be bounded by half the size of
the interdependent orbit union minus the number of (dictated) orbits in the
interdependent orbit union. We introduce some terminology to express this idea
after Lemma 3.13.

###### Lemma 3.13

Let $P$ be a connected non-max-locked ordered set of width $w\geq 3$ and let
$U\subset P$ be a max-locked interdependent orbit union with $m\geq 3$
nonempty ranks and width $a\leq w-1$ such that $(m,a)\not=(3,2)$, that is,
such that $P$ is not isomorphic to $2C_{3}$. Then $|{\rm Aut}_{{\cal
D}|U}(U)|=a!\leq\min\left\\{(w-1)!,\left\lfloor{1\over
2}\left(|U|-m\right)\right\rfloor!\right\\}$.

Proof. By Lemma 2.11, we have $|{\rm Aut}_{{\cal D}|U}(U)|=a!\leq(w-1)!$.
Because $U$ is max-locked, it consists of $m$ natural orbits with $a$ elements
each. Hence $\left\lfloor{1\over
2}\left(|U|-m\right)\right\rfloor=\left\lfloor{1\over
2}\left(ma-m\right)\right\rfloor=\left\lfloor{1\over
2}\left(m(a-1)\right)\right\rfloor.$ In case $m\geq 4$, we have that the last
term is at least $2(a-1)\geq a$. In case $m=3$ and $a\geq 3$, we have that the
last term is $\left\lfloor{1\over
2}\left(3(a-1)\right)\right\rfloor=\left\lfloor{1\over
2}\left(3a-3\right)\right\rfloor\geq\left\lfloor{1\over
2}\left(2a\right)\right\rfloor=a.$

We conclude this section by introducing ideas and terminology that will be
fundamental for the remainder of this paper.

###### Definition 3.14

We will say that the structured ordered set $(P,{\cal D}_{P})$ is (dually)
isomorphic to the structured ordered set $(Q,{\cal D}_{Q})$ iff there is a
(dual) isomorphism $\Phi:P\to Q$ such that, for all $D\in{\cal D}_{P}$, we
have $\Phi[D]\in{\cal D}_{Q}$.

###### Definition 3.15

Let $(P,{\cal D})$ be a structured ordered set.

  1. 1.

We call $(P,{\cal D})$ an interdependent orbit union iff $\bigcup{\cal D}$ is
an interdependent ${\cal D}$-orbit union.

  2. 2.

We say $(P,{\cal D})$ is without slack iff none of the sets in ${\cal D}$
contains a nontrivial order-autonomous antichain.

  3. 3.

We call $(P,{\cal D})$ tight iff it is without slack and each $D\in{\cal D}$
is a ${\cal D}$-orbit, that is, it is without slack and ${\rm Aut}_{\cal
D}(P)$ acts transitively on every $D\in{\cal D}$.

  4. 4.

If $(U,{\cal D})$ is an interdependent orbit union that is not max-locked and
such that $U$ is not a singleton, we say $(U,{\cal D})$ is flexible.

By Lemma 3.13, our main focus will be on flexible interdependent orbit unions
$(U,{\cal D})$. (Max-locked interdependent orbit unions of height $1$ or of
width $2$ and height $3$ will be handled separately.) Because we will first
focus on indecomposable ordered sets, we will assume that $(U,{\cal D})$ is
without slack. Because we can always refine the dictated orbit structure, we
are free to assume that $(U,{\cal D})$ is tight.

Similar to Lemma 3.13 we define the following.

###### Definition 3.16

Let $(P,{\cal D})$ be a structured ordered set, let $w\geq 3$ and let
$o\in{\mathbb{Z}}$. Then $(P,{\cal D})$ is called offset by $o$ from being
$w$-adequately bounded iff there are numbers
$w_{1},\ldots,w_{M}\in\\{0,\ldots,w-1\\}$ such that $|{\rm Aut}_{{\cal
D}}(P)|\leq\prod_{j=1}^{M}w_{j}!$ and such that
$\sum_{j=1}^{M}w_{j}\leq\left\lfloor{1\over 2}\left(|P|-|{\cal
D}|+o\right)\right\rfloor$. When $o$ can be chosen to be zero, $(P,{\cal D})$
is called $w$-adequately bounded.

Note that, although $w$ will often be the width of the ordered set, in
Definition 3.16 above, it is just a number. Lemma 6.6 and Theorem 7.4 show the
ultimate use of this idea. Similarly, for some specific constructions, we will
choose $M=m=|{\cal D}|$ and some $w_{j}!$ will be a bound on the number of
permutations induced by ${\rm Aut}_{\cal D}(U)$ on $D_{j}$, but we should note
that there is no formal connection between the $w_{j}$ and the $D_{j}$ other
than the final inequality in Definition 3.16.

By Lemma 3.13 max-locked interdependent orbit unions with $m\geq 3$ nonempty
ranks and width $a\leq w-1$ such that $(m,a)\not=(3,2)$ are $w$-adequately
bounded. The ordered set $2C_{3}$ is offset by 1 from being $3$-adequately
bounded. We denote the natural dictated orbit structure of $2C_{3}$ by ${\cal
D}(2C_{3})$. By Lemma 2.10, max-locked interdependent orbit unions of height
$1$ and width $w$ have $w!$ automorphisms, $2w$ elements and $2$ orbits, so
they are are offset by $2$ from being $w$-adequately bounded. From this point
forward through the end of Section 7, our goal is to prove that most non-max-
locked interdependent orbit unions $U$ are $\max\\{w(U),5\\}$-adequately
bounded and to treat the remaining cases separately. Section 4 provides the
requisite structural insights and some inequalities, Section 6 provides the,
unfortunately a bit technical, base step of the induction, which is then
completed in Section 7.

##  4 The Orbit Graph of an Interdependent Orbit Union

The idea for producing a bound on the number of automorphisms for a flexible
tight interdependent orbit union is an induction on the number of dictated
orbits. Recall that, for tight interdependent orbit unions $(U,{\cal D})$, we
have that every $D\in{\cal D}$ is an orbit. Hence the vertex set of ${\cal
O}(U,{\cal D})$ is ${\cal D}$. When a dictated orbit $D_{n}\in{\cal D}$ is
removed, the orbit graph can become disconnected and the resulting structured
ordered set may contain nontrivial order-autonomous antichains. We start with
some standard notation that assures that the orbits with indices smaller than
$n$ form a component of the resulting graph ${\cal O}(U,{\cal D})-D_{n}$, and
which allows easy reference to orbits with certain properties. This notation
will be used throughout this section.

###### Notation 4.1

Throughout this section, $(U,{\cal D})$ will be a flexible tight
interdependent orbit union with $|{\cal D}|\geq 3$, with the labeling of the
elements of ${\cal D}=\\{D_{1},\ldots,D_{m}\\}$ and $n\geq 3$ chosen so that
the following hold.

  1. 1.

$\\{D_{1},\ldots,D_{n-1}\\}$ is a connected component of the graph ${\cal
O}(U,{\cal D})-D_{n}$.

  2. 2.

The orbits that are directly interdependent with $D_{n}$ are
$D_{s},\ldots,D_{n-1}$ and $D_{r},\ldots,D_{m}$.

  3. 3.

The orbits that contain nontrivial $U\setminus\bigcup_{i=n}^{m}D_{i}$-order-
autonomous antichains are $D_{t},\ldots,D_{n-1}$.

Note that Notation 4.1 allows for $n=m$, that is, for $D_{n}$ to not be a
cutvertex of ${\cal O}(U,{\cal D})$. Moreover, because $(U,{\cal D})$ is an
interdependent orbit union, ${\cal O}(U,{\cal D})$ is connected, so $s\leq
n-1$. For the other parameters, $r>m$ or $t>n-1$ shall indicate that there are
no orbits as described via $r$ or $t$.

To easily refer to the (possibly trivial) order-autonomous antichains in the
orbits $D_{s},\ldots,D_{n-1}$, we introduce the following notation.

###### Notation 4.2

For every $j\in\\{s,\ldots,n-1\\}$, we let $A_{1}^{j},\ldots,A_{\ell_{j}}^{j}$
be the maximal $U\setminus\bigcup_{i=n}^{m}D_{i}$-order-autonomous antichains
that partition $D_{j}$. We set ${\cal
A}^{j}:=\\{A_{1}^{j},\ldots,A_{\ell_{j}}^{j}\\}$. Moreover, for every
$i\in\\{1,\ldots,\ell_{j}\\}$, we choose a fixed element $a_{i}^{j}\in
A_{i}^{j}$. Note that, for $s\leq j\leq t-1$, the sets $A_{i}^{j}$ are
singletons.

The fact that automorphisms map maximal order-autonomous antichains to maximal
order-autonomous antichains motivates the definition below, which will
frequently be used and which leads to our first insights.

###### Definition 4.3

Let $S$ be a set, let ${\cal A}=\\{A_{1},\ldots,A_{\ell}\\}$ be a partition of
$S$ and let $\Phi:S\to S$ be a permutation of $S$. We say that $\Phi$ respects
the partition ${\cal A}$ iff, for every $i\in\\{1,\ldots,\ell\\}$, there is a
$j\in\\{1,\ldots,\ell\\}$ such that $\Phi[A_{i}]=A_{j}$.

###### Lemma 4.4

For every $j\in\\{s,\ldots n-1\\}$ we have that $\ell_{j}>1$ and every
$\Phi\in{\rm Aut}_{\cal D}(U)$ respects the partition ${\cal A}^{j}$ of
$D_{j}$. Moreover, for all $i,k\in\\{1,\ldots,\ell_{j}\\}$, we have
$\left|A_{i}^{j}\right|=\left|A_{k}^{j}\right|$.

Proof. Let $j\in\\{s,\ldots,n-1\\}$. Because $n\geq 3$ and
$\\{D_{1},\ldots,D_{n-1}\\}$ is a connected component of the graph ${\cal
O}(U,{\cal D})-D_{n}$, we have that $D_{j}$ is directly interdependent with
another $D_{j^{\prime}}$ with
$j^{\prime}\in\\{1,\ldots,n-1\\}\setminus\\{j\\}$. Consequently, $D_{j}$
itself is not a $U\setminus\bigcup_{i=n}^{m}D_{i}$-order-autonomous antichain.
Hence $\ell_{j}>1$.

Let $\Phi\in{\rm Aut}_{\cal D}(U)$. Because
$\Phi|_{U\setminus\bigcup_{i=n}^{m}D_{i}}\in{\rm Aut}_{{\cal
D}\setminus\\{D_{n},\ldots,D_{m}\\}}(U\setminus\bigcup_{i=n}^{m}D_{i})$, we
have $\Phi[D_{j}]=D_{j}$, and because automorphisms map maximal order-
autonomous antichains to maximal order-autonomous antichains, $\Phi$ must map
every $A_{i}^{j}$ to another $A_{k}^{j}$, that is, $\Phi$ respects ${\cal
A}^{j}$.

Because $(U,{\cal D})$ is tight, for any $i,k\in\\{1,\ldots,\ell_{j}\\}$,
there is a $\Phi\in{\rm Aut}_{\cal D}(U)$ such that
$\Phi\left(a_{i}^{j}\right)=a_{k}^{j}$. Consequently, because $\Phi$ respects
${\cal A}^{j}$, we have $\Phi\left[A_{i}^{j}\right]=A_{k}^{j}$, and hence
$\left|A_{i}^{j}\right|=\left|A_{k}^{j}\right|$.

###### Lemma 4.5

For all $j\in\\{t,\ldots,n-1\\}$, $i\in\\{1,\ldots,\ell_{j}\\}$ and distinct
$x,y\in A_{i}^{j}$, there is a $d\in D_{n}$ such that $d$ is comparable to one
of $x$ and $y$, but not the other.

Proof. Let $j\in\\{t,\ldots,n-1\\}$ and $i\in\\{1,\ldots,\ell_{j}\\}$. Because
$D_{j}$ is not directly interdependent with any $D_{k}$ with $k>n$, we have
that $A_{i}^{j}$ is order-autonomous in $U\setminus D_{n}$. Because, for any
distinct $x,y\in A_{i}^{j}$, the set $\\{x,y\\}$ is not order-autonomous in
$U$, there must be a $d\in D_{n}$ such that $d$ is comparable to one of $x$
and $y$, but not the other.

In our analysis, the order-autonomous antichains $A_{i}^{j}$ will be collapsed
into singletons. Hence we introduce the following and again establish some
natural properties.

###### Definition 4.6

We define the $D_{n}$-pruned and compacted ordered set
$U_{n}:=\bigcup_{i=1}^{s-1}D_{i}\cup\bigcup_{j=s}^{n-1}\left\\{a_{i}^{j}:i\in\\{1,\ldots,\ell_{j}\\}\right\\}$
and we define

$\displaystyle{\cal D}_{n}$ $\displaystyle:=$ $\displaystyle\\{D_{j}\cap
U_{n}:j\in\\{1,\ldots,n-1\\}\\}$ $\displaystyle=$
$\displaystyle\\{D_{j}:j\in\\{1,\ldots,s-1\\}\\}\cup\left\\{\left\\{a_{1}^{j},\ldots,a_{\ell_{j}}^{j}\right\\}:j\in\\{s,\ldots,n-1\\}\right\\}.$

For every $\Phi\in{\rm Aut}_{\cal D}(U)$, we define the function
$\Phi_{n}:U_{n}\to U_{n}$ by
$\Phi_{n}|_{\bigcup_{j=1}^{s-1}D_{j}}:=\Phi|_{\bigcup_{j=1}^{s-1}D_{j}}$, and
by, for any $j\in\\{s,\ldots,n-1\\}$ and $i\in\\{1,\ldots,\ell_{j}\\}$,
setting $\Phi_{n}\left(a_{i}^{j}\right)$ to be the unique element of
$\Phi\left[A_{i}^{j}\right]\cap U_{n}$.

###### Lemma 4.7

For every $\Phi\in{\rm Aut}_{\cal D}(U)$, we have that $\Phi_{n}\in{\rm
Aut}_{{\cal D}_{n}}(U_{n})$. Moreover, $(U_{n},{\cal D}_{n})$ is a tight
interdependent orbit union.

Proof. Clearly, ${\cal D}_{n}$ is a dictated orbit structure for $U_{n}$.

Because $\\{D_{1},\ldots,D_{n-1}\\}$ is a connected component of the graph
${\cal O}(U,{\cal D})-D_{n}$, by Lemma 4.5, $(U_{n},{\cal D}_{n})$ is a tight
interdependent orbit union.

Because $(U,{\cal D})$ is without slack and because we choose exactly one
element from each maximal $U\setminus\bigcup_{i=n}^{m}D_{i}$-order-autonomous
antichain to be in $U_{n}$, we obtain that $(U_{n},{\cal D}_{n})$ is an
interdependent orbit union without slack.

For any $\Phi\in{\rm Aut}_{\cal D}(U)$, it follows from the definitions that
$\Phi_{n}\in{\rm Aut}_{{\cal D}_{n}}(U_{n})$. Because, for any
$j\in\\{s,\ldots,n-1\\}$ and $x,y\in\\{1,\ldots,\ell_{j}\\}$, there is a
$\Phi\in{\rm Aut}_{\cal D}(U)$ with $\Phi\left[A_{x}^{j}\right]=A_{y}^{j}$, we
conclude that $(U_{n},{\cal D}_{n})$ is tight.

With the “early orbits” $D_{1},\ldots,D_{n-1}$ thus discussed, we now turn to
the remaining orbits $D_{n},\ldots,D_{m}$ as well as the connection between
$D_{n}$ and the sets $A_{i}^{j}$.

###### Definition 4.8

Let $Q:=\bigcup_{j=s}^{m}D_{j}$, let ${\cal
E}_{Q}:=\\{A_{i}^{j}:j=s,\ldots,n-1;i=1,\ldots,\ell_{j}\\}\cup\\{D_{j}:j=n,\ldots,m\\}$
and let ${\cal D}_{Q}$ be the set of all ${\cal E}_{Q}$-orbits.

###### Lemma 4.9

$(Q,{\cal D}_{Q})$ is a tight structured ordered set.

Proof. First note that, for $j\geq n$, all $D_{i}$ that are directly
interdependent with $D_{j}$ are contained in $\bigcup_{k=s}^{m}D_{k}=Q$.
Therefore, any $Q$-order-autonomous antichain in a set $D_{j}$ with $j\geq n$
would be $U$-order-autonomous. Hence for $j\geq n$, no $D_{j}$ contains a
nontrivial $Q$-order-autonomous antichain.

By Lemma 4.5, for $j\in\\{s,\ldots,n-1\\}$ and $i\in\\{1,\ldots,\ell_{j}\\}$,
no $A_{i}^{j}$ contains a nontrivial $Q$-order-autonomous antichain. We
conclude that $(Q,{\cal E}_{Q})$ is a structured ordered set without slack.
Because ${\cal D}_{Q}$ is the set of all ${\cal E}_{Q}$-orbits, we conclude
that $(Q,{\cal D}_{Q})$ is a tight structured ordered set.

$D_{n}$$D_{n}$$D_{n}$$D_{n}$$D_{n}$$D_{n}$$A_{1}^{n-1}$$A_{1}^{n-1}$$A_{1}^{n-1}$$A_{1}^{n-1}$$A_{1}^{n-1}$$A_{1}^{n-1}$$A_{2}^{n-1}$$A_{2}^{n-1}$$A_{2}^{n-1}$$A_{2}^{n-1}$$A_{2}^{n-1}$$A_{2}^{n-1}$$S_{4}^{\ddagger}$$S_{4}^{\dagger}$$S_{6}^{\ddagger}$$S_{6}^{\dagger}$$6C_{2}^{\ddagger}$$6C_{2}^{\dagger}$

Figure 3:  Structured ordered sets induced on $D_{n-1}\cup D_{n}$ with $n=m$
that are not interdependent orbit unions. The orbits are marked with ovals,
$D_{n}$ is marked with a dashed box, and the partition $A_{1}^{n-1}\cup
A_{2}^{n-1}$ is labeled.

Lemma 4.9 may feel a little unsatisfying compared to Lemma 4.7 in that
$(Q,{\cal D}_{Q})$ need not be an interdependent orbit union. However, Figure
3 gives examples that this really need not be the case: Any of the structured
ordered sets given there could be a structured ordered set $(Q,{\cal D}_{Q})$
in the case in which $m=n$, that is, $D_{n}$ is a pendant vertex, and
$|U_{n}\cap D_{n-1}|=2$

###### Definition 4.10

With $\Phi_{n}$ as in Definition 4.6, we define ${\rm Aut}_{{\cal
D}_{Q}}^{U}(Q):=\\{\Psi\in{\rm Aut}_{\cal D}(U):\Psi_{n}={\rm id}_{U_{n}}\\}$.
For every $\Delta\in{\rm Aut}_{{\cal D}_{Q}}(Q)$, we define $\Delta^{U}$ by

$\Delta^{U}(x):=\cases{\Delta(x);&if $x\in Q$,\cr x;&if $x\in U\setminus Q$.}$

###### Lemma 4.11

${\rm Aut}_{{\cal D}_{Q}}^{U}(Q)=\\{\Psi\in{\rm Aut}_{\cal D}(U):\Psi_{n}={\rm
id}_{U_{n}}\\}=\left\\{\Delta^{U}:\Delta\in{\rm Aut}_{{\cal
D}_{Q}}(Q)\right\\}$.

Proof. First note that, for every $\Delta\in{\rm Aut}_{{\cal D}_{Q}}(Q)$, the
fact that $\Delta$ fixes all sets $A_{i}^{j}$ implies that $\Delta^{U}\in{\rm
Aut}_{{\cal D}}(U)$ and that $\Delta^{U}_{n}={\rm id}_{U_{n}}$.

Conversely, if $\Psi\in{\rm Aut}_{\cal D}(U)$ satisfies $\Psi_{n}={\rm
id}_{U_{n}}$, then $\Psi$ maps every $A_{i}^{j}$ to itself. Hence
$\Psi|_{Q}\in{\rm Aut}_{{\cal D}_{Q}}(Q)$ and $\Psi=(\Psi|_{Q})^{U}$.

###### Theorem 4.12

The set ${\rm Aut}_{{\cal D}_{Q}}^{U}(Q)$ is a normal subgroup of ${\rm
Aut}_{\cal D}(U)$ and the factor group ${\rm Aut}_{\cal D}(U)/{\rm Aut}_{{\cal
D}_{Q}}^{U}(Q)$ is isomorphic to a subgroup of ${\rm Aut}_{{\cal
D}_{n}}(U_{n})$. Consequently $|{\rm Aut}_{{\cal D}}(U)|\leq|{\rm Aut}_{{\cal
D}_{n}}(U_{n})||{\rm Aut}_{{\cal D}_{Q}}(Q)|$.

Proof. First note that, because $\Phi_{n}\Psi_{n}=(\Phi\Psi)_{n}$ and
$(\Phi^{-1})_{n}=(\Phi_{n})^{-1}$, we have that ${\rm Aut}_{{\cal
D}_{Q}}^{U}(Q)$ is a subgroup of ${\rm Aut}_{\cal D}(U)$.

Via Lemma 4.11, let $\Delta^{U}\in{\rm Aut}_{{\cal D}_{Q}}^{U}(Q)$ and let
$\Phi\in{\rm Aut}_{\cal D}(U)$. Then
$\left(\Phi^{-1}\Delta^{U}\Phi\right)_{n}=\Phi^{-1}_{n}\Delta^{U}_{n}\Phi_{n}=\Phi^{-1}_{n}\Phi_{n}={\rm
id}_{U_{n}}$. Hence $\Phi^{-1}{\rm Aut}_{{\cal D}_{Q}}^{U}(Q)\Phi={\rm
Aut}_{{\cal D}_{Q}}^{U}(Q)$ and therefore ${\rm Aut}_{{\cal D}_{Q}}^{U}(Q)$ is
a normal subgroup of ${\rm Aut}_{\cal D}(U)$.

Moreover, for all $\Phi,\Psi\in{\rm Aut}_{\cal D}(U)$, we have $\Phi{\rm
Aut}_{{\cal D}_{Q}}^{U}(Q)=\Psi{\rm Aut}_{{\cal D}_{Q}}^{U}(Q)$ iff
$\Phi_{n}=\Psi_{n}$. Hence the factor group ${\rm Aut}_{\cal D}(U)/{\rm
Aut}_{{\cal D}_{Q}}^{U}(Q)$ is, via $\Phi{\rm Aut}_{{\cal
D}_{Q}}^{U}(Q)\mapsto\Phi_{n}$, isomorphic to a subgroup of ${\rm Aut}_{{\cal
D}_{n}}(U_{n})$. [The subgroup may be proper, because it can happen that not
all $\Psi\in{\rm Aut}_{{\cal D}_{n}}(U_{n})$ are equal to a $\Phi_{n}$ with
$\Phi\in{\rm Aut}_{\cal D}(U)$.] The inequality now follows.

###### Definition 4.13

The separation partition ${\cal S}(D_{n})$ of $D_{n}$ is the partition of
$D_{n}$ that is contained in ${\cal D}_{Q}$.

###### Lemma 4.14

Every $\Phi\in{\rm Aut}_{\cal D}(U)$ respects ${\cal D}_{Q}$. Every nontrivial
${\cal D}_{Q}$-orbit that is contained in a set $A_{i}^{j}$ is directly
interdependent with a ${\cal D}_{Q}$-orbit $S\in{\cal S}(D_{n})$. Every ${\cal
D}_{Q}$-interdependent orbit union that is contained in
$\bigcup_{j=s}^{n-1}D_{j}$ is a singleton.

Proof. Suppose, for a contradiction, there are a $\Phi\in{\rm Aut}_{\cal
D}(U)$ and an $S\in{\cal D}_{Q}$ such that $\Phi[S]\not\in{\cal D}_{Q}$. Then
$\Phi[S]$ intersects two distinct sets $B,C\in{\cal D}_{Q}$ or $\Phi[S]$ is
strictly contained in a set $D\in{\cal D}_{Q}$. Because we are free to work
with the inverse, it suffices to consider the case in which $\Phi[S]$
intersects two distinct sets $B,C\in{\cal D}_{Q}$. Because $S\in{\cal D}_{Q}$,
there is a $\Delta^{U}\in{\rm Aut}_{{\cal D}_{Q}}(Q)$ that maps a
$b\in\Phi^{-1}[B]\cap S$ to a $c\in\Phi^{-1}[C]\cap S$. Now $\Phi(b)\in B$,
$\Phi\Delta^{U}\Phi^{-1}\left(\Phi(b)\right)=\Phi(c)\in C$ and
$\Phi\Delta^{U}\Phi^{-1}|_{Q}\in{\rm Aut}_{{\cal D}_{Q}}(Q)$, a contradiction.
We thus conclude that every $\Phi\in{\rm Aut}_{\cal D}(U)$ respects ${\cal
D}_{Q}$.

Finally, by Lemma 4.5, any nontrivial ${\cal D}_{Q}$-orbit that is contained
in an $A_{i}^{j}$ is directly interdependent with an $S\in{\cal S}(D_{n})$.
Because no two distinct $A_{i}^{j}$ are directly interdependent and no
$A_{i}^{j}$ is directly interdependent with a $D_{k}$ with $k>n$, every ${\cal
D}_{Q}$-interdependent orbit union that is contained in
$\bigcup_{j=s}^{n-1}D_{j}$ must be a singleton.

##  5 Induction Preparation: Estimates for $(Q,{\cal D}_{Q})$

We now obtain the following generalization of Lemma 2.1.

###### Lemma 5.1

With notation as given so far, the following hold.

  1. 1.

If every $\Psi\in{\rm Aut}_{{\cal D}_{Q}}(Q)$ is uniquely determined by
$\Psi|_{D_{n}}$, then $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\min\left\\{(w(U)-1)!,\left(\left({|D_{n}|\over|{\cal
S}(D_{n})|}\right)!\right)^{|{\cal S}(D_{n})|}\right\\}$.

  2. 2.

If $n=m$, that is, if $D_{n}$ is not a cutvertex of ${\cal O}(U,{\cal D})$,
then $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\min\left\\{(w(U)-1)!,\left(\left({|D_{n}|\over|{\cal
S}(D_{n})|}\right)!\right)^{|{\cal
S}(D_{n})|},\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!\right\\}$.

  3. 3.

If $n=m$, that is, if $D_{n}$ is not a cutvertex of ${\cal O}(U,{\cal D})$,
and if, for all $j\in\\{s,\ldots,m-1\\}$ and $i\in\\{1,\ldots,\ell_{j}\\}$, we
have $|A_{i}^{j}|=1$, then $|{\rm Aut}_{{\cal D}}(U)|\leq|{\rm Aut}_{{\cal
D}_{m}}(U_{m})|$.

Proof. For part 1, note that, ${\rm Aut}_{{\cal D}_{Q}}(Q)$ induces at most
$\left(\left({|D_{n}|\over|{\cal S}(D_{n})|}\right)!\right)^{|{\cal
S}(D_{n})|}$ permutations on $D_{n}$. By hypothesis for this part, every
$\Phi\in{\rm Aut}_{{\cal D}_{Q}}(Q)$ is determined by its values on $D_{n}$,
hence $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq\left(\left({|D_{n}|\over|{\cal
S}(D_{n})|}\right)!\right)^{|{\cal S}(D_{n})|}$. Moreover, suppose, for a
contradiction, that ${\rm Aut}_{{\cal D}_{Q}}(Q)$ induces $>(w(U)-1)!$
permutations on $D_{n}$. Then, in case $w(U)\not=4$, $Q$ is max-locked. By
Lemma 2.11 (or directly for $w(U)=4$), this implies that all $|A_{i}^{j}|$ are
equal to $w(U)$ and then $U$ would contain an antichain with $2w(U)$ elements,
a contradiction.

For part 2, first note that, by Lemma 4.5, for all $\Phi\in{\rm Aut}_{{\cal
D}_{Q}}(Q)$, we have that $\Phi|_{D_{n}}$ determines all $\Phi|_{A_{i}^{j}}$,
which means we can apply part 1 to obtain the first two numbers in the minimum
on the right hand side. For the last number in the minimum on the right hand
side, note that, because any two distinct $x,y\in D_{m}$ satisfy $\\{p\in
P:p\sim x\\}\not=\\{p\in P:p\sim y\\}$ and all elements comparable to elements
in $D_{m}$ are in $\bigcup_{j=s}^{n-1}\bigcup_{i=1}^{\ell_{j}}A_{i}^{j}$, we
have that $\Phi|_{\bigcup_{j=s}^{n-1}\bigcup_{i=1}^{\ell_{j}}A_{i}^{j}}$
determines $\Phi|_{D_{m}}$.

Part 3 follows from part 2 and Theorem 4.12.

The idea for our induction proof is to add $(Q,{\cal D}_{Q})$ to $(U_{n},{\cal
D}_{n})$ to obtain the interdependent orbit union $(U,{\cal D})$. We could
(and will) work with insights from the induction hypothesis regarding
$(Q,{\cal D}_{Q})$ being $w(U)$-adequately bounded. However, one on hand,
these insights may not be available because $|{\cal D}_{Q}|$ is too large for
the induction hypothesis to apply. On the other hand, such an estimate may be
more than what is needed: $(U_{n},{\cal D}_{n})$ has
$\sum_{j=1}^{s-1}|D_{j}|+\sum_{j=s}^{n-1}\ell_{j}$ points and $n-1$ orbits,
$(U,{\cal D})$ has $\sum_{j=1}^{m}|D_{j}|$ points and $m$ orbits, and
$(Q,{\cal D}_{Q})$ has $\sum_{j=s}^{m}|D_{j}|$ points, but the number of
orbits is, at least to this author, not easy to determine. Because we
ultimately need an estimate for $(U,{\cal D})$, Definition 5.2 below is the
notion of boundedness we need for $(Q,{\cal D}_{Q})$, as Lemma 5.3 will
illustrate.

###### Definition 5.2

Let $q\in{\mathbb{Z}}$ and define $\ell_{Q}:=\sum_{j=s}^{n-1}\ell_{j}$ and

$T_{q}:=\left\lfloor{1\over
2}\left(\left(\sum_{j=n+1}^{m}|D_{j}|-(m-n)\right)+\left(|D_{n}|-{|{\cal
S}(D_{n})|}\right)+\left(\sum_{j=s}^{n-1}|D_{j}|-\ell_{Q}\right)+q\right)\right\rfloor.$

We will call $(Q,{\cal D}_{Q})$ induction $w$-adequately $q$-bounded iff there
are numbers $w_{1},\ldots,w_{M}\in\\{0,\ldots,w-1\\}$ such that $|{\rm
Aut}_{{\cal D}_{Q}}(Q)|\leq\prod_{j=1}^{M}w_{j}!$ and such that
$\sum_{j=1}^{M}w_{j}\leq T_{q}$. In cases in which $q\leq|{\cal S}(D_{n})|-1$
and the specific value of $q$ is immaterial, we will also say that $(Q,{\cal
D}_{Q})$ is induction $w$-adequately bounded.

###### Lemma 5.3

With notation as given so far, let $(U_{n},{\cal D}_{n})$ be offset by $o$
from being $w$-adequately bounded.

  1. 1.

If $|{\rm Aut}_{{\cal D}}(U)|\leq|{\rm Aut}_{{\cal D}_{n}}(U_{n})|$, then
$(U,{\cal D})$ is offset by $o-(|D_{n}|-1)$ from being $w$-adequately bounded.

  2. 2.

If $(Q,{\cal D}_{Q})$ is induction $w$-adequately $q$-bounded, then $(U,{\cal
D})$ is offset by $o+q-(|{\cal S}(D_{n})|-1)$ from being $w$-adequately
bounded.

In particular, if $(U_{n},{\cal D}_{n})$ is $w$-adequately bounded and
$(Q,{\cal D}_{Q})$ is induction $w$-adequately bounded, then $(U,{\cal D})$ is
$w$-adequately bounded.

Moreover, if $(U_{n},{\cal D}_{n})$ is offset by $1$ from being $w$-adequately
bounded and $(Q,{\cal D}_{Q})$ is induction $w$-adequately $(|{\cal
S}(D_{n})|-2)$-bounded, then $(U,{\cal D})$ is $w$-adequately bounded.

  3. 3.

If $o=1$, $(Q,{\cal D}_{Q})$ is induction $w$-adequately $(|{\cal
S}(D_{n})|-1)$-bounded, and
$\left(\sum_{j=n+1}^{m}|D_{j}|-(m-n)\right)+\left(|D_{n}|-1\right)+\left(\sum_{j=s}^{n-1}|D_{j}|-\ell_{Q}\right)$
is odd, then $(U,{\cal D})$ is $w$-adequately bounded.

Proof. Because $(U_{n},{\cal D}_{n})$ is offset by $o$ from being
$w$-adequately bounded, there are numbers $w_{i}\in\\{0,\ldots,w-1\\}$,
$i=1,\ldots,M$ such that $|{\rm Aut}_{{\cal
D}_{n}}(U_{n})|\leq\prod_{i=1}^{M}w_{i}!$ and
$\sum_{i=1}^{M}w_{i}\leq\left\lfloor{1\over 2}\left(|U_{n}|-|{\cal
D}_{n}|+o\right)\right\rfloor$. Now part 1 follows easily, because the size of
the set increases by $\sum_{i=n}^{m}|D_{i}|$ and the number of orbits
increases by $m-n+1$ as we go from $(U_{n},{\cal D}_{n})$ to $(U,{\cal D})$.

For part 2, because $(Q,{\cal D}_{Q})$ is induction $w$-adequately
$q$-bounded, there are numbers $w_{M+1},\ldots,w_{M+K}$ such that $|{\rm
Aut}_{{\cal D}_{Q}}(Q)|\leq\prod_{i=M+1}^{M+K}w_{i}!$ with
$w_{i}\in\\{0,\ldots,w-1\\}$ and $\sum_{j=M+1}^{M+K}w_{j}\leq T_{q}$.

By Theorem 4.12, we have

$|{\rm Aut}_{{\cal D}}(U)|\leq|{\rm Aut}_{{\cal D}_{n}}(U_{n})||{\rm
Aut}_{{\cal
D}_{Q}}(Q)|\leq\prod_{i=1}^{M}w_{i}!\prod_{i=M+1}^{M+K}w_{i}!=\prod_{i=1}^{M+K}w_{i}!,$

Because $|{\cal D}_{n}|=n-1$ and $|{\cal D}|=m$, the sum of the $w_{i}$ is
bounded as follows.

$\displaystyle\sum_{i=1}^{M+K}w_{i}=\sum_{i=1}^{M}w_{i}+\sum_{i=M+1}^{M+K}w_{i}$
$\displaystyle\leq$ $\displaystyle\left\lfloor{1\over 2}\left(|U_{n}|-|{\cal
D}_{n}|+o\right)\right\rfloor+\left\lfloor{1\over
2}\left(\sum_{i=n}^{m}|D_{i}|-(m-n+1)+\sum_{j=s}^{n-1}|D_{j}|-\ell_{Q}+q-(|{\cal
S}(D_{n})|-1)\right)\right\rfloor$ $\displaystyle\leq$
$\displaystyle\left\lfloor{1\over
2}\left(|U_{n}|+\sum_{j=s}^{n-1}|D_{j}|-\ell_{Q}+\sum_{i=n}^{m}|D_{i}|-(m-n+1)-(n-1)+o+q-(|{\cal
S}(D_{n})|-1)\right)\right\rfloor$ $\displaystyle=$
$\displaystyle\left\lfloor{1\over 2}\left(|U|-|{\cal D}|+o+q-(|{\cal
S}(D_{n})|-1)\right)\right\rfloor$

For part 3, $|{\rm Aut}_{{\cal D}}(U)|$ is bounded by the same product.
Because, for odd numbers $2k+1$, we have $\left\lfloor{1\over
2}(2k+1)\right\rfloor=\left\lfloor{1\over 2}(2k+1-1)\right\rfloor$, we obtain
the following.

$\displaystyle\sum_{i=1}^{M+K}w_{i}=\sum_{i=1}^{M}w_{i}+\sum_{i=M+1}^{M+K}w_{i}$
$\displaystyle\leq$ $\displaystyle\left\lfloor{1\over 2}\left(|U_{n}|-|{\cal
D}_{n}|+1\right)\right\rfloor+\left\lfloor{1\over
2}\left(\left(\sum_{j=n+1}^{m}|D_{j}|-(m-n)\right)+\left(|D_{n}|-1\right)+\left(\sum_{j=s}^{n-1}|D_{j}|-\ell_{Q}\right)-1\right)\right\rfloor$
$\displaystyle\leq$ $\displaystyle\left\lfloor{1\over
2}\left(|U_{n}|+\left(\sum_{i=n}^{m}|D_{i}|+\sum_{j=s}^{m-1}|D_{j}|-\ell_{Q}\right)-|{\cal
D}_{n}|-(m-n+1)\right)\right\rfloor$ $\displaystyle=$
$\displaystyle\left\lfloor{1\over 2}\left(|U|-|{\cal D}|\right)\right\rfloor.$

We conclude this section with some sufficient conditions for $(Q,{\cal
D}_{Q})$ being induction $w(U)$-adequately bounded.

###### Lemma 5.4

Let $(P,{\cal D})$ be a tight structured ordered set and let $C,D\in{\cal D}$
be so that $C\upharpoonleft_{\cal D}D$. Then $\gcd(|C|,|D|)>1$.

Proof. Because $(P,{\cal D})$ is tight, the automorphism group acts
transitively on $C$ and on $D$. Hence any two elements of $C$ have the same
number $1\leq u<|D|$ of upper bounds in $D$ and any two elements of $D$ have
the same number $1\leq\ell<|C|$ of lower bounds in $C$. Moreover,
$|C|u=|D|\ell$.

Suppose, for a contradiction, that $\gcd(|C|,|D|)=1$. Because $|C|$ is a
factor of $|D|\ell$, we have that $|C|$ must divide $\ell$, contradicting
$\ell<|C|$.

Similar to Definition 2.2, we define the following.

###### Definition 5.5

Let $(P,{\cal D})$ be a structured ordered set and let $D\in{\cal D}$. We
define $\alpha_{\cal D}(D):=|\\{\Phi|_{D}:\Phi\in{\rm Aut}_{\cal D}(P)\\}|$.

The goal throughout the following proofs, in which $n=m$, is to bound $|{\rm
Aut}_{{\cal D}_{Q}}(Q)|$ with a product of factorials such that the sum of the
individual numbers is less than or equal to $T_{q}={1\over
2}\left\lfloor\left(|D_{n}|-{|{\cal
S}(D_{n})|}\right)+\left(\sum_{j=s}^{n-1}|D_{j}|-\ell_{Q}\right)+q\right\rfloor.$
In many cases, $q$ will be equal to zero. Because
$|D_{j}|=\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|$, we will feel free to
switch between the two quantities, and the same holds true for
$\ell_{Q}=\sum_{j=s}^{n-1}\ell_{j}$.

###### Lemma 5.6

With notation as given so far, let $D_{n}$ not be a cutvertex of ${\cal
O}(U,{\cal D})$, $\sum_{j=t}^{n-1}\ell_{j}\geq 3$ and $|{\cal S}(D_{n})|=1$.
Then $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded.

Proof. By Lemma 4.5, we have $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq\alpha_{{\cal
D}_{Q}}(D_{n})$. By part 2 of Lemma 5.1, we have $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!$.
Because $|{\cal S}(D_{n})|=1$ there is no $\left|A_{i}^{j}\right|$ that is
equal to $1$.

Case 1: $\alpha_{{\cal D}_{Q}}(D_{n})>(|D_{n}|-1)!$. Clearly $|{\rm
Aut}_{{\cal D}_{Q}}(Q)|\leq\alpha_{{\cal D}_{Q}}(D_{n})\leq|D_{n}|!$. By Lemma
2.11 (or directly for $|D_{n}|=4$), there are a $j$ and distinct $i,k$ such
that $|A_{i}^{j}|\geq|D_{n}|$ and $|A_{k}^{j}|\geq|D_{n}|$. Hence $w(U)\geq
w(Q)\geq 2|D_{n}|$. Moreover, because $\sum_{j=t}^{n-1}\ell_{j}\geq 3$, there
is another set $A_{i^{\prime}}^{j^{\prime}}$ not equal to either of
$A_{i}^{j}$ and $A_{k}^{j}$ such that $|A_{i^{\prime}}^{j^{\prime}}|>1$. Now
$T_{0}\geq\left\lfloor{1\over
2}\left((|A_{i}^{j}|+|A_{k}^{j}|-2)+(|D_{n}|-1)+(|A_{i^{\prime}}^{j^{\prime}}|-1)\right)\right\rfloor\geq\left\lfloor{1\over
2}\left(3|D_{n}|-3+1\right)\right\rfloor=\left\lfloor{1\over
2}\left(2|D_{n}|+(|D_{n}|-2)\right)\right\rfloor\geq|D_{n}|$, proves that
$(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded.

Case 2: $\alpha_{{\cal D}_{Q}}(D_{n})\leq(|D_{n}|-1)!$.

Case 2.1:
$(|D_{n}|-1)\leq\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)$.
In this case $T_{0}\leq|D_{n}|-1$. Via $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\alpha_{{\cal D}_{Q}}(D_{n})\leq(|D_{n}|-1)!$, we obtain that
$(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded.

Case 2.2:
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)<(|D_{n}|-1)$,
and there is an $|A_{i}^{j}|$ that is not equal to $2$, or, if all
$|A_{i}^{j}|=2$, then $\sum_{j=s}^{n-1}\ell_{j}>3$. Because all cases in which
Lemma 2.7 cannot be applied are excluded, we obtain $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!\leq\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)!$.
Because
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)$
is smaller than $(|D_{n}|-1)\leq w(U)-1$ and less than or equal to $T_{0}$, we
obtain that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded.

Case 2.3:
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)<(|D_{n}|-1)$,
and all $|A_{i}^{j}|$ are equal to $2$ and $\sum_{j=s}^{n-1}\ell_{j}=3$. In
this case, we have $|A_{1}^{n-1}|=|A_{2}^{n-1}|=|A_{3}^{n-1}|=2$,
$|D_{n-1}|=6$ and
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)=3$.
Consequently $|D_{n}|>4$. By Lemma 5.4, the case $|D_{n}|=5$ does not occur,
Clearly, $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!=8<4!$,
and, because $|D_{n}|\geq 6$, we have $T_{0}\geq 4$, so $(Q,{\cal D}_{Q})$ is
induction $w(U)$-adequately bounded.

###### Lemma 5.7

With notation as given so far, let $D_{n}$ not be a cutvertex of ${\cal
O}(U,{\cal D})$ and let $\sum_{j=t}^{n-1}\ell_{j}\geq 3$. Then $(Q,{\cal
D}_{Q})$ is induction $w(U)$-adequately bounded.

Proof. By Lemma 5.6, we can assume that $|{\cal S}(D_{n})|>1$. In case
$T_{0}\geq w(U)-1$, using $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq(w(U)-1)!$, we
have that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded. Hence,
for the remainder of this proof, we can assume that $T_{0}<w(U)-1$.

Recall that, by part 2 of Lemma 5.1, we have

$|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\min\left\\{(w(U)-1)!,\left(\left({|D_{n}|\over|{\cal
S}(D_{n})|}\right)!\right)^{|{\cal
S}(D_{n})|},\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!\right\\}.$

Further, recall that $|A_{i}^{j}|>1$ iff $j\in\\{t,\ldots,n-1\\}$. Hence
$\sum_{j=s}^{t-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{t-1}\ell_{j}=0$
and $\prod_{j=s}^{t-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!=1$, that
is, this sum and product have no effect on the argument. To stay connected to
the definition of induction $w$-adequate boundedness, we will continue to
start all sums and products at $s$, but the estimates are all derived and
needed for the corresponding sums and products starting at $t$.

Case 1: $\sum_{j=t}^{n-1}\ell_{j}\geq 4$ or $\sum_{j=t}^{n-1}\ell_{j}=3$ and
one of the $\left|A_{i}^{n-1}\right|$ is not equal to $2$.

Case 1.1:
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)\leq\left(|D_{n}|-{|{\cal
S}(D_{n})|}\right)$. In case $\sum_{j=t}^{n-1}\ell_{j}=3$, we have $t=n-1$ and
then $|A_{1}^{n-1}|=|A_{2}^{n-1}|=|A_{3}^{n-1}|\not=2$. By Lemma 2.7, we
obtain
$\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!\leq\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)!$.
Now $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\prod_{j=s}^{n-1}\prod_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|!\leq\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)!$,
and, by assumption for this case,
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)$
is less than or equal to $T_{0}$ as well as less than or equal to
$\left(|D_{n}|-{|{\cal S}(D_{n})|}\right)\leq w(Q)-1$. Hence $(Q,{\cal
D}_{Q})$ is induction $w(Q)\leq w(U)$-adequately bounded.

In the remaining subcases, 1.2 and 1.3, because
$\left(\left({|D_{n}|\over|{\cal S}(D_{n})|}\right)!\right)^{|{\cal
S}(D_{n})|}\leq\left(|D_{n}|-{|{\cal S}(D_{n})|}+1\right)!$, we set
$H:=\min\left\\{(w(U)-1),\left(|D_{n}|-{|{\cal S}(D_{n})|}+1\right)\right\\}$,
and we have the inequality $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\min\left\\{(w(U)-1)!,\left(|D_{n}|-{|{\cal
S}(D_{n})|}+1\right)!\right\\}=H!$.

Case 1.2:
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)\geq\left(|D_{n}|-{|{\cal
S}(D_{n})|}+2\right)$. Because $H\leq\left(|D_{n}|-{|{\cal
S}(D_{n})|}+1\right)\leq T_{0}$, we obtain that $(Q,{\cal D}_{Q})$ is
induction $w(U)$-adequately bounded.

Case 1.3:
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)=\left(|D_{n}|-{|{\cal
S}(D_{n})|}+1\right)$. Because $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq H!$ and
$H\leq T_{1}$, we have that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
$1$-bounded. Because $|{\cal S}(D_{n})|>1$, this means that $(Q,{\cal D}_{Q})$
is induction $w(U)$-adequately bounded.

Case 2: $|A_{1}^{n-1}|=|A_{2}^{n-1}|=|A_{3}^{n-1}|=2$. In this case, we have
$|D_{n-1}|=6$. and
$\left(\sum_{j=s}^{n-1}\sum_{i=1}^{\ell_{j}}\left|A_{i}^{j}\right|-\sum_{j=s}^{n-1}\ell_{j}\right)=3$.

We first consider small sizes $|D_{n}|\leq 5$. Because $|{\cal S}(D_{n})|>1$,
the cases $|D_{n}|=3$ and $|D_{n}|=5$ do not occur, and the case $|D_{n}|=2$
leads to $|{\rm Aut}_{{\cal D}_{Q}}(Q)|=1$, which is trivial. This leaves the
case $|D_{n}|=4$, and there the only nontrivial case is $|{\cal S}(D_{n})|=2$.
Now $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq\alpha_{{\cal D}_{Q}}(D_{n})=4<3!$.
Because $T_{1}=3$, we conclude that $(Q,{\cal D}_{Q})$ is induction
$w(U)$-adequately bounded.

Finally, we consider $|D_{n}|\geq 6$. First note that $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\prod_{i=1}^{3}\left|A_{i}^{n-1}\right|=(2!)^{3}=8<4!$ and
$4<w(Q)-1\leq w(U)-1$. In case $\left(|D_{n}|-{|{\cal S}(D_{n})|}\right)\geq
5$, we have $T_{0}\geq 4$ and $(Q,{\cal D}_{Q})$ is induction
$w(U)$-adequately bounded. In case $\left(|D_{n}|-{|{\cal
S}(D_{n})|}\right)\leq 4$, because the sets in ${\cal S}(D_{n})$ all are of
the same size, we obtain $|D_{n}|\in\\{6,8\\}$.

For $|D_{n}|=8$, we obtain $|{\cal S}(D_{n})|=4$, and, for $|D_{n}|=6$, by
Lemma 5.4, we obtain $|{\cal S}(D_{n})|=3$. In either case, we have that
$T_{2}=4$, which proves that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
bounded.

By Lemma 4.4, the case $\sum_{j=t}^{n-1}\ell_{j}=1$ does not occur. This
leaves the case $\sum_{j=t}^{n-1}\ell_{j}=2$.

###### Lemma 5.8

With notation as given so far, let $D_{n}$ not be a cutvertex of ${\cal
O}(U,{\cal D})$, $\sum_{j=t}^{n-1}\ell_{j}=2$ and $|{\cal S}(D_{n})|\geq 3$.
Then $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded.

Proof. Because $\sum_{j=t}^{n-1}\ell_{j}=2$, we have $\ell_{n-1}=2$, that is,
${\cal A}^{n-1}=\\{A_{1}^{n-1},A_{2}^{n-1}\\}$.

Case 1:
$\left|A_{1}^{n-1}\right|+\left|A_{2}^{n-1}\right|-2\geq\left(|D_{n}|-{|{\cal
S}(D_{n})|}+1\right)$. In this case, $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\alpha_{\cal D}(D_{n})\leq\left(\left({|D_{n}|\over|{\cal
S}(D_{n})|}\right)!\right)^{|{\cal S}(D_{n})|}\leq(|D_{n}|-{|{\cal
S}(D_{n})|}+1)!$ and $|D_{n}|-{|{\cal S}(D_{n})|}+1$ is less than or equal to
$w(Q)-2\leq w(U)-1$ as well as less than or equal to $T_{1}$. Hence $(Q,{\cal
D}_{Q})$ is induction $w(U)$-adequately bounded.

Case 2:
$\left|A_{1}^{n-1}\right|+\left|A_{2}^{n-1}\right|-2\leq\left(|D_{n}|-{|{\cal
S}(D_{n})|}\right)$. In this case, $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\left|A_{1}^{n-1}\right|!\left|A_{2}^{n-1}\right|!\leq\left(\left|A_{1}^{n-1}\right|+\left|A_{2}^{n-1}\right|-1\right)!$
and $\left|A_{1}^{n-1}\right|+\left|A_{2}^{n-1}\right|-1\leq T_{0}+1\leq
T_{2}$. Hence $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded.

The only cases for which we have not yet proved that $(Q,{\cal D}_{Q})$ is
induction $w(U)$-adequately bounded are
$\sum_{j=t}^{n-1}\ell_{j}=2=\ell_{n-1}$ and $|{\cal S}(D_{n})|\leq 2$. The
case $\sum_{j=t}^{n-1}\ell_{j}=2=\ell_{n-1}$, $|{\cal S}(D_{n})|=1$, will
follow from the base step for $|{\cal D}|=3$ in Section 6. This leaves the
case $\sum_{j=t}^{n-1}\ell_{j}=2=\ell_{n-1}=|{\cal S}(D_{n})|$.

###### Lemma 5.9

With notation as given so far, let $D_{n}$ not be a cutvertex of ${\cal
O}(U,{\cal D})$, $\sum_{j=t}^{n-1}\ell_{j}=2=|{\cal S}(D_{n})|$ and
$|D_{n}|\not=|D_{n-1}|$. Then $(Q,{\cal D}_{Q})$ is induction
$w(U)$-adequately bounded.

Proof. Without loss of generality, assume that $|D_{n}|<|D_{n-1}|$. Because
$\sum_{j=t}^{n-1}\ell_{j}=2=|{\cal S}(D_{n})|$, we obtain
$|D_{n}|\leq|D_{n-1}|-2$. Now $|{\rm Aut}_{{\cal
D}_{Q}}(Q)|\leq\left({D_{n}\over 2}\right)!\left({D_{n}\over
2}\right)!\leq(|D_{n}|-1)!$ and $|D_{n}|-1=\left\lfloor{1\over
2}\left(|D_{n}|-2+|D_{n}|\right)\right\rfloor\leq\left\lfloor{1\over
2}\left(|D_{n}|-2+|D_{n-1}|-2\right)\right\rfloor=T_{0}$. Thus $(Q,{\cal
D}_{Q})$ is induction $w(U)$-adequately bounded.

###### Lemma 5.10

With notation as given so far, let $D_{n}$ not be a cutvertex of ${\cal
O}(U,{\cal D})$, $\sum_{j=t}^{n-1}\ell_{j}=2=|{\cal S}(D_{n})|$ and
$|D_{n}|=|D_{n-1}|\geq 8$. Then $(Q,{\cal D}_{Q})$ is induction
$w(U)$-adequately bounded.

Proof. By Lemma 2.7, $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq\left({D_{n}\over
2}\right)!\left({D_{n}\over 2}\right)!\leq(|D_{n}|-2)!$ and
$|D_{n}|-2=\left\lfloor{1\over
2}\left(|D_{n}|-2+|D_{n-1}|-2\right)\right\rfloor=T_{0}$. Thus $(Q,{\cal
D}_{Q})$ is induction $w(U)$-adequately bounded.

###### Lemma 5.11

With notation as given so far, let $D_{n}$ not be a cutvertex of ${\cal
O}(U,{\cal D})$, $\sum_{j=t}^{n-1}\ell_{j}\geq 2$, $|{\cal S}(D_{n})|\geq 2$,
let $(Q,{\cal D}_{Q})$ be not induction $w(U)$-adequately bounded and let
$(V,{\cal D}_{V})$ be the structured ordered subset that consists of all the
non-singleton interdependent orbit unions of $(Q,{\cal D}_{Q})$. Then
$\ell_{n-1}=|{\cal S}(D_{n})|=2$, $V=D_{n-1}\cup D_{n}$, and $(V,{\cal
D}_{V})$ is isomorphic or dually isomorphic to one of the structured ordered
sets $\left(S_{4}^{\dagger},{\cal D}_{S_{4}^{\dagger}}\right)$,
$\left(6C_{2}^{\dagger},{\cal D}_{6C_{2}^{\dagger}}\right)$,
$\left(S_{6}^{\dagger},{\cal D}_{S_{6}^{\dagger}}\right)$,
$\left(S_{4}^{\ddagger},{\cal D}_{S_{4}^{\ddagger}}\right)$,
$\left(6C_{2}^{\ddagger},{\cal D}_{6C_{2}^{\ddagger}}\right)$,
$\left(S_{6}^{\ddagger},{\cal D}_{S_{6}^{\ddagger}}\right)$ in Figure 3. In
particular, $V=D_{n-1}\cup D_{n}$ does not contain any order-autonomous
antichains.

Proof. Let $(Q,{\cal D}_{Q})$ be not induction $w(U)$-adequately bounded such
that $\sum_{j=t}^{n-1}\ell_{j}\geq 2$ and $|{\cal S}(D_{n})|\geq 2$. By Lemma
5.7, we have $\sum_{j=t}^{n-1}\ell_{j}=2$, that is, ${\cal
A}^{n-1}=\\{A_{1}^{n-1},A_{2}^{n-1}\\}$. By Lemma 5.8, we have $|{\cal
S}(D_{n})|=2$, that is, ${\cal
S}(D_{n})=\left\\{B_{1}^{n},B_{2}^{n}\right\\}$, and we also conclude
$(V,{\cal D}_{V})=(D_{n-1}\cup
D_{n},\\{A_{1}^{n-1},A_{2}^{n-1},B_{1}^{n},B_{2}^{n}\\})$. By Lemmas 5.9 and
5.10, we have $|D_{n-1}|=|D_{n}|<8$ and hence, because $|{\cal S}(D_{n})|=2$
and ${\cal S}(D_{n})$ must be nontrivial, $|D_{n-1}|=|D_{n}|\in\\{4,6\\}$.

Because no nontrivial ${\cal D}_{Q}$-orbit is order-autonomous in $Q$, without
loss of generality, we can assume that
$A_{1}^{n-1}\upharpoonleft\\!\downharpoonright_{\cal D}B_{1}^{n}$ and
$A_{2}^{n-1}\upharpoonleft\\!\downharpoonright_{\cal D}B_{2}^{n}$. The only
possibilities for two orbits with $2$ or $3$ elements each to be directly
interdependent are isomorphic to $2C_{2}$, $3C_{2}$ and the six crown
$C_{6}=S_{3}$. Hence, each $A_{i}^{n-1}\cup B_{i}^{n}$ must be isomorphic to
one of these sets. Because $(U,{\cal D})$ is tight and, by Lemma 4.14, the
${\cal D}$-automorphisms respect ${\cal S}(D_{n})$, $A_{1}^{n-1}\cup
B_{1}^{n}$ must be isomorphic to $A_{2}^{n-1}\cup B_{2}^{n}$

Any further direct interdependence
$A_{i}^{n-1}\upharpoonleft\\!\downharpoonright_{\cal D}B_{j}^{n}$ with
$i\not=j$ would induce $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq 2!$ in case
$|D_{n-1}|=|D_{n}|=4$, or, $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq 3!$ in case
$|D_{n-1}|=|D_{n}|=6$. In either case, $(Q,{\cal D}_{Q})$ would be induction
$w(U)$-adequately bounded. Thus there are no further direct interdependences
in $(V,{\cal D}_{V})$ and all possible combinations are listed in Figure 3.

##  6 Base Step: Forbidden Configurations

Clearly, Lemma 5.3 is the key building block to show, via an induction on
$|U|$, that “many” flexible tight interdependent orbit unions $(U,{\cal D})$
are $w(U)$-adequately bounded. Unlike in most induction proofs, for this
particular situation, the base step is a bit complex: There are a number of
flexible tight interdependent orbit unions $(U,{\cal D})$ with two or three
orbits which are not $w(U)$-adequately bounded. On the positive side, the
proofs in this section will show how these “forbidden configurations,” see
Definition 6.4 below for details, arise naturally, though annoyingly, via max-
locked ordered sets for which Lemma 3.13 does not provide the requisite bound,
and through the merging of an $8$-crown or an ordered set $S_{4}$ or $4C_{2}$
or $2V$ (see Definition 6.2 below) with the ordered set $2V$. The $8$-crown
arises naturally though Lemma 6.1 below.

###### Lemma 6.1

Let $(U,\\{B,T\\})$ be a flexible tight interdependent orbit union such that
the elements of $B$ are minimal and the elements of $T$ are maximal. If $U$ is
not an 8-crown, then $(U,\\{B,T\\})$ is $\max\\{|B|,|T|\\}$-adequately
bounded.

Proof. Without loss of generality, assume that $|B|\leq|T|$. Because $U$ is
without slack, by Lemma 2.1, $|{\rm
Aut}_{\\{B,T\\}}(U)|\leq\alpha_{\\{B,T\\}}(B)$.

Because $(U,\\{B,T\\})$ is tight, by Lemma 5.4, we have $\gcd(|B|,|T|)>1$.
Therefore, in case $|B|<|T|$, we have $|B|\leq|T|-2$. Now $|{\rm
Aut}_{\\{B,T\\}}(U)|\leq\alpha_{\\{B,T\\}}(B)\leq|B|!$ and
$|B|=\left\lfloor{1\over
2}\left(|B|+|B|\right)\right\rfloor\leq\left\lfloor{1\over
2}\left(|B|+|T|-2\right)\right\rfloor$.

This leaves the case $|B|=|T|$. First suppose, for a contradiction, that
$|B|=|T|=4$. Because $(U,\\{B,T\\})$ is tight, and because every element of
$T$ has at least one lower cover, there is a $c\in\\{1,2,3\\}$ such that every
element of $T$ has exactly $c$ lower covers and every element of $B$ has
exactly $c$ upper covers. If every element of $T$ had exactly one lower cover,
then $U$ would be a copy of $4C_{2}$, contradicting that $(U,\\{B,T\\})$ is
flexible. If every element of $T$ had exactly three lower covers, then,
because $(U,\\{B,T\\})$ is without slack, $U$ would be a copy of $S_{4}$,
again contradicting that $(U,\\{B,T\\})$ is flexible. Thus every element of
$T$ has two lower covers and every element of $B$ has two upper covers.
Because $U$ is not an $8$-crown, $U$ could only be the disjoint union of two
$4$-crowns, contradicting that $(U,\\{B,T\\})$ is without slack. Thus the case
$|B|=|T|=4$ does not occur.

This leaves the case $|B|=|T|\not=4$. Because $U$ is flexible, we have
$\alpha_{\\{B,T\\}}(B)\leq(|B|-1)!$. Hence $|{\rm
Aut}_{\\{B,T\\}}(U)|\leq(|B|-1)!$ and $|B|-1=\left\lfloor{1\over
2}\left(|B|+|T|-2\right)\right\rfloor$.

The $8$-crown $C_{8}$ has $8$ automorphisms, $8$ elements and $2$ natural
orbits, so it is offset by $4$ from being $w(C_{8})$-adequately bounded. By
Lemma 6.1, the $8$-crown $C_{8}$ with its natural dictated orbit structure
${\cal D}(C_{8})$ is the only flexible tight interdependent orbit union
$(U,{\cal D})$ with exactly $2$ dictated orbits that is not $w(U)$-adequately
bounded. For exactly three orbits, we need to define a few ordered sets.

###### Definition 6.2

(See Figure 4.) We define the following ordered sets with dictated orbit
structures.

  1. 1.

We define the ordered set $2C_{3}^{*}$ to be the set
$\\{b_{1},b_{2},m_{1},m_{2},t_{1},t_{2}\\}$ with the comparabilities
$b_{1}<m_{1}<t_{1}$, $b_{2}<m_{2}<t_{2}$, and $b_{1},b_{2}<t_{1},t_{2}$. We
define the dictated orbit structure ${\cal
D}\left(2C_{3}^{*}\right):=\big{\\{}\\{b_{1},b_{2}\\},\\{m_{1},m_{2}\\},\\{t_{1},t_{2}\\}\big{\\}}$.

  2. 2.

We define the ordered set $2V$ to be the set
$\left\\{b_{1},b_{2},t_{1}^{1},t_{2}^{1},t_{1}^{2},t_{2}^{2}\right\\}$ with
the comparabilities $b_{1}<t_{1}^{1},t_{2}^{1}$ and
$b_{2}<t_{1}^{2},t_{2}^{2}$. We define the dictated orbit structure ${\cal
D}(2V):=\left\\{\\{b_{1},b_{2}\\},\left\\{t_{1}^{1},t_{1}^{2}\right\\},\left\\{t_{2}^{1},t_{2}^{2}\right\\}\right\\}$.

  3. 3.

We define the ordered set $\widetilde{S_{4}}$ to be the set
$\\{b_{1},b_{2},b_{3},b_{4},m_{1},m_{2},t_{1},t_{2},t_{3},t_{4}\\}$ with the
comparabilities $b_{1},b_{2}<m_{2}<t_{3},t_{4}$,
$b_{3},b_{4}<m_{1}<t_{1},t_{2}$, $b_{1}<t_{2}$, $b_{2}<t_{1}$, $b_{3}<t_{4}$,
$b_{4}<t_{3}$, plus the comparabilities dictated by transitivity. Moreover, we
define the dictated orbit structure ${\cal
D}\left(\widetilde{S_{4}}\right):=\big{\\{}\\{b_{1},b_{2},b_{3},b_{4}\\},\\{m_{1},m_{2}\\},\\{t_{1},t_{2},t_{3},t_{4}\\}\big{\\}}$.

$2C_{3}^{*}$$2V$$\widetilde{S_{4}}$

Figure 4: The forbidden configurations from Definition 6.2. Dictated orbit
structures that are not equal to the natural one are indicated with ovals.

Next, we define a way to obtain ordered sets from smaller ordered sets by
attaching 2 points to generate an ordered set $2V$ within the new set.

###### Definition 6.3

(Also see Figure 5.) Let $Q\in\\{2V,4C_{2},S_{4},C_{8}\\}$, let $B$ be the set
of minimal elements of $Q$, let $T=\\{t_{1},t_{2},t_{3},t_{4}\\}$ be the set
of maximal elements of $Q$, labeled such that, in case $Q\in\\{2V,C_{8}\\}$,
$t_{1}$ and $t_{3}$ do not have a common lower bound and $t_{2}$ and $t_{4}$
do not have a common lower bound. Let $A=\\{a_{1},a_{2}\\}$ be a set of two
additional points that are not in $Q$.

  1. 1.

We define the ordered set $\widehat{Q}$ to be the ordered set obtained by
adding $a_{1}$ and $a_{2}$ to $Q$ such that $a_{1}$ is an upper bound of
$t_{1}$ and $t_{3}$ and such that $a_{2}$ is an upper bound of $t_{2}$ and
$t_{4}$. We define ${\cal D}\left(\widehat{Q}\right):=\\{B,T,A\\}$.

  2. 2.

We define the ordered set $\overline{Q}$ to be the ordered set obtained by
adding $a_{1}$ and $a_{2}$ to $Q$ such that $a_{1}$ is a lower bound of
$t_{1}$ and $t_{3}$ and such that $a_{2}$ is a lower bound of $t_{2}$ and
$t_{4}$. We define ${\cal D}\left(\overline{Q}\right):=\\{B,T,A\\}$.

$\overline{2V}$$\widehat{2V}$$\overline{4C_{2}}$$\widehat{4C_{2}}$$\overline{S_{4}}$$\widehat{S_{4}}$$\overline{C_{8}}$$\widehat{C_{8}}$

Figure 5: The forbidden configurations constructed from $2V$, $4C_{2}$,
$S_{4}$ and $C_{8}$ via Definition 6.3. Dictated orbit structures that are not
equal to the natural one are indicated with ovals. As a mnemonic aid: Hats
indicate a peaked roof, bars a flat one.

###### Definition 6.4

An interdependent orbit union $(U,{\cal D})$ will be called a forbidden
configuration iff $U$ is max-locked of height $1$ or if $(U,{\cal D})$ is
isomorphic or dually isomorphic to any of $\left(C_{8},{\cal
D}\left(C_{8}\right)\right)$, $\left(2C_{3},{\cal
D}\left(2C_{3}\right)\right)$, (see Figures 4 and 5 for the remaining sets)
$\left(2C_{3}^{*},{\cal D}\left(2C_{3}^{*}\right)\right)$, $\left(2V,{\cal
D}\left(2V\right)\right)$, $\left(\widehat{2V},{\cal
D}\left(\widehat{2V}\right)\right)$, $\left(\overline{2V},{\cal
D}\left(\overline{2V}\right)\right)$, $\left(\widehat{C_{8}},{\cal
D}\left(\widehat{C_{8}}\right)\right)$, $\left(\overline{C_{8}},{\cal
D}\left(\overline{C_{8}}\right)\right)$, $\left(\widehat{4C_{2}},{\cal
D}\left(\widehat{4C_{2}}\right)\right)$, $\left(\overline{4C_{2}},{\cal
D}\left(\overline{4C_{2}}\right)\right)$, $\left(\widehat{S_{4}},{\cal
D}\left(\widehat{S_{4}}\right)\right)$, $\left(\overline{S_{4}},{\cal
D}\left(\overline{S_{4}}\right)\right)$, $\left(\widetilde{S_{4}},{\cal
D}\left(\widetilde{S_{4}}\right)\right)$.

###### Lemma 6.5

Every forbidden configuration with $3$ dictated orbits is offset by $1$ from
being $5$-adequately bounded.

Proof. For $i\in\\{1,2,3\\}$, we say that $(U,{\cal D})$ is of type $i$ iff
$(U,{\cal D})$ has $2^{i}$ automorphisms and $4+2i$ points.

The ordered sets $\left(2C_{3},{\cal D}\left(2C_{3}\right)\right)$,
$\left(2C_{3}^{*},{\cal D}\left(2C_{3}^{*}\right)\right)$ and $(2V,{\cal
D}(2V))$ have $2$ automorphisms and $6$ elements;
$\left(\widetilde{S_{4}},{\cal D}\left(\widetilde{S_{4}}\right)\right)$ has
$8$ automorphisms and $10$ elements; $\left(\widehat{2V},{\cal
D}\left(\widehat{2V}\right)\right)$ and $\left(\overline{2V},{\cal
D}\left(\overline{2V}\right)\right)$ each have $4$ automorphisms and $8$
points.

For the remaining forbidden configurations $(U,{\cal D})$ with 3 dictated
orbits, note that each has $10$ points. Let the orbit with 2 elements be
$D_{3}$ and assume $D_{3}\upharpoonleft\\!\downharpoonright_{\cal D}D_{2}$.
Then $D_{3}\cup D_{2}$ is isomorphic to $2V$ or its dual, which, with its
natural automorphism structure, has $8$ automorphisms. Moreover, $D_{1}\cup
D_{2}$ is a set $C_{8}$, $S_{4}$ or $4C_{2}$, and in each case111In the case
of $C_{8}$, this is because of the way the two-element orbit was attached., we
obtain $|{\rm Aut}_{\cal D}(U)|=8$.

Thus, every forbidden configuration with $3$ dictated orbits is of type $i$
with $i\in\\{1,2,3\\}$. Now note that $2^{i}\leq(i+1)!$ and
$\left\lfloor{1\over 2}(4+2i-3+1)\right\rfloor=i+1$.

Our induction’s base step with ${\cal D}$ having 3 orbits, is Lemma 6.6 below.
Within its proof we will introduce further useful items that will be used
later.

###### Lemma 6.6

Let $(U,{\cal D})$ with ${\cal D}=\\{D_{1},D_{2},D_{3}\\}$ be a flexible tight
interdependent orbit union that is not a forbidden configuration. Then
$(U,{\cal D})$ is $\max\\{w(U),5\\}$-adequately bounded.

Proof. This proof consists of separately discussing the cases that there are
$\\{i,j,k\\}=\\{1,2,3\\}$ such that $|D_{i}|>|D_{j}|+|D_{k}|$, or, such that
$|D_{i}|=|D_{j}|+|D_{k}|$, or, $|D_{1}|=|D_{2}|=|D_{3}|=2$, or,
$|D_{i}|<|D_{j}|+|D_{k}|$ and not all three are equal to $2$. Cases and
subcases will be indicated in italics.

Case 1: There are $\\{i,j,k\\}=\\{1,2,3\\}$ such that
$|D_{i}|>|D_{j}|+|D_{k}|$. In this case, by Lemma 2.1, $|{\rm Aut}_{\cal
D}(U)|\leq|D_{j}|!|D_{k}|!\leq(|D_{j}|+|D_{k}|-1)!$. Moreover,
$\left\lfloor{1\over
2}(|D_{i}|+|D_{j}|+|D_{k}|-3))\right\rfloor\geq\left\lfloor{1\over
2}(2|D_{j}|+2|D_{k}|-2))\right\rfloor=|D_{j}|+|D_{k}|-1$. Hence, in this case,
$(U,{\cal D})$ is $w(U)$-adequately bounded.

Case 2. There are $\\{i,j,k\\}=\\{1,2,3\\}$ such that
$|D_{i}|=|D_{j}|+|D_{k}|$. In case $|{\rm Aut}_{\cal D}(U)|\leq(|D_{i}|-2)!$,
because $\left\lfloor{1\over
2}(|D_{1}|+|D_{2}|+|D_{3}|-3))\right\rfloor=\left\lfloor{1\over
2}(2|D_{i}|-3))\right\rfloor=|D_{i}|-2$, we obtain that $(U,{\cal D})$ is
$w(U)$-adequately bounded. Thus, for the remainder of this case, we can assume
that $|{\rm Aut}_{\cal D}(U)|>(|D_{i}|-2)!$. Because $|{\rm Aut}_{\cal
D}(U)|\leq|D_{j}|!|D_{k}|!$, by Lemma 2.7 and by symmetry, we only need to
consider the cases $(|D_{j}|,|D_{k}|)\in\\{(3,3),(3,4)\\}\cup\\{(2,n):n\geq
2\\}$. By Lemma 5.4, the case $(|D_{j}|,|D_{k}|)=(3,4)$, which leads to
$|D_{i}|=7$, does not occur, and, in the case $(|D_{j}|,|D_{k}|)=(2,n)$, $n$
must be even.

Because, for two directly interdependent tight orbits, any two elements of the
first orbit are comparable to the same number of elements of the second orbit,
the following definition is safe.

###### Definition 6.7

Let $(U,{\cal D})$ be a tight interdependent orbit union and let
$D_{a}\upharpoonleft\\!\downharpoonright_{\cal D}D_{b}$. We define $z_{a\to
b}$ to be the number of elements of $D_{b}$ that are comparable to an
individual element of $D_{a}$.

We will frequently use that $z_{a\to b}|D_{a}|=z_{b\to a}|D_{b}|$.

Case 2.1. $|D_{j}|=|D_{k}|=2$, $|D_{i}|=4$. First, we note that, if one of
$D_{j}$ or $D_{k}$ were not directly interdependent with $D_{k}$, then $D_{k}$
would contain two order-autonomous $2$-antichains, which cannot be. Thus
$D_{j},D_{k}\upharpoonleft\\!\downharpoonright_{\cal D}D_{i}$. Therefore, we
obtain that $z_{j\to i}=z_{k\to i}=2$ and $z_{i\to j}=z_{i\to k}=1$ and then,
because $D_{i}$ cannot contain any nontrivial order-autonomous antichains,
$(U,{\cal D})$ is isomorphic or dually isomorphic to one of
$\left(\widehat{2V},{\cal D}\left(\widehat{2V}\right)\right)$ and
$\left(\overline{2V},{\cal D}\left(\overline{2V}\right)\right)$.

Case 2.2. $|D_{j}|=2$, $|D_{k}|=n$, $n\geq 4$, $|D_{i}|=2+n$. Because the case
$|{\rm Aut}_{\cal D}(U)|\leq(|D_{i}|-2)!=n!$ has already been discussed, and
because $|{\rm Aut}_{\cal D}(U)|\leq\alpha_{\cal D}(D_{j})\alpha_{\cal
D}(D_{k})\leq 2!n!$, the only case that needs to be considered is
$\alpha_{\cal D}(D_{j})=2$ and $\alpha_{\cal D}(D_{k})=n!$. In this case,
$D_{k}\not\upharpoonleft\\!\downharpoonright_{\cal D}D_{j}$, and hence
$D_{k}\upharpoonleft\\!\downharpoonright_{\cal D}D_{i}$. Now $z_{i\to
k}\in\\{2,\ldots,|D_{k}|-2\\}$ and, because $\alpha_{\cal D}(D_{k})=n!$, we
conclude that $|D_{i}|\geq\pmatrix{n\cr z_{i\to k}\cr}\geq\pmatrix{n\cr
2\cr}={1\over 2}n(n-1)$. For $n>4$, we thus obtain that $\pmatrix{n\cr z_{i\to
k}\cr}>n+2$, which cannot be. For $n=4$, we have $z_{i\to k}=2$, and, for
every $\Phi\in{\rm Aut}_{\cal D}(U)$, $\Phi|_{D_{k}}$ determines first
$\Phi|_{D_{i}}$ and then $\Phi$ itself. Hence, in this case $|{\rm Aut}_{\cal
D}(U)|\leq|D_{k}|!=n!$, which was already discussed.

Case 2.3. $|D_{j}|=|D_{k}|=3$, $|D_{i}|=6$. Assume without loss of generality
that $D_{i}\upharpoonleft_{\cal D}D_{j}$. Independent of whether $z_{i\to
j}=1$ or $z_{i\to j}=2$, we have that $D_{i}$ consists of three $D_{i}\cup
D_{j}$-order-autonomous antichains $D_{i}^{1},D_{i}^{2},D_{i}^{3}$ with two
elements each. Because $D_{i}$ does not contain any nontrivial $D_{i}\cup
D_{j}\cup D_{k}$-order-autonomous subsets, we conclude that
$D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{k}$. Similar to the
preceding argument, $D_{i}$ consists of three $D_{i}\cup D_{k}$-order-
autonomous antichains with two elements each, such that each intersects
exactly two $D_{i}^{\ell}$. Therefore, for every $\Phi\in{\rm Aut}_{\cal
D}(U)$, the $3!$ ways that $\Phi$ could permute the $D_{i}^{\ell}$ as sets
determine $\Phi|_{D_{k}}$, which then determines how $\Phi$ maps every
$D_{i}^{\ell}$ to its image. Hence $|{\rm Aut}_{\cal D}(U)|\leq 3!$ and
$(U,{\cal D})$ is $w(U)$-adequately bounded.

Case 3: $|D_{1}|=|D_{2}|=|D_{3}|=2$. In this case, $(U,{\cal D})$ is one of
$\left(2C_{3},{\cal D}\left(2C_{3}\right)\right)$, $\left(2C_{3}^{*},{\cal
D}\left(2C_{3}^{*}\right)\right)$, and $\left(2V,{\cal
D}\left(2V\right)\right)$.

Case 4: For all $\\{i,j,k\\}=\\{1,2,3\\}$, we have $|D_{i}|<|D_{j}|+|D_{k}|$,
and there is a $z$ with $|D_{z}|>2$. First note that, for all
$i\in\\{1,2,3\\}$, we have $\left\lfloor{1\over
2}(|D_{1}|+|D_{2}|+|D_{3}|-3))\right\rfloor\geq\left\lfloor{1\over
2}(2|D_{i}|-2))\right\rfloor=|D_{i}|-1$. Hence, if $|{\rm Aut}_{\cal
D}(U)|\leq(|D_{i}|-1)!$, then $(U,{\cal D})$ is $w(U)$-adequately bounded. We
can assume $|{\rm Aut}_{\cal D}(U)|>(|D_{i}|-1)!$ for the remainder of this
case.

Via Lemma 5.4, it is not possible for two orbits to have two elements and the
third to have $3<2+2$ elements. Therefore, at most one orbit has $2$ elements.

Case 4.1: For all $\\{i,j,k\\}=\\{1,2,3\\}$ such that
$D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{j},D_{k}$, we have that
$D_{i}$ does not contain any nontrivial $D_{i}\cup D_{k}$\- or $D_{i}\cup
D_{k}$-order-autonomous antichains. In this case, for any $\Phi\in{\rm
Aut}_{\cal D}(U)$ and $D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{j}$,
the restriction $\Phi|_{D_{i}}$ determines $\Phi|_{D_{i}\cup D_{j}}$ which
determines $\Phi$. Hence ${\rm Aut}_{\cal D}(U)|\leq\min\\{\alpha_{\cal
D}(D_{1}),\alpha_{\cal D}(D_{2}),\alpha_{\cal D}(D_{3})\\}$. The case that
there is an $i$ such that $\alpha_{\cal D}(D_{i})\leq(|D_{i}|-1)!$ has already
been discussed. This leaves the case that, for all $i\in\\{1,2,3\\}$, we have
that $\alpha_{\cal D}(D_{i})>(|D_{i}|-1)!$. In case
$\max\\{|D_{1}|,|D_{2}|,|D_{3}|\\}\not=4$, this implies that $(U,{\cal D})$ is
max-locked, which was excluded. This leaves the case that
$\max\\{|D_{1}|,|D_{2}|,|D_{3}|\\}=4$. In this case, by Lemma 5.4, we first
conclude that two interdependent orbits have size $2$ or $4$, and then that
the third size $|D_{i}|$ cannot be equal to $3$ either. Because any $D_{i}\cup
D_{j}$ with $D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{j}$,
$|D_{i}|=2$ and $|D_{j}|=4$ contains nontrivial $D_{i}\cup D_{j}$-order-
autonomous antichains, the last case to consider is
$|D_{1}|=|D_{2}|=|D_{3}|=4$. In this case, ${\rm Aut}_{\cal D}(U)|\leq 4!$ and
$\left\lfloor{1\over
2}(|D_{1}|+|D_{2}|+|D_{3}|-3))\right\rfloor=\left\lfloor{1\over
2}(12-3))\right\rfloor=4$, and $(U,{\cal D})$ is $5$-adequately bounded.

###### Definition 6.8

Let $(P,{\cal D})$ be a structured ordered set and let $D_{j},D_{k}\in{\cal
D}$ be so that $D_{j}\upharpoonleft\\!\downharpoonright_{\cal D}D_{k}$. For
every $x\in D_{j}$, define $B_{x}^{k}:=\\{z\in D_{j}:\updownarrow
z\setminus(D_{k}\cup\\{z\\})=\updownarrow x\setminus(D_{k}\cup\\{x\\})\\}$. We
define the partition of $D_{j}$ induced by removal of $D_{k}$ to be ${\cal
B}^{j\setminus k}:=\left\\{B_{x}^{k}:x\in D_{j}\right\\}$. This partition is
called nontrivial iff it contains at least one set that is not the underlying
set and not a singleton.

Note that, clearly, every $\Phi\in{\rm Aut}_{\cal D}(P)$ respects every
partition ${\cal B}^{j\setminus k}$.

Case 4.2: There are $\\{i,j,k\\}=\\{1,2,3\\}$ such that
$D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{j},D_{k}$, such that
$D_{i}$ contains nontrivial $D_{i}\cup D_{k}$-order-autonomous antichains and
there is a $q\in\\{j,k\\}$ such that $D_{q}$ does not contain nontrivial
$D_{i}\cup D_{q}$-order-autonomous antichains. In this case, because
$D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{q}$, for any $\Phi\in{\rm
Aut}_{\cal D}(U)$, the restriction $\Phi|_{D_{i}}$ determines
$\Phi|_{D_{i}\cup D_{q}}$ which determines $\Phi$, and hence we have that
$|{\rm Aut}_{\cal D}(U)|\leq\alpha_{\cal D}(D_{i})$. By Lemma 2.8, because
every $\Phi\in{\rm Aut}_{\cal D}(U)$ respects ${\cal B}^{i\setminus j}$, for
$|D_{i}|\geq 6$, we obtain $|{\rm Aut}_{\cal D}(U)|\leq\alpha_{\cal
D}(D_{i})\leq(|D_{i}|-1)!$, which has already been discussed. Hence
$|D_{i}|<6$. Because $D_{i}$ can be partitioned nontrivially into sets of
pairwise equal sizes, we obtain that $|D_{i}|$ cannot be prime. Hence
$|D_{i}|=4$.

Because the case $|{\rm Aut}_{\cal D}(U)|\leq(|D_{i}|-1)!$ has already been
treated, we can assume that $3!<|{\rm Aut}_{\cal D}(U)|\leq\alpha_{\cal
D}(D_{i})\leq 4!$. In case $|U|\geq 11$, we obtain $\left\lfloor{1\over
2}(|D_{1}|+|D_{2}|+|D_{3}|-3))\right\rfloor\geq\left\lfloor{1\over 2}\cdot
8\right\rfloor=4$ and $(U,{\cal D})$ is $5$-adequately bounded. This leaves
the case $|U|\leq 10$. In this case, by Lemma 5.4, both $|D_{j}|$ and
$|D_{k}|$ are even and because at most one of them could be equal to $2$, we
can assume without loss of generality that $|D_{j}|=4$ and $|D_{k}|=2$. Now
$D_{i}\cup D_{k}$ must be isomorphic to $2V$ or its dual. In case $z_{i\to
j}=z_{j\to i}=1$, $D_{i}\cup D_{j}$ must be isomorphic to $4C_{2}$. Because
$D_{j}$ does not contain any nontrivial $D_{i}\cup D_{j}$-order-autonomous
antichains, in case $z_{i\to j}=z_{j\to i}=2$, $D_{i}\cup D_{j}$ must be
isomorphic to $C_{8}$. In case $z_{i\to j}=z_{j\to i}=3$, $D_{i}\cup D_{j}$
must be isomorphic to $S_{4}$. Therefore, $D_{i}\cup D_{j}$ must be isomorphic
to $C_{8}$, $S_{4}$ or $4C_{2}$. Now $(U,{\cal D})$ must be isomorphic to
$\left(\widehat{D_{i}\cup D_{j}},{\cal D}\left(\widehat{D_{i}\cup
D_{j}}\right)\right)$, $\left(\overline{D_{i}\cup D_{j}},{\cal
D}\left(\overline{D_{i}\cup D_{j}}\right)\right)$, one of their duals, or, in
case $D_{i}\cup D_{j}$ is isomorphic to $S_{4}$, to
$\left(\widetilde{S_{4}},{\cal D}\left(\widetilde{S_{4}}\right)\right)$, all
of which are forbidden configurations.

Case 4.3. There are $\\{i,j,k\\}=\\{1,2,3\\}$ such that
$D_{i}\upharpoonleft\\!\downharpoonright_{\cal D}D_{j},D_{k}$, we have that
$D_{i}$ and $D_{k}$ contain nontrivial $D_{i}\cup D_{k}$-order-autonomous
antichains and $D_{j}$ contains nontrivial $D_{i}\cup D_{j}$-order-autonomous
antichains. In this case, we must have that
$D_{j}\upharpoonleft\\!\downharpoonright_{\cal D}D_{k}$, and then, by symmetry
and Case 4.2, we can assume that, for all distinct $i,j\in\\{1,2,3\\}$, we
have that both $D_{i}$ and $D_{j}$ contain nontrivial $D_{i}\cup D_{j}$-order-
autonomous antichains.

The notation in Section 4, with the removed orbits being the ones with the
highest indices, is convenient to state the results so far. However, in
symmetric situations, as we encounter here and, later, in Lemma 7.2, we may
need to remove a noncutvertex $D_{k}$ of ${\cal O}(U,{\cal D})$ that does not
have the highest index. To handle such situations, we introduce the following
notation.

###### Definition 6.9

With notation as in Section 4, let $k\leq m$ and let $D_{k}$ be a noncutvertex
of ${\cal O}(U,{\cal D})$. We define $(U^{k},{\cal D}^{k})$ and $(Q^{k},{\cal
D}_{Q^{k}})$ to be the ordered sets as constructed in Section 4 with $D_{k}$
in the place of $D_{m}$ and vice versa. All corresponding quantities will
carry a superscript $k$.

For $\\{i,j,k\\}=\\{1,2,3\\}$, because $\ell_{i}^{k}+\ell_{j}^{k}\geq 4$, by
Lemma 5.7, we have that $(Q^{k},{\cal D}_{Q^{k}})$ is induction
$w(U)$-adequately bounded. Thus, by Lemma 6.1 and by part 2 of Lemma 5.3, the
only case left to consider is if every $(U^{k},{\cal D}^{k})$ is an $8$-crown
or max-locked, that is, a set $pC_{2}$ or a set $S_{p}$. This means that, for
any $\\{i,j,k\\}=\\{1,2,3\\}$, we have $|{\cal B}^{i\setminus k}|=|{\cal
B}^{j\setminus k}|$ because each is the number of minimal or maximal elements
of $U^{k}$.

Without loss of generality, we can assume that $|D_{3}|\leq|D_{2}|,|D_{1}|$.

Suppose, for a contradiction, that $|D_{3}|=4$. Then $|{\cal B}^{2\setminus
1}|=|{\cal B}^{3\setminus 1}|=2$ and $|{\cal B}^{1\setminus 2}|=|{\cal
B}^{3\setminus 2}|=2$. Because any two of our three sets are directly
interdependent, one of $D_{1}$ and $D_{2}$ is the set of maximal elements or
the set of minimal elements. By duality and because the sizes of $D_{1}$ and
$D_{2}$ are immaterial for the argument, without loss of generality, we can
assume that $D_{1}$ is the set of maximal elements of $U$. Because $(U,{\cal
D})$ is tight, and because ${\cal B}^{2\setminus 1}$ and ${\cal B}^{3\setminus
1}$ are nontrivial, no element $x\in D_{1}$ is above all minimal elements or
above all but one minimal element. Because ${\cal B}^{3\setminus 2}$ is not
trivial, every $x\in D_{1}$ is above at least two elements of $D_{3}$. Because
${\cal B}^{3\setminus 2}\not={\cal B}^{3\setminus 1}$, every $x\in D_{1}$ is
above two elements in different sets of ${\cal B}^{3\setminus 1}$.

Let $x\in D_{1}$. In case $D_{2}\upharpoonleft_{\cal
D}D_{3}\upharpoonleft_{\cal D}D_{1}$, because $x$ is above two elements in
different sets of ${\cal B}^{3\setminus 1}$ and $|{\cal B}^{3\setminus
1}|=2=|{\cal B}^{2\setminus 1}|$, we obtain $x>D_{2}$, a contradiction. Thus
$D_{3}\upharpoonleft_{\cal D}D_{2}\upharpoonleft_{\cal D}D_{1}$ and $D_{3}$ is
the set of minimal elements of $U$. Because $x$ is above some element in
$D_{2}$, it is also above at least one whole set in ${\cal B}^{3\setminus 1}$.
Because $x$ is above at least one element in another set of ${\cal
B}^{3\setminus 1}$, we conclude that $x$ is above at least $3$ of the $4$
minimal elements of $U$, a contradiction.

Because $D_{3}$ has a nontrivial partition, $|D_{3}|$ cannot be a prime
number. Thus $|D_{3}|\geq 6$.

Note that, for $j\in\\{1,2\\}$, we have $|{\rm Aut}_{\cal
D}(U)|\leq\alpha_{\cal D}(D_{3})|{\cal B}^{j\setminus 3}|!$. Because
$|D_{3}|\geq 6$, by Lemma 2.8, because ${\cal B}^{3\setminus 1}$ is not
trivial, we have $\alpha_{\cal D}(D_{3})\leq(|D_{3}|-1)!$. Moreover, $|{\cal
B}^{j\setminus 3}|\leq{|D_{j}|\over 2}$. Hence, trivially, $|{\cal
B}^{j\setminus 3}|\leq{|D_{j}|\over a}$ with $a\in\\{2,3\\}$, and
$\alpha_{\cal D}(D_{3})\leq(|D_{3}|-b)!$ with $b\in\\{1,2\\}$. For $a=3$ or
$b=2$ or $|D_{3}|<|D_{1}|$ (and $j=2$, $k=1$), we have the following for
$\\{j,k\\}=\\{1,2\\}$, $a\in\\{2,3\\}$ and $b\in\\{1,2\\}$.

$\displaystyle|D_{3}|-2b$ $\displaystyle\leq$
$\displaystyle|D_{k}|-3+\left(1-{2\over a}\right)|D_{j}|$
$\displaystyle{1\over 2}|D_{3}|-b$ $\displaystyle\leq$ $\displaystyle{1\over
2}(|D_{k}|-3)+\left({1\over 2}-{1\over a}\right)|D_{j}|$
$\displaystyle{|D_{j}|\over a}+|D_{3}|-b$ $\displaystyle\leq$
$\displaystyle{1\over 2}(|D_{1}|+|D_{2}|+|D_{3}|-3)$
$\displaystyle\left\lceil{|D_{j}|\over a}\right\rceil+|D_{3}|-b$
$\displaystyle\leq$ $\displaystyle\left\lfloor{1\over
2}(|D_{1}|+|D_{2}|+|D_{3}|-3)\right\rfloor$

Hence, in all these cases, $(U,{\cal D})$ is $w(U)$-adequately bounded, and we
are left with the case that $|D_{1}|=|D_{2}|=|D_{3}|\geq 6$ and $|{\cal
B}^{j\setminus 3}|>{|D_{j}|\over 3}$, that is, $|{\cal B}^{j\setminus
3}|={|D_{j}|\over 2}$. By symmetry, we can assume that all $|{\cal
B}^{j\setminus k}|={|D_{j}|\over 2}$.

In case $|D_{j}|\geq 8$, we obtain $\alpha_{\cal
D}(D_{3})\leq\left({|D_{3}|\over 2}\right)!2^{|D_{3}|\over 2}\leq(|D_{3}|-2)!$
and, by the above with $b=2$, $(U,{\cal D})$ is $w(U)$-adequately bounded.

Finally, suppose, for a contradiction, that $|D_{1}|=|D_{2}|=|D_{3}|=6$ and
all ${\cal B}^{i\setminus j}$ partition $D_{i}$ into doubletons. Without loss
of generality, assume that $D_{3}\upharpoonleft_{\cal
D}D_{2}\upharpoonleft_{\cal D}D_{1}$. Because ${\cal B}^{3\setminus 2}$ is
nontrivial, no element $x\in D_{1}$ is above $5$ or more elements of $D_{3}$.
Let $x\in D_{1}$. Because every set in ${\cal B}^{2\setminus 3}$ is a
doubleton, $x$ is above at least two elements of $D_{2}$. Because no set of
${\cal B}^{2\setminus 3}$ is contained in a set of ${\cal B}^{2\setminus 1}$,
these two elements must be in different sets of ${\cal B}^{2\setminus 1}$.
Hence $x$ is above at least 2 different sets of ${\cal B}^{3\setminus 1}$,
which means $x$ is above at least 4 elements of $D_{3}$. Because ${\cal
B}^{3\setminus 2}\not={\cal B}^{3\setminus 1}$, $x$ must be above exactly one
more element of $D_{1}$. However, then $x$ is above $5$ elements of $D_{1}$, a
contradiction.

This concludes the proof of Lemma 6.6.

##  7 Induction Step: Bounding the Number of Automorphisms in Non-Max-Locked
Interdependent Orbit Unions

As in Section 4, $(U,{\cal D})$ is a flexible tight interdependent orbit
union, but with $|{\cal D}|\geq 4$. The idea for the proof of Theorem 7.4
below is an induction in which we obtain estimates of $|{\rm Aut}_{\cal
D}(U)|$ by applying Theorem 4.12, Lemma 5.3 and Lemma 5.11 to a noncutvertex
$D_{m}$ of the orbit graph ${\cal O}(U,{\cal D})$ and the resulting ordered
sets $(U_{m},{\cal D}_{m})$ and $(Q,{\cal D}_{Q})$.

By part 2 of Lemma 5.3, when $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
bounded and $(U_{n},{\cal D}_{n})$ is $\max\\{w(U),5\\}$-adequately bounded,
then $(U,{\cal D})$ is $\max\\{w(U),5\\}$-adequately bounded. Hence, our last
obstacle for the induction proof of Theorem 7.4 below, are sets $(Q,{\cal
D}_{Q})$ that are not induction $w(U)$-adequately bounded and forbidden
configurations $(U_{n},{\cal D}_{n})$. Lemma 5.11 and Lemma 7.1 below show
that there are very few sets $(Q,{\cal D}_{Q})$ that are not induction
$w(U)$-adequately bounded.

###### Lemma 7.1

With notation as in Section 4, if $D_{m}$ is not a cutvertex of ${\cal
O}(U,{\cal D})$ and $(Q,{\cal D}_{Q})$ is not induction $w(U)$-adequately
bounded with $\sum_{j=t}^{m-1}\ell_{j}=2$ and $|{\cal S}(D_{m})|=1$, then
$|D_{m-1}|=4$, and $(Q,{\cal D}_{Q})$ is isomorphic to $(2V,{\cal D}(2V))$, or
$\left(\overline{2V},{\cal D}\left(\overline{2V}\right)\right)$, or one of
their duals. Moreover, $D_{m}$ is a pendant vertex of ${\cal O}(U,{\cal D})$.

Proof. By Lemma 6.6 and because $(Q,{\cal D}_{Q})$ being $w(U)$-adequately
bounded implies that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
bounded, $(Q,{\cal D}_{Q})$ must be a forbidden configuration. Because the
${\cal D}_{Q}$-orbits $A_{1}^{m-1}$ and $A_{2}^{m-1}$ are not directly
interdependent, the orbit graph ${\cal O}(Q,{\cal D}_{Q})$ must be a path with
$3$ vertices, and, because $A_{1}^{m-1},A_{2}^{m-1}\subseteq D_{m-1}$, the
endvertices must have the same number of elements and their union must be an
antichain, too. Now $(Q,{\cal D}_{Q})$ is isomorphic to $(2V,{\cal D}(2V))$,
$\left(\overline{2V},{\cal D}\left(\overline{2V}\right)\right)$ or one of
their duals, because these are the only forbidden configurations whose orbit
graph is a path whose endvertices are antichains of the same size whose union
is an antichain, too.

Finally, because ${\cal S}(D_{m})=1$, there are no singleton sets $A_{i}^{j}$,
which means that $D_{m-1}$ is the only orbit that is directly interdependent
with $D_{m}$, that is, $D_{m}$ is a pendant vertex of ${\cal O}(U,{\cal D})$.

###### Lemma 7.2

With notation as in Section 4, if $D_{m}$ is not a cutvertex of ${\cal
O}(U,{\cal D})$, $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately bounded,
and $(U_{m},{\cal D}_{m})$ is a forbidden configuration with $|{\cal
D}_{m}|=3$, then $(U,{\cal D})$ is $\max\\{w(U),5\\}$-adequately bounded.

Proof. Clearly, $m=4$. By Lemma 6.5, every forbidden configuration with $3$
orbits is offset by $1$ from being $5$-adequately bounded. Therefore, by Lemma
5.3, we obtain that $(U,{\cal D})$ is $\max\\{w(U),5\\}$-adequately bounded in
case $|{\rm Aut}_{{\cal D}}(U)|\leq|{\rm Aut}_{{\cal D}_{4}}(U_{4})|$, in case
$(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately $({\cal
S}(D_{4})-2)$-bounded, and in case $(Q,{\cal D}_{Q})$ is induction
$w(U)$-adequately $({\cal S}(D_{4})-1)$-bounded and
$\left(|D_{4}|-1\right)+\left(\sum_{j=s}^{3}|D_{j}|-\ell_{Q}\right)$ is odd.

This leaves us the case that $|{\rm Aut}_{{\cal D}}(U)|>|{\rm Aut}_{{\cal
D}_{4}}(U_{4})|$, $(Q,{\cal D}_{Q})$ is not induction $w(U)$-adequately
$({\cal S}(D_{4})-2)$-bounded, which means that $(Q,{\cal D}_{Q})$ is
induction $w(U)$-adequately $({\cal S}(D_{4})-1)$-bounded, and
$\left(|D_{4}|-1\right)+\left(\sum_{j=s}^{3}|D_{j}|-\ell_{Q}\right)$ is even.
Because every orbit in a forbidden configuration with $3$ orbits has an even
number of at most $4$ elements, all $\ell_{j}$ are even. Moreover, because
$|U_{4}|\leq 10$, we have
$\ell_{Q}=\sum_{j=s}^{n-1}\ell_{j}\in\\{2,4,6,8,10\\}$. Finally, because
$\left(|D_{4}|-1\right)+\left(\sum_{j=s}^{3}|D_{j}|-\ell_{Q}\right)$ is even,
we obtain that $|D_{4}|$ is odd.

Without loss of generality, we can assume that $D_{1}$ is not a cutvertex of
${\cal O}(U,{\cal D})$. Let $(U^{1},{\cal D}^{1})$ be the ordered set we
obtain through removal of $D_{1}$ as in Theorem 4.12. Then $|{\cal D}^{1}|=3$.
Because $|D_{4}|$ is odd and can therefore only split into an odd number of
orbits, ${\cal D}^{1}$ contains an orbit with an odd number of elements, which
means that $(U^{1},{\cal D}^{1})$ is not a forbidden configuration. Hence, by
Lemma 6.6, $(U^{1},{\cal D}^{1})$ is $\max\\{w(U),5\\}$-adequately bounded. If
the ordered set $(Q^{1},{\cal D}_{Q^{1}})$, obtained through removal of
$D_{1}$ as in Theorem 4.12, is induction $w(U)$-adequately bounded, then, by
part 2 of Lemma 5.3, $(U,{\cal D})$ is $\max\\{w(U),5\\}$-adequately bounded.

We are left to consider the case that $(Q^{1},{\cal D}_{Q^{1}})$ is not
induction $w(U)$-adequately bounded. By Lemmas 5.11 and 7.1, we have that
$|D_{1}|\in\\{2,4,6\\}$. Because $|D_{4}|$ is odd, by Lemma 5.4, $D_{1}$ is
not directly interdependent with $D_{4}$. Let $k\in\\{2,3\\}$ be so that
$D_{1}\upharpoonleft\\!\downharpoonright_{\cal D}D_{k}$ and $D_{k}$ contains
nontrivial order-autonomous antichains induced by the removal of $D_{1}$. In
case $|D_{1}|=6$, by Lemma 5.11, we would obtain $|D_{k}|=6$ and that no
subset of $D_{1}\cup D_{k}$ would be an order-autonomous antichain in
$U\setminus D_{4}$. This would mean that $(U_{4},{\cal D}_{4})$ contains
orbits of size $6$, contradicting the fact that $(U_{4},{\cal D}_{4})$ is a
forbidden configuration. Hence, $|D_{1}|\in\\{2,4\\}$.

By Lemmas 5.11 and 7.1, the orbit $D_{k}$ has $4$ elements. Because $|D_{4}|$
is odd, by Lemma 5.4, $D_{4}$ is not directly interdependent with $D_{k}$.
Because (standard assumption for Section 4)
$D_{4}\upharpoonleft\\!\downharpoonright_{\cal D}D_{3}$, we obtain $k=2$,
$|D_{2}|=4$, and $D_{4}$ is not directly interdependent with either of $D_{1}$
and $D_{2}$. Because removal of $D_{1}$ also produces an interdependent orbit
union, we conclude that $D_{2}\upharpoonleft\\!\downharpoonright_{\cal
D}D_{3}$. In particular, by Lemma 5.4, $|D_{3}|$ is even.

The only way removal of $D_{1}$ can induce nontrivial $U\setminus
D_{1}$-order-autonomous antichains in $D_{2}$ is when $D_{2}$ contains
$D_{2}\cup D_{3}$-order-autonomous antichains. Because the existence of
$D_{2}\cup D_{3}$-order-autonomous antichains in $D_{2}$ only depends on
$D_{3}\cap U_{4}$, and because $U_{4}$ is a forbidden configuration, by Lemma
6.6 and inspection of Figures 4 and 5, we see that this is only possible when
$|D_{3}\cap U_{4}|=2$. Hence $\sum_{j=t}^{3}\ell_{j}=2$. Note that this means
that, to establish that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
$({\cal S}(D_{4})-2)$-bounded, the sum of the bounding factorials would need
to be bounded by $\left\lfloor{1\over 2}(|D_{3}|+|D_{4}|-4)\right\rfloor$.

Again by Lemma 5.4, there are odd numbers $b,c$ with $b>1$ and an even number
$e$ such that $|D_{3}|=eb$ and $|D_{4}|=cb$. Because every $\Phi\in{\rm
Aut}_{{\cal D}_{Q}}(Q)$ is determined by its restriction to $D_{3}$ and
respects the partition into $A_{1}^{3}$ and $A_{2}^{3}$, $c\geq e+1$ would
imply $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq\left({e\over 2}b\right)!\left({e\over
2}b\right)!<(eb-1)!$ and $\left\lfloor{1\over
2}(eb+cb-4)\right\rfloor\geq\left\lfloor{1\over
2}((e+c)b-4)\right\rfloor\geq\left\lfloor eb+{b\over 2}-2\right\rfloor\geq
eb-1$, which would mean that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
$({\cal S}(D_{4})-2)$-bounded, which was excluded. Hence $c\leq e-1$.
Therefore $|{\rm Aut}_{{\cal D}_{Q}}(Q)|\leq\alpha_{{\cal
D}_{Q}}(D_{n})\leq(cb)!$. For $b>3$, $\left\lfloor{1\over
2}(cb+(c+1)b-4)\right\rfloor=\left\lfloor{1\over 2}(2cb+b-4)\right\rfloor\geq
cb$, which would mean that $(Q,{\cal D}_{Q})$ is induction $w(U)$-adequately
$({\cal S}(D_{4})-2)$-bounded, which was excluded. Hence $c\leq e-1$ and
$b=3$. Now $|{\rm Aut}_{\cal D}(U)|\leq|{\rm Aut}_{{\cal D}_{4}}(U_{4})||{\rm
Aut}_{{\cal D}_{Q}}(Q)|\leq 8\cdot(3c)!$ and $\left\lfloor{1\over
2}(|U|-|{\cal D}|)\right\rfloor=\left\lfloor{1\over
2}(3c+3e+|D_{1}|+|D_{2}|-4)\right\rfloor\geq\left\lfloor{1\over
2}(6c+3+|D_{1}|+|D_{2}|-4)\right\rfloor\geq\left\lfloor{1\over
2}(6c+5)\right\rfloor\geq 3c+2$. Because $3c+2<3e\leq w(U)$ and
$8\cdot(3c)!<(3c+2)!$, we obtain that $(U,{\cal D})$ is $w(U)$-adequately
bounded.

###### Lemma 7.3

With notation as in Section 4, let $(U,{\cal D})$ be a flexible tight
interdependent orbit union with $|{\cal D}|\geq 4$, let $D^{1}$ and $D^{2}$ be
two distinct noncutvertices of ${\cal O}(U,{\cal D})$ whose removal leads to
sets $(Q^{i},{\cal D}_{Q^{i}})$ that are not induction $w(U)$-adequately
bounded, and let $(U_{m-2},{\cal D}_{m-2})$ be the interdependent orbit union
obtained by consecutively removing $D^{1}$ and $D^{2}$ by iterating the
process in Section 4. Then, independent of whether $(U_{m-2},{\cal D}_{m-2})$
is a forbidden configuration or $\max\\{w(U),5\\}$-adequately bounded,
$(U,{\cal D})$ is $\max\\{w(U),5\\}$-adequately bounded.

Proof. First suppose, for a contradiction, that there is a $D\in{\cal D}$ such
that $D^{1}\upharpoonleft\\!\downharpoonright_{\cal
D}D\upharpoonleft\\!\downharpoonright_{\cal D}D^{2}$ and $D$ is nontrivially
partitioned in each ${\cal D}_{Q^{i}}$. Because none of the sets from Lemma
5.11 contain any nontrivial order-autonomous antichains, both sets $D^{j}$
must be as in Lemma 7.1. Thus, by Lemma 7.1, $D^{1}$ and $D^{2}$ are pendant
vertices and $|D|=4$.

Let the partitions of $D$ induced by removal of $D^{1}$ or $D^{2}$,
respectively, be $D=A_{1}^{1}\cup A_{2}^{1}=A_{1}^{2}\cup A_{2}^{2}$. If
$A_{1}^{1}\in\\{A_{1}^{2},A_{2}^{2}\\}$, then $A_{1}^{1}$ is order-autonomous
in $U$, which cannot be. Thus $A_{1}^{1}$ intersects each of $A_{1}^{2}$ and
$A_{2}^{2}$. Because all $A_{i}^{j}$ are order-autonomous in
$U\setminus(D^{1}\cup D^{2})$ we obtain that $D$ is order-autonomous in
$U\setminus(D^{1}\cup D^{2})$. Because both $D^{1}$ and $D^{2}$ are pendant
vertices and we have just shown that $D$ is not adjacent to any other orbits,
we conclude that $\\{D,D^{1},D^{2}\\}$ is a connected component of ${\cal
O}(U,{\cal D})$. Hence it is the whole vertex set of the orbit graph,
contradicting that $|{\cal D}|\geq 4$. Thus, if
$D^{1}\upharpoonleft\\!\downharpoonright_{\cal D}E^{1}$ and
$D^{2}\upharpoonleft\\!\downharpoonright_{\cal D}E^{2}$ and each $E^{i}$ is
nontrivially partitioned in each ${\cal D}_{Q^{i}}$, then $E_{1}\not=E_{2}$.

Now let $\alpha_{n-2}:=\left|\left\\{\Phi|_{U_{m-2}}:\Phi\in{\rm
Aut}(U)\right\\}\right|\leq|{\rm Aut}_{D_{m-2}}(U_{m-2})|$ and note that
$|{\rm Aut}_{\cal D}(U)|\leq\alpha_{n-2}|{\rm Aut}(Q^{1},{\cal
D}_{Q^{1}})||{\rm Aut}(Q^{2},{\cal D}_{Q^{2}})|$. Also note that, by Lemmas
5.11 and 7.1, we have that $|{\rm Aut}(Q^{i},{\cal
D}_{Q^{1}})|\in\\{2,4,36\\}$.

In case $(U_{m-2},{\cal D}_{m-2})$ is $\max\\{w(U),5\\}$-adequately bounded,
an estimate similar to part 2 of Lemma 5.3 proves that, if $|{\rm
Aut}(Q^{1},{\cal D}_{Q^{1}})||{\rm Aut}(Q^{2},{\cal D}_{Q^{2}})|$ is bounded
by a product of factorials whose arguments are individually at most $w(U)-1$
and such that the sum of these arguments is bounded by $\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-6)\right\rfloor$, then $(U,{\cal D})$ is
$\max\\{w(U),5\\}$-adequately bounded: We use the numbers $w_{i}$ that we have
for $|{\rm Aut}_{D_{m-2}}(U_{m-2})|$ and for $|{\rm Aut}(Q^{1},{\cal
D}_{Q^{1}})||{\rm Aut}(Q^{2},{\cal D}_{Q^{2}})|$ and then note that their sum
is bounded by $\left\lfloor{1\over 2}(|U_{m-2}|-|{\cal
D}_{m-2}|)\right\rfloor+\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-6)\right\rfloor=\left\lfloor{1\over
2}((|U|-(|Q_{1}|+|Q_{2}|)+4)-(|{\cal D}|-2))\right\rfloor+\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-6)\right\rfloor\leq\left\lfloor{1\over 2}(|U|-|{\cal
D}|)\right\rfloor$. The details for bounding $|{\rm Aut}(Q^{1},{\cal
D}_{Q^{1}})||{\rm Aut}(Q^{2},{\cal D}_{Q^{2}})|$ with a product of factorials
whose arguments are bounded by $\max\\{w(U),5\\}-1$ and such that the sum of
the arguments is bounded by $\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-6)\right\rfloor$ are listed in Table 1.

$|{\rm Aut}_{{\cal D}_{Q^{1}}}(Q^{1})|\rule{0.0pt}{14.45377pt}$ $|Q_{1}|$
$|{\rm Aut}_{{\cal D}_{Q^{2}}}(Q^{2})|$ $|Q_{2}|$ $\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-6)\right\rfloor$ bound 36 12 36 12 9 $36\cdot 36<4!5!$ 36
12 4 8 7 $36\cdot 4=4!3!$ 36 12 2 6 6 $36\cdot 2<5!$ 4 8 4 8 5 $4\cdot 4<4!$ 4
8 2 6 4 $4\cdot 2<4!$ 2 6 2 6 3 $2\cdot 2<3!$

Table 1: Bounding $|{\rm Aut}_{{\cal D}_{Q^{1}}}(Q^{1})|\cdot|{\rm Aut}_{{\cal
D}_{Q^{2}}}(Q^{2})|$ when $(U_{n-2},{\cal D}_{n-2})$ is
$\max\\{w(U),5\\}$-adequately bounded. The offset we must subtract from
$|Q_{1}|+|Q_{2}|$ is $s=6$ and the sum of the arguments of the factorials in
the bound must be bounded by $\left\lfloor{1\over
2}|Q_{1}|+|Q_{2}|-6\right\rfloor$.

In case $(U_{m-2},{\cal D}_{m-2})$ is a forbidden configuration, we first note
that, because $E^{1}\not=E^{2}$, we have that $(U_{m-2},{\cal D}_{m-2})$
contains $2$ distinct orbits, namely the $E^{i}\cap U_{m-2}$, that have
exactly $2$ elements. Thus, by Lemma 6.6 and inspection of Figures 4 and 5,
$(U_{m-2},{\cal D}_{m-2})$ is one of $2C_{2}$, $2C_{3}$, $2C_{3}^{*}$, $2V$;
$\widehat{2V}$, $\overline{2V}$ or their dual.

In case $(U_{m-2},{\cal D}_{m-2})$ is one of $2C_{2}$, $2C_{3}$, $2C_{3}^{*}$,
$2V$ or their dual, we have that $|U|=|Q_{1}|+|Q_{2}|$ and ${\cal D}=4$, or
$|U|=|Q_{1}|+|Q_{2}|+2$ and ${\cal D}=5$. Thus $\left\lfloor{1\over
2}(|U|-|{\cal D}|)\right\rfloor\geq\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-4)\right\rfloor$. Moreover, $|{\rm Aut}_{{\cal D}}(U)|\leq
2|{\rm Aut}_{{\cal D}_{Q^{1}}}(Q^{1})||{\rm Aut}_{{\cal D}_{Q^{2}}}(Q^{2})|$
and the details for bounding $|{\rm Aut}_{\cal D}(U)|$ with the right product
of the right factorials are listed in Table 2.

$|{\rm Aut}_{{\cal D}_{Q^{1}}}(Q^{1})|\rule{0.0pt}{14.45377pt}$ $|Q_{1}|$
$|{\rm Aut}_{{\cal D}_{Q^{2}}}(Q^{2})|$ $|Q_{2}|$ $\left\lfloor{1\over
2}(|Q_{1}|+|Q_{2}|-4)\right\rfloor$ bound 36 12 36 12 10 $2\cdot 36\cdot
36<4!5!$ 36 12 4 8 8 $2\cdot 36\cdot 4<4!4!$ 36 12 2 6 7 $2\cdot 36\cdot
2<5!2!$ 4 8 4 8 6 $2\cdot 4\cdot 4<4!2!$ 4 8 2 6 5 $2\cdot 4\cdot 2<4!$ 2 6 2
6 4 $2\cdot 2\cdot 2<4!$

Table 2: Bounding $|{\rm Aut}_{\cal D}(U)|$ when $(U_{n-2},{\cal D}_{n-2})$ is
one of $2C_{2}$, $2C_{3}$, $2C_{3}^{*}$, $2V$ or their dual. The sum of the
arguments of the factorials in the bound must be bounded by
$\left\lfloor{1\over 2}(|U|-|{\cal D}|)\right\rfloor$, for which a lower bound
is provided in the second to last column.

Finally, in case $(U_{m-2},{\cal D}_{m-2})$ is one of $\widehat{2V}$,
$\overline{2V}$ or their dual, we have that $|U|=|Q_{1}|+|Q_{2}|+4$ and ${\cal
D}=5$. Thus $\left\lfloor{1\over 2}(|U|-|{\cal
D}|)\right\rfloor=\left\lfloor{1\over 2}(|Q_{1}|+|Q_{2}|+4-5)\right\rfloor$.
Moreover, $|{\rm Aut}_{{\cal D}}(U)|\leq 4|{\rm Aut}_{{\cal