# An intermediate case of exponential multivalued forbidden matrix
configurations

Wallace Peaslee 44footnotemark: 4
University of Cambridge
Department of Applied Mathematics and Theoretical Physics
Cambridge, United Kingdom Supported by a UK Engineering and Physical Sciences
Research Council Doctoral Training Partnership grant. Attila Sali
44footnotemark: 4
HUN-REN Alfréd Rényi Institute of Mathematics and
Department of Computer Science, BUTE
Budapest, Hungary Research was partially supported by the National Research,
Development and Innovation Office (NKFIH) grants K–116769 and SNN-135643. This
work was also supported by the BME-Artificial Intelligence FIKP grant of EMMI
(BME FIKP-MI/SC) and by the Ministry of Innovation and Technology and the
National Research, Development and Innovation Office within the Artificial
Intelligence National Laboratory of Hungary. Jun Yan
University of Warwick
Mathematics Institute
Coventry, United Kingdom Supported by the Warwick Mathematics Institute Centre
for Doctoral Training, and by funding from the UK EPSRC (Grant number:
EP/W523793/1).Research conducted under the auspices of the Budapest Semesters
in Mathematics program.

###### Abstract

The forbidden number $\operatorname{forb}(m,F)$, which denotes the maximum
number of distinct columns in an $m$-rowed $(0,1)$-matrix with no submatrix
that is a row and column permutation of $F$, has been widely studied in
extremal set theory. Recently, this function was extended to $r$-matrices,
whose entries lie in $\\{0,1,\cdots,r-1\\}$. $\operatorname{forb}(m,r,F)$ is
the maximum number of distinct columns in an $r$-matrix with no submatrix that
is a row and column permutation of $F$. While $\operatorname{forb}(m,F)$ is
polynomial in $m$, $\operatorname{forb}(m,r,F)$ is exponential for $r\geq 3$.
Recently, $\operatorname{forb}(m,r,F)$ was studied for some small
$(0,1)$-matrices $F$, and exact values were determined in some cases. In this
paper we study $\operatorname{forb}(m,r,M)$ for $M=\begin{bmatrix}0&1\\\
0&1\\\ 1&0\end{bmatrix}$, which is the smallest matrix for which this
forbidden number is unknown. Interestingly, it turns out that this problem is
closely linked with the following optimisation problem. For each triangle in
the complete graph $K_{m}$, pick one of its edges. Let $m_{e}$ denote the
number of times edge $e$ is picked. For each $\alpha\in\mathbb{R}$, what is
$H(m,\alpha)=\max\sum_{e\in E(K_{m})}\alpha^{m_{e}}$? We establish a
relationship between $\operatorname{forb}(m,r,M)$ and $H(m,(r-1)/(r-2))$, find
upper and lower bounds for $H(m,\alpha)$, and use them to significantly
improve known bounds for $\operatorname{forb}(m,r,M)$.

##  1 Introduction

For every matrix $A$, let $\left\lvert A\right\rvert$ denote the number of
columns in $A$. A matrix $A$ is called simple if all of its $\left\lvert
A\right\rvert$ columns are pairwise distinct. We say a matrix $A$ contains a
configuration of a matrix $F$, and denote it by $F\prec A$, if some submatrix
of $A$ is a row and column permutation of $F$. If $A$ does not contain a
configuration of $F$, we say that $A$ avoids $F$ and denote this as
$F\not\prec A$.

An $r$-matrix is a matrix whose entries are contained in the set
$\\{0,1,\ldots,r-1\\}$. Define $\operatorname{Avoid}(m,r,F)$ to be the set of
all $m$-rowed simple $r$-matrices that avoid $F$. The forbidden configuration
problem studies the following extremal function defined for a collection
$\mathcal{F}$ of matrices.

$\operatorname{forb}(m,r,\mathcal{F})=\max\left\\{\left\lvert
A\right\rvert\colon A\in\operatorname{Avoid}(m,r,F)\text{ for every
}F\in\mathcal{F}\right\\}$

We say $A\in\operatorname{Avoid}(m,r,\mathcal{F})$ is extremal if
$|A|=\operatorname{forb}(m,r,\mathcal{F})$. When $r=2$ we usually write
$\operatorname{forb}(m,{\mathcal{F}})$ in place of
$\operatorname{forb}(m,2,{\mathcal{F}})$. We also use
$\operatorname{forb}(m,r,F)$ instead of the more cumbersome
$\operatorname{forb}(m,r,\\{F\\})$.

The basic result in the theory of forbidden configurations is Sauer’s Theorem
(also proved by Perles and Shelah [9], and Vapnik and Chervonenkis [10]).

######  Theorem 1.1 ([8]).

For every positive integer $k$, let $K_{k}$ denote the $k\times 2^{k}$ matrix
containing every possible $(0,1)$-column exactly once. Then for every positive
integer $m$, we have

$\operatorname{forb}(m,K_{k})=\binom{m}{k-1}+\binom{m}{k-2}+\cdots+\binom{m}{1}+\binom{m}{0}.$

The matrix $K_{k}$ is also called the complete $2$-matrix. Note that for fixed
$k$, $\operatorname{forb}(m,K_{k})$ is polynomial in $m$. Alon [1] proved a
generalisation of this result for complete $r$-matrices $K_{k}^{r}$, which
contain every possible $(0,1,\cdots,r-1)$-column exactly once.
$\operatorname{forb}(m,r,K_{k}^{r})$ turns out to be exponential in $m$ when
$r>2$. This is a special case of a more general dichotomy phenomenon proved by
Füredi and Sali [6]. In what follows, an $(i,j)$-matrix is a matrix whose
entries are either $i$ or $j$.

######  Theorem 1.2 ([6]).

Let ${\mathcal{F}}$ be a family of $r$-matrices. If for every pair
$i,j\in\\{0,1,\cdots,r-1\\}$, there is an $(i,j)$-matrix in ${\mathcal{F}}$,
then $\operatorname{forb}(m,r,{\mathcal{F}})=O(m^{k})$ for some positive
integer $k$. If ${\mathcal{F}}$ has no $(i,j)$-matrix for some pair
$i,j\in\\{0,1,\cdots,r-1\\}$, then
$\operatorname{forb}(m,r,{\mathcal{F}})=\Omega(2^{m})$.

The function $\operatorname{forb}(m,{\mathcal{F}})$ has been investigated
extensively, and the reader is suggested to consult the dynamic survey of
Anstee [2]. However, the investigation of the general case of $r$-matrices
(for $r>2$) has just started. Earlier papers mainly focused on giving
conditions that ensure polynomial bounds, such as [3, 5].

A result of Dillon and Sali [4] calculates $\operatorname{forb}(m,r,F)$
exactly for all $r\geq 3$ and all $3\times 2$ and $3\times 3$ simple
$(0,1)$-matrices except for $M=\begin{bmatrix}0&1\\\ 0&1\\\ 1&0\end{bmatrix}$,
which they bound by:

$m(r-1)^{m-1}+(r-1)^{m}\leq\operatorname{forb}(m,r,M)\leq\frac{3}{2}m(r-1)^{m-1}+(r-1)^{m}$
(1)

The lower bound in (1) follows from the observation that the matrix consisting
of all columns with at most one 0 contains no configuration of $M$, while the
upper bound follows from
$\operatorname{forb}(m,M)=\left\lfloor\frac{3m}{2}\right\rfloor+1$ and a
general upper bound theorem of Dillon and Sali. The aim of this paper is to
study $\operatorname{forb}(m,r,M)$ and find better lower and upper bounds for
them.

It turns out that the value $\operatorname{forb}(m,r,M)$ is closely linked
with the answer to the following optimisation problem.

######  Definition 1.3.

A multigraph $\mathcal{G}$ on vertex set $V$ is called a triangular choice
multigraph (TCM) if it can be obtained as follows. Start with the empty graph
on $V$. For every unordered triple $u,v,w$ of distinct vertices in $V$, choose
exactly one of edge $uv,uw,vw$ and add a copy of it to the multigraph. In
particular, the total number of edges in $\mathcal{G}$, counting
multiplicities, is $\binom{|V|}{3}$.

A triangular choice multigraph $\mathcal{G}$ on $V$ is 2-recursive if
$|V|=1,2$ and $\mathcal{G}$ is the empty graph, or $|V|\geq 3$ and there
exists a partition $V=V_{1}\cup V_{2}$, with $V_{1},V_{2}\not=\emptyset$, and
multigraphs $\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3}$ such that

  * •

$\mathcal{G}=\mathcal{G}_{1}\cup\mathcal{G}_{2}\cup\mathcal{G}_{3}$, where the
union is taken with edge multiplicity.

  * •

$\mathcal{G}_{1}$ is a 2-recursive TCM on $V_{1}$ and $\mathcal{G}_{2}$ is a
2-recursive TCM on $V_{2}$.

  * •

$\mathcal{G}_{3}$ is obtained by adding a copy of edge $uv$ for every
unordered triple $u,v,w\in V$ with $u,v\in V_{1}$ and $w\in V_{2}$, and adding
a copy of edge $vw$ for every unordered triple $u,v,w\in V$ with $u\in V_{1}$
and $v,w\in V_{2}$.

12345

Vertex Triplet |  1,2,3 |  1,2,4 |  1,2,5 |  1,3,4 |  1,3,5 |  1,4,5 |  2,3,4 |  2,3,5 |  2,4,5 |  3,4,5
---|---|---|---|---|---|---|---|---|---|---
Subgraph |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345

Figure 1: An example triangular choice multigraph $\mathcal{G}$ on 5 vertices,
which is 2-recursive with $V_{1}=\\{1,2,3\\}$ and $V_{2}=\\{4,5\\}$. All 10
vertex triplets are enumerated in the table with the chosen edges indicated.

######  Question 1.4.

Let $\mathcal{G}$ be a triangular choice multigraph on $[m]$. For every
$ij\in[m]^{(2)}$, let $m^{\mathcal{G}}_{ij}$ denote the multiplicity of the
edge $ij$, which is also the number of unordered triples $i,j,k$ in which the
edge $ij$ is chosen. For every $\alpha\in\mathbb{R}$, define

$\displaystyle w(\mathcal{G},\alpha)$
$\displaystyle=\sum_{xy\in[m]^{(2)}}\alpha^{m^{\mathcal{G}}_{xy}},$
$\displaystyle H(m,\alpha)$
$\displaystyle=\max\left\\{w(\mathcal{G},\alpha)\colon\mathcal{G}\text{ is a
TCM on }[m]\right\\},$ $\displaystyle H_{2}(m,\alpha)$
$\displaystyle=\max\left\\{w(\mathcal{G},\alpha)\colon\mathcal{G}\text{ is a
2-recursive TCM on }[m]\right\\}.$

We say a TCM $\mathcal{G}$ is extremal if, depending on context, it satisfies
$w(\mathcal{G},\alpha)=H(m,\alpha)$ or
$w(\mathcal{G},\alpha)=H_{2}(m,\alpha)$. What are the values of $H(m,\alpha)$
and $H_{2}(m,\alpha)$? What do the extremal graphs look like?

Our first result relates $\operatorname{forb}(m,r,M)$ to
$H(m,\frac{r-1}{r-2})$ and $H_{2}(m,\frac{r-1}{r-2})$.

######  Theorem 1.5.

For every $m\geq 0$, $r\geq 3$,

$H_{2}\left(m,\frac{r-1}{r-2}\right)\cdot(r-2)^{m-2}\leq\operatorname{forb}(m,r,M)-(r-1)^{m}-m(r-1)^{m-1}\leq
H\left(m,\frac{r-1}{r-2}\right)\cdot(r-2)^{m-2}.$

Our second result is the following upper bound on $H(m,2)$, which we then use
to find an upper bound for $\operatorname{forb}(m,r,M)$ for all $r\geq 3$.

######  Theorem 1.6.

For every $m\geq 0$, $H(m,2)\leq\frac{83}{192}m2^{m-1}$.

######  Theorem 1.7.

For every $m\geq 0$ and $r\geq 3$, we have
$\operatorname{forb}(m,r,M)\leq\left(1+\frac{83}{192}\right)m(r-1)^{m-1}+(r-1)^{m}$.

Our third result is a lower bound on $H_{2}(m,\alpha)$ obtained by a recursive
construction, which then implies a lower bound on $\operatorname{forb}(m,r,M)$
for all $r\geq 3$. For every $\alpha>1$, let
$\lambda(\alpha)=\sum_{j=1}^{\infty}\frac{2^{j-1}}{\alpha^{2^{j}}}$.

######  Theorem 1.8.

For every $\alpha>1$, $\epsilon>0$, and all sufficiently large $m$, we have

$H_{2}(m,\alpha)>\frac{1}{2}(\lambda(\alpha)-\epsilon)m\alpha^{m}.$

Consequently, for every $r\geq 3$, $\epsilon>0$, and all sufficiently large
$m$, we have

$\operatorname{forb}(m,r,M)\geq\left(1+\frac{r-1}{2(r-2)^{2}}\lambda\left(\frac{r-1}{r-2}\right)-\epsilon\right)m(r-1)^{m-1}+(r-1)^{m}.$

Note that since $\lambda(2)\approx 0.390747$ and $\frac{83}{192}\approx
0.432292$, Theorem 1.5, Theorem 1.6 and Theorem 1.9 together improve the
bounds for $\operatorname{forb}(m,3,M)$ given by (1). For every $r\geq 3$, one
can compare to a Riemann sum to show that
$\frac{r-1}{2(r-2)^{2}}\lambda(\frac{r-1}{r-2})>0.25$, and numerical
experiments suggest a stronger bound
$\frac{r-1}{2(r-2)^{2}}\lambda(\frac{r-1}{r-2})>0.36$.

Moreover, in the case when $\alpha=2$, we show that the construction we used
in Theorem 1.8 above to obtain a lower bound for $H_{2}(m,2)$ is actually
optimal, which in particular provides an exact recurrence formula for
$H_{2}(m,2)$.

######  Theorem 1.9.

For every $m\geq 3$ except 6, let $k=k(m)$ be the unique integer such that
$2^{k}+2^{k-1}\leq m<2^{k}+2^{k+1}$. For $m=6$, let $k=k(6)=3$. Then

$H_{2}(m,2)=H_{2}(2^{k},2)2^{m-2^{k}}+H_{2}(m-2^{k},2)2^{2^{k}}+2^{k}(m-2^{k}).$

Consequently,
$\lim_{m\to\infty}\frac{H_{2}(m,2)}{m2^{m-1}}=\lambda(2)=\sum_{j=1}^{\infty}\frac{2^{j-1}}{2^{2^{j}}}$.

Furthermore, we have the following conjecture when $r=3$ and $\alpha=2$, .

######  Conjecture 1.10.

$H(m,2)=H_{2}(m,2)$ for all $m\geq 3$. Consequently,
$\operatorname{forb}(m,3,M)=2^{m}+m2^{m-1}+H(m,2)$, and

$\lim_{m\to\infty}\frac{\operatorname{forb}(m,3,M)}{m2^{m-1}}-1=\lim_{m\to\infty}\frac{H(m,2)}{m2^{m-1}}=\lim_{m\to\infty}\frac{H_{2}(m,2)}{m2^{m-1}}=\lambda(2).$

The rest of the paper is organised as follows. In Section 2, we introduce two
key concepts that will be used throughout this paper. In Section 2.1, we show
that to every extremal $A\in\operatorname{Avoid}(m,r,M)$, we can associate
what is called a _choice_ , which is a collection $\mathcal{B}$ of
$\binom{m}{3}$ $3\times 3$ matrices, one for each triple of rows in $A$.
Roughly speaking, for each triple of rows in $A$, the corresponding $3\times
3$ matrix in $\mathcal{B}$ witnesses the fact that $A$ restricted to these
three rows contains no configuration of $M$. We further distinguish every
choice as either _good_ or _bad_. In Section 2.2, we encode the information
contained in every choice $\mathcal{B}$ into a directed multigraph
$\mathcal{D}_{\mathcal{B}}$, which allows us to analyse the choices and, in
particular, compute $\operatorname{forb}(m,r,M)$ more easily.

In Section 3, we prove Theorem 1.5, which links $\operatorname{forb}(m,r,M)$
with the quantities $H(m,\frac{r-1}{r-2})$ and $H_{2}(m,\frac{r-1}{r-2})$
introduced in Question 1.4. We first prove this in Section 3.1 under the
additional assumption that the choice $\mathcal{B}$ associated to the extremal
matrix $A$ is good. To this end, we define an additional undirected multigraph
$\mathcal{G}_{\mathcal{B}}$, and write $\operatorname{forb}(m,r,M)$ in terms
of its edge multiplicities. Then, we finish the proof in Section 3.2 by
dealing with the case when the associated choice $\mathcal{B}$ is not
necessarily good.

In Section 4, we prove Theorem 1.6 and Theorem 1.7. First, in Section 4.1, we
define the concept of closed sets, which will help us analyse the structures
of triangular choice multigraphs. Then, in Section 4.2, we prove a key lemma
showing that when $\alpha=2$, there exists an extremal TCM whose maximal
closed sets all have sizes at least 2. In Section 4.3, we use this lemma to
prove Theorem 1.6, which gives an upper bound on $H(m,2)$, and then deduce
Theorem 1.7 from it.

In Section 5, we prove Theorem 1.8 and Theorem 1.9. We begin by using the
definition of 2-recursive TCM to find a recurrence relation for
$H_{2}(m,\alpha)$ that involves maximising over all possible bipartitions of
$[m]$, which we call _splits_. Then we prove Theorem 1.8 in Section 5.1, which
gives a lower bound on $H_{2}(m,\alpha)$, by specifying a particular split for
every $m$. In Section 5.2, we prove Theorem 1.9, which completely determines
the values of $H_{2}(m,2)$ by showing the splits we specified in Section 5.1
are actually optimal.

In Section 6, we begin by stating generalisations to Theorem 1.6 and Theorem
1.9 that we proved for the cases when $\alpha\geq 2$, and make an analogous
conjecture to Conjecture 1.10. Finally, we comment on this conjecture and the
open cases of $r\geq 4$ and $\alpha<2$.

##  2 Preliminaries

In this section, we introduce two key concepts that will be used throughout
this paper.

###  2.1 Choice

In this subsection, we associate what is called a choice to every extremal
$A\in\operatorname{Avoid}(m,r,M)$. Let $A\in\operatorname{Avoid}(m,r,M)$ be
extremal. Note that for each triple $i,j,k$ of rows, $A$ restricted to rows
$i,j,k$ does not contain any configuration of $M$ is equivalent to $A$
restricted to rows $i,j,k$ containing at most one column in each of the
following three pairs.

$\left\\{\begin{bmatrix}1\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}0\\\ 1\\\
1\end{bmatrix}\right\\},\left\\{\begin{bmatrix}0\\\ 1\\\
0\end{bmatrix},\begin{bmatrix}1\\\ 0\\\
1\end{bmatrix}\right\\},\left\\{\begin{bmatrix}0\\\ 0\\\
1\end{bmatrix},\begin{bmatrix}1\\\ 1\\\ 0\end{bmatrix}\right\\}$ (2)

Since $A$ contains the maximum number of distinct columns, for each triple
$i,j,k$ of rows, $A$ restricted to those rows must contain exactly one column
in each of the three pairs above, as otherwise we can obtain a matrix in
$\operatorname{Avoid}(m,r,M)$ that contains strictly more columns. This leads
to the following definitions.

######  Definition 2.1.

A choice on $V$ is a collection $\mathcal{B}=(B_{i,j,k}\colon\\{i,j,k\\}\in
V^{(3)})$ of $3\times 3$ matrices, where each $B_{i,j,k}$ is formed by picking
one column from each of the three pairs in (2) and putting them together in
that order. For every $X\subset V$, the restriction of a choice $\mathcal{B}$
on $V$ to $X$ is the choice $\mathcal{B}|_{X}=(B_{i,j,k}\colon\\{i,j,k\\}\in
X^{(3)})$ on $X$.

Let $A\in\operatorname{Avoid}(m,r,M)$. We say that rows $i,j,k$ forbid a
$3\times 3$ matrix $B_{i,j,k}$ if $A$ restricted to rows $i,j,k$ contains no
column of $B_{i,j,k}$. If $A$ is extremal, then there is a unique $3\times 3$
matrix $B_{i,j,k}$ forbidden by each triple $i,j,k$ of rows, hence every
extremal $A$ is associated with a choice
$\mathcal{B}=(B_{i,j,k}\colon\\{i,j,k\\}\in[m]^{(3)})$ on $[m]$.

We call a choice $\mathcal{B}$ good if none of the $B_{i,j,k}$ is $I$ or
$I^{c}$, and bad otherwise.

Given a choice $\mathcal{B}$ on $[m]$, define
$\operatorname{Avoid}(m,r,\mathcal{B})$ to be the set of all simple $m$-rowed
matrices $A$ such that for each triple $i,j,k$, $A$ restricted to rows $i,j,k$
contains no columns of $B_{i,j,k}$. Also, define
$\operatorname{forb}(m,r,\mathcal{B})=\max\\{\left\lvert A\right\rvert\colon
A\in\operatorname{Avoid}(m,r,\mathcal{B})\\}$.

It is clear from the definition above that $\operatorname{Avoid}(m,r,M)$ is
the union of $\operatorname{Avoid}(m,r,\mathcal{B})$ taken over all possible
choices $\mathcal{B}$ on $[m]$. Hence,

$\operatorname{forb}(m,r,M)=\max\\{\operatorname{forb}(m,r,\mathcal{B})\colon\mathcal{B}\text{
is a choice on }[m]\\}.$

######  Definition 2.2.

For any column $c$, define its _support_ to be the index set of its
$(0,1)$-entries. For a choice $\mathcal{B}$ on $V$ and any column $c$ with row
index set $V$, we say $c$ is valid with respect to $\mathcal{B}$ if for every
triple $i,j,k$ of rows, $c$ restricted to these rows does not contain a column
of $B_{i,j,k}$.

Now let $\mathcal{B}$ be a choice on $[m]$ and let $X\subset[m]$. Define
$\mathcal{C}(\mathcal{B},X)$ to be the set of valid $(0,1)$-columns with row
set $X$ with respect to $\mathcal{B}|_{X}$, and define
$c(\mathcal{B},X)=\left\lvert\mathcal{C}(\mathcal{B},X)\right\rvert$.
Similarly, let $\mathcal{C}^{*}(\mathcal{B},X)$ be the set of all valid
columns on $[m]$ with respect to $\mathcal{B}$ that have support $X$, and let
$c^{*}(\mathcal{B},X)=\left\lvert\mathcal{C}^{*}(\mathcal{B},X)\right\rvert$.

Observe that $c^{*}(\mathcal{B},X)=c(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}$ since any of the $r-2$ symbols in $\\{2,\cdots,r-1\\}$ can be
used on $[m]\setminus X$. The following lemma shows that to compute
$\operatorname{forb}(m,r,\mathcal{B})$, it suffices to count valid columns
with different supports separately.

######  Lemma 2.3.

For any choice $\mathcal{B}$ on $[m]$, we have

$\operatorname{forb}(m,r,\mathcal{B})=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)=\sum_{X\subset[m]}c(\mathcal{B},X)(r-2)^{m-|X|}.$

###### Proof.

Let $Y=\bigcup_{X\subset[m]}\mathcal{C}^{*}(\mathcal{B},X)$. Note that for any
$X_{1},X_{2}\subset[m]$ and $X_{1}\neq X_{2}$,
$\mathcal{C}^{*}(\mathcal{B},X_{1})\cap\mathcal{C}^{*}(\mathcal{B},X_{2})=\emptyset$.
Therefore, $|Y|=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)$. Consider the matrix
$A$ consisting of all the columns in $Y$ exactly once. Then,
$A\in\operatorname{Avoid}(m,r,\mathcal{B})$ and hence
$\operatorname{forb}(m,r,\mathcal{B})\geq|A|=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)$.

On the other hand, let $A^{\prime}\in\operatorname{Avoid}(m,r,\mathcal{B})$.
For every column $c$ in $A^{\prime}$, if the support of $c$ is
$X_{c}\subset[m]$, then $c\in\mathcal{C}^{*}(\mathcal{B},X_{c})\subset Y$.
Hence, $|A^{\prime}|\leq|Y|=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)$ and so
$\operatorname{forb}(m,r,\mathcal{B})\leq\sum_{X\subset[m]}c^{*}(\mathcal{B},X)$.
Therefore,
$\operatorname{forb}(m,r,\mathcal{B})=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)$.
∎

###  2.2 Multigraph

In this subsection, we show how to encode the forbidden conditions carried by
a choice $\mathcal{B}$ into a directed multigraphs.

######  Definition 2.4.

Let $X\subseteq[m]$ and $\mathcal{B}$ be a choice on $[m]$. For distinct
$i,j\in X$, we say that there is a _$0$ -implication_ from $i$ to $j$ on $X$
if for any column $c$ with support $X$ in a matrix
$A\in\operatorname{Avoid}(m,r,\mathcal{B})$, $c_{i}=0$ implies $c_{j}=0$.

Fix a choice $\mathcal{B}$ on $[m]$. It is easy to check that for each triple
$i,j,k$ of rows, if $B_{i,j,k}\neq I,I^{c}$, then $B_{i,j,k}$ is a
configuration of one of the following:

$A_{1}=\begin{bmatrix}0&0&0\\\ 1&0&1\\\ 1&1&0\end{bmatrix},\mbox{
\par}A_{2}=\begin{bmatrix}0&0&1\\\ 0&1&0\\\ 1&1&1\end{bmatrix}.$

Let $X\subset[m]$ and $i,j,k$ be a triple in $X$. Note that if
$B_{i,j,k}=A_{1}$, then the restriction applied by forbidding $B_{i,j,k}$ is
exactly equivalent to two $0$-implications on $X$, one from $i$ to $j$ and
another from $i$ to $k$. Similarly, if $B_{i,j,k}=A_{2}$, then the restriction
is equivalent to two $0$-implications on $X$, one from $i$ to $k$ and another
from $j$ to $k$. In general, when $B_{i,j,k}$ is a configuration of $A_{1}$ or
$A_{2}$, the restriction it applies is always equivalent to two
$0$-implications on $X$ among $i,j,k$. Moreover, these two $0$-implications
either both come from the same row index or both go to the same row index.

We can now encode this information into a directed multigraph.

######  Definition 2.5.

Given a choice $\mathcal{B}$ and $X\subseteq[m]$, define the directed
multigraph $\mathcal{D}_{\mathcal{B}}(X)$ associated to $\mathcal{B}$ and $X$
as follows. For each triple $i,j,k$ of rows of $X$, if $B_{i,j,k}=I,I^{c}$, we
do nothing. Otherwise, we draw two directed edges corresponding to the two
$0$-implications equivalent to forbidding $B_{i,j,k}$, with an edge going from
$x$ to $y$ if there is a $0$-implication from $x$ to $y$. For brevity, we
write $\mathcal{D}_{\mathcal{B}}$ for $\mathcal{D}_{\mathcal{B}}([m])$.

In general, the directed multigraph $\mathcal{D}_{\mathcal{B}}(X)$ is not
simply the subgraph induced by $X$ in $\mathcal{D}_{\mathcal{B}}$. Indeed, if
a directed edge $ij$ in $\mathcal{D}_{\mathcal{B}}$ comes from the triple
$i,j,k$, and $X$ contains $i,j$ but not $k$, then at least this copy of the
directed edge $ij$ is not in $\mathcal{D}_{\mathcal{B}}(X)$. However,
$\mathcal{D}_{\mathcal{B}}(X)$ could still contain a directed edge $ij$ if $X$
contains another row $k^{\prime}$ which contributes to a directed edge $ij$.
From definition, we also see that $\mathcal{D}_{\mathcal{B}}$ is a directed
multi-graph with $2\binom{m}{3}$ directed edges if $\mathcal{B}$ is a good
choice. Figure 2 shows an example directed multigraph associated to a good
choice $\mathcal{B}$ on five vertices. In the next section, we will use the
directed multigraphs $\mathcal{D}_{\mathcal{B}}(X)$ to help us compute the
quantities $c(\mathcal{B},X)$ in Lemma 2.3.

12345

${1,2,3}$

${1,2,3}$

$1,2,4$

$1,2,4$

$1,2,5$

$1,2,5$

$1,3,4$

$1,3,4$

$1,3,5$

$1,3,5$

$1,4,5$

$1,4,5$

$2,3,4$

$2,3,4$

$2,3,5$

$2,3,5$

$2,4,5$

$2,4,5$

$3,4,5$

$3,4,5$

$B_{1,2,3}$ |  $B_{1,2,4}$ |  $B_{1,2,5}$ |  $B_{1,3,4}$ |  $B_{1,3,5}$ |  $B_{1,4,5}$ |  $B_{2,3,4}$ |  $B_{2,3,5}$ |  $B_{2,4,5}$ |  $B_{3,4,5}$
---|---|---|---|---|---|---|---|---|---
$A_{1}$ |  $A_{2}$ |  $A_{2}$ |  $A_{2}$ |  $A_{2}$ |  $A_{1}$ |  $A_{2}$ |  $A_{2}$ |  $A_{1}$ |  $A_{1}$
12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345 |  12345

Figure 2: An example directed multigraph $\mathcal{D}_{\mathcal{B}}$ on 5
vertices showing the 0-implications from a good (and uniformly directed)
choice $\mathcal{B}$. The 0-implications corresponding to each
$B_{i,j,k}\in\mathcal{B}$ are enumerated in the table. Each directed edge is
labeled with the triple that contributed the corresponding 0-implication.

##  3 Proof of Theorem 1.5

In this section, we prove Theorem 1.5, which relates
$\operatorname{forb}(m,r,M)$ to the quantities $H(m,\frac{r-1}{r-2})$ and
$H_{2}(m,\frac{r-1}{r-2})$ introduced in Question 1.4. We do this in two
steps. Recall from Section 2.1 that
$\operatorname{forb}(m,r,M)=\max\\{\operatorname{forb}(m,r,\mathcal{B})\colon\mathcal{B}\text{
is a choice on }[m]\\}$, and every choice is either good or bad. We first
prove Theorem 1.5 in Section 3.1 assuming the choice $\mathcal{B}$ is good.
Then, we finish the proof in Section 3.2 by proving Theorem 3.4, which bounds
the maximum of $\operatorname{forb}(m,r,\mathcal{B})$ over all bad choices
$\mathcal{B}$.

###  3.1 Good choice

In this subsection, we assume $\mathcal{B}$ is a good choice on $[m]$. To
determine $\operatorname{forb}(m,r,\mathcal{B})$, it suffices to compute
$c(\mathcal{B},X)$ for each $X\subset[m]$ by Lemma 2.3.

######  Lemma 3.1.

Let $\mathcal{B}$ be a good choice on $[m]$ and let $X\subset[m]$. Then
$c(\mathcal{B},X)=n_{t}(\mathcal{B},X)+t(\mathcal{B},X)+1$, where
$t(\mathcal{B},X)$ is the number of strongly connected components in
$\mathcal{D}_{\mathcal{B}}(X)$ and $n_{t}(\mathcal{B},X)$ is the number of
unordered pairs of strongly connected components in
$\mathcal{D}_{\mathcal{B}}(X)$ such that there is no directed edge between
them.

Consequently, $c(\mathcal{B},X)\leq n(\mathcal{B},X)+\left\lvert
X\right\rvert+1$, where $n(\mathcal{B},X)$ is the number of unordered pairs of
vertices in $X$ with no directed edge between them in
$\mathcal{D}_{\mathcal{B}}(X)$. For simplicity, we sometimes say there is a
non-edge between two such vertices. Equality is achieved if all strongly
connected components in $\mathcal{D}_{\mathcal{B}}(X)$ are singletons.

###### Proof.

Fix a good choice $\mathcal{B}$ on $[m]$ and an $X\subset[m]$, write $t$ for
$t(\mathcal{B},X)$ and let $C_{1},\cdots,C_{t}$ be all the strongly connected
components in $\mathcal{D}_{\mathcal{B}}(X)$. For any distinct $i,j\in[t]$,
edges (if any) between vertices in $C_{i}$ and $C_{j}$ can only go in one
direction, as otherwise $C_{i}\cup C_{j}$ is a larger strongly connected
component. Hence, we may assume without loss of generality that
$C_{1},\cdots,C_{t}$ are ordered such that for any $i<j$ in $[t]$, edges (if
any) between $C_{i}$ and $C_{j}$ always go from $C_{i}$ to $C_{j}$.

Let $S=\\{(i,j)\in[t]\times[t]\colon i<j\text{ and there is no directed edge
between $C_{i}$ and $C_{j}$}\\}$, then $|S|=n_{t}(\mathcal{B},X)$. We claim
that $(i,j)\in S$ implies that $j=i+1$. Indeed, if $(i,j)\in S$ and $j>i+1$,
let $x\in C_{i},y\in C_{i+1}$ and $z\in C_{j}$. Then, as there is no directed
edge between $C_{i}$ and $C_{j}$, the two directed edges corresponding to the
two 0-implications created by $B_{x,y,z}$ must be $xy$ and $zy$, or $yx$ and
$yz$. In the first case, the edge $zy$ goes from $C_{j}$ to $C_{i+1}$, while
in the second case, the edge $yx$ goes from $C_{i+1}$ to $C_{i}$. Both
contradict the ordering of the strongly connected components.

Now we compute $c(\mathcal{B},X)$, the number of valid (0,1)-columns $c$ with
row set $X$ with respect to $\mathcal{B}|_{X}$. Such a column $c$ has to be
constant on each strongly connected component. The column that is 1 on every
component is a valid choice of $c$. For every $i\in[t]$, let $c$ be a valid
column such that $C_{i}$ is the first component on which $c$ is 0. Then, $c$
is 1 on each $C_{j}$ with $j<i$ from assumption. Also, unless $(i,j)\in S$,
$c$ is 0 on each $C_{j}$ with $j>i$ because there is a directed edge going
from $C_{i}$ to $C_{j}$. In any case, the column $c$ that is 0 on $C_{k}$ for
each $k\geq i$ and 1 on each $C_{k}$ with $k<i$ is always valid. As $i$ ranges
in $[t]$, we get $t=t(\mathcal{B},X)$ such columns. From above, the only $j>i$
that could satisfy $(i,j)\in S$ is $j=i+1$. In this case, the column $c$ that
is 0 on $C_{k}$ for each $k\geq i$ except $i+1$, and 1 on $C_{i+1}$ and each
$C_{k}$ with $k<i$ is also valid. There are $|S|=n_{t}(\mathcal{B},X)$ such
columns as $i$ ranges in $[t]$.

This implies that $c(\mathcal{B},X)=n_{t}(\mathcal{B},X)+t(\mathcal{B},X)+1$.
The second part of the lemma is is clear as $t(\mathcal{B},X)\leq\left\lvert
X\right\rvert$ and $n_{t}(\mathcal{B},X)\leq n(\mathcal{B},X)$ trivially. If
all strongly connected components in $\mathcal{D}_{\mathcal{B}}(X)$ are
singletons, then $t(\mathcal{B},X)=|X|$ and
$n_{t}(\mathcal{B},X)=n(\mathcal{B},X)$, so equality is achieved. ∎

Recall that $c^{*}(\mathcal{B},X)=c(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}$. Lemma 2.3 and Lemma 3.1 imply that

$\displaystyle\operatorname{forb}(m,r,\mathcal{B})$
$\displaystyle=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)=\sum_{X\subset[m]}c(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}$
$\displaystyle\leq\sum_{X\subset[m]}(n(\mathcal{B},X)+\left\lvert
X\right\rvert+1)(r-2)^{m-\left\lvert X\right\rvert}$
$\displaystyle=(r-1)^{m}+m(r-1)^{m-1}+\sum_{X\subset[m]}n(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}.$ (3)

To maximise the quantity
$\sum_{X\subset[m]}n(\mathcal{B},X)(r-2)^{m-\left\lvert X\right\rvert}$ over
all good choices $\mathcal{B}$, we define an undirected multigraph
$\mathcal{G}_{\mathcal{B}}$ that transforms this problem to Question 1.4.

######  Definition 3.2.

Fix a good choice $\mathcal{B}$ on $[m]$. For every triple $x<y<z$, the
restriction imposed by forbidding $B_{x,y,z}$ corresponds to 2 directed edges
sharing a common vertex in the triangle $xyz$ in $\mathcal{D}_{\mathcal{B}}$,
say $xy,xz$ or $yx,zx$. Then we add an undirected copy of the other edge, in
this case $yz$, to the multigraph $\mathcal{G}_{\mathcal{B}}$. Moreover, for
every unordered pair $xy\in[m]^{(2)}$, denote the multiplicity of edge $xy$ in
$\mathcal{G}_{\mathcal{B}}$ by $m^{\mathcal{B}}_{xy}$, where we drop the
superscript if the choice of $\mathcal{B}$ is clear.

Note that, by definition, $\mathcal{G}_{\mathcal{B}}$ is always a triangular
choice multigraph and
$m^{\mathcal{B}}_{xy}=m^{\mathcal{G}_{\mathcal{B}}}_{xy}$. On the other hand,
for every triangular choice multigraph $\mathcal{G}$, we can find a good
choice $\mathcal{B}$ such that $\mathcal{G}=\mathcal{G}_{\mathcal{B}}$. Figure
2 provides an example of a directed multigraph $\mathcal{D}_{\mathcal{B}}$
associated to a good choice $\mathcal{B}$. The triangular choice multigraph
$\mathcal{G}_{\mathcal{B}}$ associated to the same good choice $\mathcal{B}$
is given in Figure 1.

The following lemma rewrites the sum in (3.1) that we are trying to maximise,
and brings it to the form of Question 1.4.

######  Lemma 3.3.

For every good choice $\mathcal{B}$ on $[m]$,

$\sum_{X\subset[m]}n(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}=(r-2)^{m-2}\sum_{xy\in[m]^{(2)}}\left(\frac{r-1}{r-2}\right)^{m_{xy}}.$

###### Proof.

Let $xy\in[m]^{(2)}$ and let $\\{x,y\\}\subset X\subset[m]$ be such that there
is no directed $xy$ or $yx$ edge in $\mathcal{D}_{\mathcal{B}}(X)$.
Equivalently, for all vertices $z\in X\setminus\\{x,y\\}$, $xy$ is the edge
among $xy,xz,yz$ added in $\mathcal{G}_{\mathcal{B}}$. Since there are
$m_{xy}$ such $z\in[m]\setminus\\{x,y\\}$, there are $\binom{m_{xy}}{k}$ such
choices of $X$ with $|X|=k+2$ for all $0\leq k\leq m_{xy}$, as we choose $k$
such $z$ alongside $x$ and $y$.

Therefore, we have

$\displaystyle\sum_{X\subset[m]}n(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}$ $\displaystyle=\sum_{X\subset[m]}(r-2)^{m-|X|}\sum_{xy\in
X^{(2)}}\mathbbm{1}(\text{there is no edge }xy\text{ in
}\mathcal{D}_{\mathcal{B}}(X))$
$\displaystyle=\sum_{xy\in[m]^{(2)}}\sum_{\\{x,y\\}\subset
X\subset[m]}(r-2)^{m-|X|}\mathbbm{1}(\text{there is no edge }xy\text{ in
}\mathcal{D}_{\mathcal{B}}(X))$
$\displaystyle=\sum_{xy\in[m]^{(2)}}\sum_{k=0}^{m_{xy}}\binom{m_{xy}}{k}(r-2)^{m-k-2}$
$\displaystyle=\sum_{xy\in[m]^{(2)}}(r-2)^{m-2-m_{xy}}\sum_{k=0}^{m_{xy}}\binom{m_{xy}}{k}(r-2)^{m_{xy}-k}$
$\displaystyle=(r-2)^{m-2}\sum_{xy\in[m]^{(2)}}\left(\frac{r-1}{r-2}\right)^{m_{xy}},$

as required. ∎

We now prove Theorem 1.5 assuming Theorem 3.4, which will be proved in the
next section.

###### Proof of Theorem 1.5.

The cases when $m=0,1,2$ are trivial, so assume $m\geq 3$. Let $\mathcal{B}$
be a good choice on $[m]$ and let $\alpha_{r}=\frac{r-1}{r-2}$. Then, (3.1)
and Lemma 3.3 imply

$\displaystyle\operatorname{forb}(m,r,\mathcal{B})$
$\displaystyle\leq(r-1)^{m}+m(r-1)^{m-1}+(r-2)^{m-2}\sum_{xy\in[m]^{(2)}}\alpha_{r}^{m^{\mathcal{G}_{\mathcal{B}}}_{xy}}$
$\displaystyle\leq(r-1)^{m}+m(r-1)^{m-1}+(r-2)^{m-2}H\left(m,\alpha_{r}\right),$

as $\mathcal{G}_{\mathcal{B}}$ is a triangular choice multigraph. Since this
is true for every good choice $\mathcal{B}$, and Theorem 3.4 shows
$\operatorname{forb}(m,r,\mathcal{B})$ have the same upper bound for all bad
choices $\mathcal{B}$, we have
$\operatorname{forb}(m,r,M)\leq(r-1)^{m}+m(r-1)^{m-1}+H(m,\alpha_{r})(r-2)^{m-2}$,
as required.

On the other hand, let $\mathcal{G}$ be a 2-recursive triangular choice
multigraph on $[m]$ such that $w(\mathcal{G},\alpha_{r})=H_{2}(m,\alpha_{r})$,
and let $[m]=V_{1}\cup V_{2}$ and
$\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3}$ be as in Definition 1.3. As
permuting the vertex labels does not change $w(\mathcal{G},\alpha_{r})$, we
may assume there exists some $m^{\prime}\in[m-1]$ such that
$V_{1}=[m^{\prime}]$ and $V_{2}=[m]\setminus[m^{\prime}]$. Note that from the
definition of 2-recursive TCM, we have

$w(\mathcal{G},\alpha_{r})=w(\mathcal{G}_{1},\alpha_{r})\alpha_{r}^{m-m^{\prime}}+w(\mathcal{G}_{2},\alpha_{r})\alpha_{r}^{m^{\prime}}+m^{\prime}(m-m^{\prime}).$

Hence, $w(\mathcal{G},\alpha_{r})=H_{2}(m,\alpha_{r})$ implies that
$w(\mathcal{G}_{1},\alpha_{r})=H_{2}(m^{\prime},\alpha_{r})$ and
$w(\mathcal{G}_{2},\alpha_{r})=H_{2}(m-m^{\prime},\alpha_{r})$.

We say a choice $\mathcal{B}$ on $[m]$ is uniformly directed if for all $i<j$,
all directed edges between $i$ and $j$ in $\mathcal{D}_{\mathcal{B}}$ point
from $i$ to $j$. We use induction to show that for every $m\geq 1$ and every
2-recursive TCM $\mathcal{G}$ on $[m]$ satisfying
$w(\mathcal{G},\alpha_{r})=H_{2}(m,\alpha_{r})$, there exists a good choice
$\mathcal{B}$ on $[m]$ such that $\mathcal{G}_{\mathcal{B}}=\mathcal{G}$ and
${\mathcal{B}}$ is uniformly directed. Note that empty choice works for
$m=1,2$. For $m\geq 3$, by induction hypothesis, there exist uniformly
directed good choices $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ on
$[m^{\prime}]$ and $[m]\setminus[m^{\prime}]$, respectively, such that
$\mathcal{G}_{\mathcal{B}_{1}}=\mathcal{G}_{1}$ and
$\mathcal{G}_{\mathcal{B}_{2}}=\mathcal{G}_{2}$. For each triple $1\leq
i<j\leq m^{\prime}<k\leq m$, define the choice on $i,j,k$ so that the
corresponding edges in $\mathcal{D}_{\mathcal{B}}$ are $ik$ and $jk$. For each
triple $1\leq i\leq m^{\prime}<j<k\leq m$, define the choice on $i,j,k$ so
that the corresponding edges in $\mathcal{D}_{\mathcal{B}}$ are $ij$ and $ik$.
Taking these together with $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ gives a
uniformly directed good choice $\mathcal{B}$ satisfying
$\mathcal{G}_{\mathcal{B}}=\mathcal{G}$, as required. In particular, for all
$X\subset[m]$, strongly connected components in $\mathcal{D}_{\mathcal{B}}(X)$
are all singletons. Hence, by Lemma 2.3, Lemma 3.1, and Lemma 3.3, we have

$\displaystyle\operatorname{forb}(m,r,M)$
$\displaystyle\geq\operatorname{forb}(m,r,\mathcal{B})=\sum_{X\subset[m]}c^{*}(\mathcal{B},X)$
$\displaystyle=\sum_{X\subset[m]}(n(\mathcal{B},X)+\left\lvert
X\right\rvert+1)(r-2)^{m-\left\lvert X\right\rvert}$
$\displaystyle=(r-1)^{m}+m(r-1)^{m-1}+\sum_{X\subset[m]}n(\mathcal{B},X)(r-2)^{m-\left\lvert
X\right\rvert}$
$\displaystyle=(r-1)^{m}+m(r-1)^{m-1}+(r-2)^{m-2}\sum_{xy\in[m]^{(2)}}\alpha_{r}^{m^{\mathcal{G}_{\mathcal{B}}}_{xy}}$
$\displaystyle=(r-1)^{m}+m(r-1)^{m-1}+(r-2)^{m-2}H_{2}(m,\alpha_{r}),$

as required. ∎

###  3.2 Bad choice

In this section we prove the following result, which completes the proof of
Theorem 1.5 in the previous subsection.

######  Theorem 3.4.

For every $m\geq 0$, $r\geq 3$,

$\max\\{\operatorname{forb}(m,r,\mathcal{B})\colon\mathcal{B}\text{ is a bad
choice}\\}-(r-1)^{m}-m(r-1)^{m-1}\leq
H\left(m,\frac{r-1}{r-2}\right)\cdot(r-2)^{m-2}.$

Let us fix a (possibly bad) choice $\mathcal{B}$ on $[m]$ and a subset
$X\subset[m]$. Our goal is to bound $c(\mathcal{B},X)$ in a different way than
Lemma 3.1. To do this, we first modify the directed multigraph
$\mathcal{D}_{\mathcal{B}}(X)$ by adding some more edges according to the
following rules whenever possible.

  1. 1.

If $i,j,k\in X$ are distinct and $ij$, $jk$ are directed edges, then add
directed edge $ik$.

  2. 2.

If $i,j,k\in X$ are distinct, $B_{i,j,k}=I$ and $ij$ is a directed edge, then
add directed edge $ik$.

  3. 3.

If $i,j,k\in X$ are distinct, $B_{i,j,k}=I^{c}$ and $ij$ is a directed edge,
then add directed edge $kj$.

Denote this new directed multigraph by
$\overline{\mathcal{D}}_{\mathcal{B}}(X)$. It is easy to see that each
directed edge in $\overline{\mathcal{D}}_{\mathcal{B}}(X)$ is indeed a
$0$-implication on $X$ according to Definition 2.4. Also note that Rule 1
above guarantees that $\overline{\mathcal{D}}_{\mathcal{B}}(X)$ is transitive.

For not necessarily distinct $i,j\in X$, we say they are independent, and
denote it as $i\sim j$, if there exists no directed edge between them in
$\overline{\mathcal{D}}_{\mathcal{B}}(X)$.

######  Lemma 3.5.

The relation $\sim$ is an equivalence relation on $X$.

###### Proof.

$\sim$ is trivially symmetric. $\sim$ is reflexive as the rules above never
result in loops. Assume now that $i\sim j$ and $j\sim k$ for distinct
$i,j,k\in X$, which implies that $B_{i,j,k}=I\text{ or }I^{c}$ in
$\mathcal{B}$. Suppose $i\not\sim k$. Without loss of generality assume $ik$
is a directed edge in $\overline{\mathcal{D}}_{\mathcal{B}}(X)$. If
$B_{i,j,k}=I$, then Rule 2 above implies the existence of a directed edge
$ij$, contradicting $i\sim j$. If $B_{i,j,k}=I^{c}$, then Rule 3 above implies
the existence of a directed edge $jk$, contradicting $j\sim k$. ∎

Call any equivalence class in $X$ under relation $\sim$ with respect to
$\mathcal{B}$ a _block_. Observe that if $i$ and $j$ are in different blocks,
then there is a directed edge between them in
$\overline{\mathcal{D}}_{\mathcal{B}}(X)$.

######  Lemma 3.6.

Let $A,B$ be two blocks in $X$. If at least one of $A,B$ has size at least 2,
then edges between $A$ and $B$ all go in the same direction.

###### Proof.

Suppose not all edges between blocks $A$ and $B$ go in the same direction,
then we can find 3 vertices, without loss of generality $a_{1},a_{2}\in A$ and
$b\in B$, such that we have directed edges $a_{1}b$ and $ba_{2}$. By the
transitivity rule, we also have directed edge $a_{1},a_{2}$, contradicting $A$
is a block. ∎

Using a well-known result on tournaments, this implies that we can order the
blocks in $\overline{\mathcal{D}}_{\mathcal{B}}(X)$ as
$D_{1},D_{2},\cdots,D_{t}$, so that for all $\gamma<\gamma^{\prime}$ in $[t]$
and all $i\in D_{\gamma},j\in D_{\gamma}^{\prime}$, there is a directed $ij$
edge in $\overline{\mathcal{D}}_{\mathcal{B}}(X)$. If
$D_{\gamma},D_{\gamma^{\prime}}$ are singleton blocks, then there might be a
directed $ji$ edge as well, but we will not use them in the proofs below.

To get an upper bound on $c(\mathcal{B},X)$, the following observation will be
useful.

######  Lemma 3.7.

Let $D$ be a block and let $i,j\in D$ be distinct. Furthermore suppose $k$ is
in a block before $D$ in the ordering defined above. Then $B_{k,i,j}\neq
I^{c}$. Similarly, if $k^{\prime}$ is in a block after $D$, then
$B_{i,j,k^{\prime}}\neq I$.

###### Proof.

If $k$ is in a block before $D$, then we have directed $ki$ and $kj$ edges. If
$B_{k,i,j}=I^{c}$, then by Rule 3 we also have directed edges $ij,ji$,
contradicting $i\sim j$. Similarly, if $k^{\prime}$ is in a block after $D$,
then we have directed $ik^{\prime}$ and $jk^{\prime}$ edges. If
$B_{i,j,k^{\prime}}=I$, then by Rule 2 we also have directed edges $ij,ji$,
again contradicting $i\sim j$. ∎

We can now obtain a preliminary upper bound on $c(\mathcal{B},X)$. Let
$b(\mathcal{B},X)$ denote the number of blocks of size at least 2 on $X$ with
respect to the choice $\mathcal{B}$.

######  Lemma 3.8.

For every choice $\mathcal{B}$ on $[m]$ and $X\subset[m]$, we have

$c(\mathcal{B},X)\leq|X|+b(\mathcal{B},X)+1.$ (4)

###### Proof.

Let the blocks in $X$ be ordered as $D_{1},D_{2},\cdots,D_{t}$ as before. For
each $\gamma\in[t]$, let $C(\mathcal{B},X,\gamma)$ be the set of columns in
$C(\mathcal{B},X)$ that have their first 0 in block $D_{\gamma}$. We claim
that $|C(\mathcal{B},X,\gamma)|\leq|D_{\gamma}|+1$ if $|D_{\gamma}|\geq 2$.
Indeed, every column $c\in C(\mathcal{B},X,\gamma)$ contains only 1’s in each
block $D_{\beta}$ for $1\leq\beta<\gamma$ and only 0’s in each block
$D_{\beta^{\prime}}$ for $\gamma<\beta^{\prime}\leq t$. If $|D_{\gamma}|=1$,
then there is at most $1=|D_{\gamma}|$ such column. If $|D_{\gamma}|=2$, then
there are at most $3=|D_{\gamma}|+1$ such columns, namely those that are
$00,10$ or $01$ on $D_{\gamma}$.

Now assume $|D_{\gamma}|\geq 3$. Since $D_{\gamma}$ is a block, for every
distinct $i,j,k\in D_{\gamma}$ we have $B_{i,j,k}=I\text{ or }I^{c}$.

Case 1. There is a column $c\in C(\mathcal{B},X,\gamma)$ that contains at
least two 0’s and at least two 1’s on $D_{\gamma}$. Let $L\subset D_{\gamma}$
be the set of row indices on which $c$ is 0, while $R\subset D_{\gamma}$ be
the set of indices on which $c$ is 1. Then for all distinct $i,j,k\in
D_{\gamma}$, we have

  1. (i)

if $|\\{i,j,k\\}\cap L|=2$ then $B_{i,j,k}=I^{c}$,

  2. (ii)

if $|\\{i,j,k\\}\cap R|=2$ then $B_{i,j,k}=I$.

We claim that in this case every column $c^{\prime}\in
C(\mathcal{B},X,\gamma)$ is constant on $L$ and on $R$. Indeed, if there exist
$i,j\in L$ such that $c^{\prime}_{i}=0,c^{\prime}_{j}=1$, then $c^{\prime}$ is
constantly 0 on $R$ by (i). But then for any $k,k^{\prime}\in R$,
$c^{\prime}_{j}=1,c^{\prime}_{k}=c^{\prime}_{k^{\prime}}=0$, contradicting
(ii). Similarly, if there exist $j,k\in R$ such that
$c^{\prime}_{j}=0,c^{\prime}_{k}=1$, then $c^{\prime}$ is constantly 1 on $L$
by (ii). But then for any $i,i^{\prime}\in L$,
$c^{\prime}_{j}=0,c^{\prime}_{i}=c^{\prime}_{i^{\prime}}=1$, contradicting
(i). Hence, there are at most $3\leq|D_{\gamma}|+1$ columns in
$C(\mathcal{B},X,\gamma)$, namely the one that is 0 on both $L$ and $R$, the
one that is 0 on $L$, 1 on $R$, and the one that is 1 on $L$ and 0 on $R$.

Case 2. No column in $C(\mathcal{B},X,\gamma)$ contains at least two 0’s and
two 1’s on $D_{\gamma}$. We claim that
$|C(\mathcal{B},X,\gamma)|\leq|D_{\gamma}|+1$. This is true if all columns in
$C(\mathcal{B},X,\gamma)$ contain at least two 0’s on $D_{\gamma}$, as then
all of them contain at most one 1 on $D_{\gamma}$. Otherwise, there is a
column $c\in C(\mathcal{B},X,\gamma)$ that has only one 0, say at $i\in
D_{\gamma}$. For all other distinct $j,k\in D_{\gamma}$, $c_{j}=c_{k}=1$, so
$B_{i,j,k}=I$. Let $c^{\prime}$ be any other column in
$C(\mathcal{B},X,\gamma)$. If $c^{\prime}$ has at least two 0’s and a 1 on
$D_{\gamma}$, then it has exactly one 1 on $D_{\gamma}$, say at $i^{\prime}$.
If $i^{\prime}=i$, then for any other distinct $j,k\in D_{\gamma}$,
$c^{\prime}_{i}=1,c^{\prime}_{j}=c^{\prime}_{k}=0$, contradicting
$B_{i,j,k}=I$. If $i^{\prime}\not=i$, then for any other $j\in D_{\gamma}$,
$c^{\prime}_{i}=c^{\prime}_{j}=0,c^{\prime}_{i^{\prime}}=1$, again
contradicting $B_{i,i^{\prime},j}=I$. Hence, any such $c^{\prime}$ is either
all 0 or has one $0$, so there are at most $|D_{\gamma}|+1$ such columns in
this case as well.

Putting all these together, we have

$c(\mathcal{B},X)=1+\sum_{\gamma=1}^{t}|C(\mathcal{B},X,\gamma)|\leq
1+\sum_{\gamma=1}^{t}|D_{\gamma}|+b(\mathcal{B},X)=|X|+b(\mathcal{B},X)+1,$

where the sum counts all the columns with at least one 0 on $X$, and the extra
1 is the column with all 1’s on $X$. ∎

We need a strengthening of bound (4). Let us call a block $D_{\gamma}$
_special_ if there exist distinct $i,j\in D_{\gamma}$ such that either there
exists some $k$ in a block before $D_{\gamma}$ satisfying $B_{k,i,j}=I$, or
there exists some $k$ in a block after $D_{\gamma}$ such that
$B_{i,j,k}=I^{c}$. Let $s(\mathcal{B},X)$ be the number of special blocks.

######  Proposition 3.9.

For every choice $\mathcal{B}$ on $[m]$ and $X\subset[m]$, we have

$c(\mathcal{B},X)\leq|X|+b(\mathcal{B},X)-s(\mathcal{B},X)+1.$

###### Proof.

Order the blocks $D_{1},D_{2},\cdots,D_{t}$ in $X$ as before. Note that by
definition every special block has size at least 2. Let $S$ be the set of
indices $\gamma\in[t]$ such that $D_{\gamma}$ is a special block. Let
$S^{\prime}\subset S$ be the set of indices $\gamma$ such that $D_{\gamma}$ is
a special block of size at least 3 that falls under Case 1 in Lemma 3.8; in
other words, $\gamma\in S^{\prime}$ if $C(\mathcal{B},X,\gamma)$ contains a
column with at least two 0’s and at least two 1’s on $D_{\gamma}$.

For each special block $D_{\gamma}$ satisfying $\gamma\in S^{\prime}$, we
actually showed in the proof of Lemma 3.8 that the number of columns in
$C(\mathcal{B},X,\gamma)$ is at most $3\leq|D_{\gamma}|<|D_{\gamma}|+1$. This
improves the bound on $c(\mathcal{B},X)$ in Lemma 3.8 by at least
$|S^{\prime}|$.

Now for each $\gamma\in S\setminus S^{\prime}$, we will find a column
$c^{\gamma}$ that is counted in the upper bound proof of Lemma 3.8, but is
actually not in $C(\mathcal{B},X)$. Note that we will not require that
$c^{\gamma}\in C(\mathcal{B},X,\gamma)$, meaning $c^{\gamma}$ need not have
its first 0 in $D_{\gamma}$, but we will make sure that these $c^{\gamma}$ are
distinct for different $\gamma\in S\setminus S^{\prime}$. Therefore, the
collection $\\{c^{\gamma}\colon\gamma\in S\setminus S^{\prime}\\}$ of columns
together will improve the bound on $c(\mathcal{B},X)$ in Lemma 3.8 by
$|S\setminus S^{\prime}|$. We find $c^{\gamma}$ as follows. Since $D_{\gamma}$
is special, we can find $i,j\in D_{\gamma}$, and either some $k$ in a block
before $D_{\gamma}$ satisfying $B_{k,i,j}=I$ or some $k$ in a block after
$D_{\gamma}$ with $B_{i,j,k}=I^{c}$.

If $k$ is in some block before $D_{\gamma}$, let $c^{\gamma}$ be the column
given by the following table. Note that this column $c^{\gamma}$ is counted in
the upper bound proof of Lemma 3.8, but is not in $C(\mathcal{B},X)$ because
$B_{k,i,j}=I$.

$x$ | $x\in D_{\beta},\beta<\gamma$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma$
---|---|---
(including $x=k$) | (including $x=i,j$)
$c^{\gamma}_{x}$ | 1 | 0

Suppose instead $k$ is in some block after $D_{\gamma}$. Let $c^{\gamma}$ be
the column given by the following table. Again, $c^{\gamma}$ is counted in the
upper bound proof of Lemma 3.8, but is not in $C(\mathcal{B},X)$ because
$B_{i,j,k}=I^{c}$.

$x$ | $x\in D_{\beta},\beta\leq\gamma$ | $x\in D_{\beta^{\prime}},\beta^{\prime}>\gamma$
---|---|---
(including $x=i,j$) | (including $x=k$)
$c^{\gamma}_{x}$ | 1 | 0

Note that for $\gamma^{\prime}<\gamma$ in $S\setminus S^{\prime}$, columns
$c^{\gamma^{\prime}}$ and $c^{\gamma}$ obtained in this way are distinct,
unless $\gamma^{\prime}=\gamma-1$ and there exist $i,j\in D_{\gamma-1}$,
$i^{\prime},j^{\prime}\in D_{\gamma}$, $k$ in some block after $D_{\gamma-1}$
(possibly equal to $i^{\prime}$ or $j^{\prime}$) and $k^{\prime}$ in some
block before $D_{\gamma}$ (possibly equal to $i$ or $j$), such that
$D_{\gamma-1}$ is special because $B_{i,j,k}=I^{c}$ and $D_{\gamma}$ is
special because $B_{k^{\prime},i^{\prime},j^{\prime}}=I$. In what follows, for
each pair $\gamma-1,\gamma\in S\setminus S^{\prime}$ satisfying
$c^{\gamma-1}=c^{\gamma}$, we replace $c^{\gamma}$ with a different column
that is also counted in the upper bound proof of Lemma 3.8 but not in
$C(\mathcal{B},X)$, so that the new collection $\\{c^{\gamma}\colon\gamma\in
S\setminus S^{\prime}\\}$ is actually a set of $|S\setminus S^{\prime}|$
pairwise distinct columns. We need to separate into several cases.

Case 1. $k$ is in a block after $D_{\gamma}$. In this case, consider the two
columns defined below.

$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x\in D_{\gamma},x\not=j^{\prime}$ | $x=j^{\prime}$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$) | (including $x=i^{\prime}$) | (including $x=k$)
$\overline{c}^{\gamma}_{x}$ | 1 | 1 | 0 | 0
$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x\in D_{\gamma},x\not=j^{\prime}$ | $x=j^{\prime}$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$) | (including $x=i^{\prime}$) | (including $x=k$)
$\tilde{c}^{\gamma}_{x}$ | 1 | 0 | 1 | 0

Neither $\overline{c}^{\gamma}_{x}$ nor $\tilde{c}^{\gamma}_{x}$ is in
$C(\mathcal{B},X)$ as $B_{i,j,k}=I^{c}$. Both $\overline{c}^{\gamma}_{x}$ and
$\tilde{c}^{\gamma}_{x}$ have their first 0 in block $D_{\gamma}$, where
$\overline{c}^{\gamma}$ is all 1 except
$\overline{c}^{\gamma}_{j^{\prime}}=1$, while $\tilde{c}^{\gamma}$ is all 0
except $\tilde{c}^{\gamma}_{j^{\prime}}=1$. Hence, one of
$\overline{c}^{\gamma},\tilde{c}^{\gamma}$ is counted in the upper bound proof
of Lemma 3.8. Replace $c^{\gamma}$ with this one.

Case 2. $k\in D_{\gamma}$, $k\not=i^{\prime},j^{\prime}$. Once again, consider
the two columns defined below.

$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x\in D_{\gamma},x\not=k$ | $x=k$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$) | (including $x=i^{\prime},j^{\prime}$)
$\overline{c}^{\gamma}_{x}$ | 1 | 1 | 0 | 0
$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x\in D_{\gamma},x\not=k$ | $x=k$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$) | (including $x=i^{\prime},j^{\prime}$)
$\tilde{c}^{\gamma}_{x}$ | 1 | 0 | 1 | 0

Note that $\overline{c}^{\gamma}_{x}$ is not in $C(\mathcal{B},X)$ as
$B_{i,j,k}=I^{c}$ and $\tilde{c}^{\gamma}_{x}$ is not in $C(\mathcal{B},X)$ as
$B_{k^{\prime},i^{\prime},j^{\prime}}=I$. Both $\overline{c}^{\gamma}_{x}$ and
$\tilde{c}^{\gamma}_{x}$ have their first 0 in block $D_{\gamma}$, where
$\overline{c}^{\gamma}$ is all 1 except $\overline{c}^{\gamma}_{k}=0$, while
$\tilde{c}^{\gamma}$ is all 0 except $\tilde{c}^{\gamma}_{k}=1$. Hence, one of
$\overline{c}^{\gamma},\tilde{c}^{\gamma}$ is counted in the upper bound proof
of Lemma 3.8. Replace $c^{\gamma}$ with this one.

Case 3. $k\in D_{\gamma}$, $k=i^{\prime}$ or $j^{\prime}$, and
$|D_{\gamma}|=3$. Without loss of generality, say $k=j^{\prime}$, and let
$\ell$ be another index in $D_{\gamma}$ not equal to
$i^{\prime},j^{\prime},k$. Again, consider the two columns defined below.

$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x\in D_{\gamma},x\not=j^{\prime},k$ | $x=j^{\prime}=k$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$) | (including $x=i^{\prime},\ell$)
$\overline{c}^{\gamma}_{x}$ | 1 | 1 | 0 | 0
$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x\in D_{\gamma},x\not=\ell$ | $x=\ell$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$) | (including $x=i^{\prime},x=j^{\prime}=k$)
$\tilde{c}^{\gamma}_{x}$ | 1 | 0 | 1 | 0

Neither $\overline{c}^{\gamma}_{x}$ nor $\tilde{c}^{\gamma}_{x}$ is in
$C(\mathcal{B},X)$ as $B_{i,j,k}=I^{c}$. Both $\overline{c}^{\gamma}_{x}$ and
$\tilde{c}^{\gamma}_{x}$ have their first 0 in block $D_{\gamma}$, where
$\overline{c}^{\gamma}$ is all 1 except $\overline{c}^{\gamma}_{k}=1$, while
$\tilde{c}^{\gamma}$ is all 0 except $\tilde{c}^{\gamma}_{\ell}=1$. Hence, one
of $\overline{c}^{\gamma},\tilde{c}^{\gamma}$ is counted in the upper bound
proof of Lemma 3.8. Replace $c^{\gamma}$ with this one.

Case 4. $k\in D_{\gamma}$, $k=i^{\prime}$ or $j^{\prime}$, and
$|D_{\gamma}|=2$. Without loss of generality , assume $k=j^{\prime}$. Consider
the column defined below.

$x$ | $x\in D_{\beta},\beta\leq\gamma-1$ | $x=i^{\prime}$ | $x=j^{\prime}=k$ | $x\in D_{\beta^{\prime}},\beta^{\prime}\geq\gamma+1$
---|---|---|---|---
(including $x=i,j,k^{\prime}$)
$\overline{c}^{\gamma}_{x}$ | 1 | 1 | 0 | 0

Note that $\overline{c}^{\gamma}_{x}$ is not in $C(\mathcal{B},X)$ as
$B_{i,j,k}=I^{c}$. Since $|D_{\gamma}|=2$, $\overline{c}^{\gamma}_{x}$ is
counted in the upper bound proof of Lemma 3.8. Replace $c^{\gamma}$ with this
one.

We claim that after these replacements, all columns $c^{\gamma}$ for
$\gamma\in S\setminus S^{\prime}$ are pairwise distinct. Indeed, the columns
$c^{\gamma}$ that were unchanged are pairwise distinct, as otherwise one of
them would have been replaced. Moreover, all of these unchanged columns are
constant on each block. For each column $c^{\gamma}$ that was updated, it has
a unique non-constant block $D_{\gamma}$. Hence, the updated columns are
pairwise distinct and also distinct from all the unchanged ones, proving the
claim. Thus, $\\{c^{\gamma}\colon\gamma\in S\setminus S^{\prime}\\}$ is now a
set of $|S\setminus S^{\prime}|$ columns that we have counted in the proof of
Lemma 3.8 that are not actually in $C(\mathcal{B},X)$.

Hence, we have

$\displaystyle c(\mathcal{B},X)$
$\displaystyle=1+\sum_{\gamma=1}^{t}|C(\mathcal{B},X,\gamma)|$
$\displaystyle\leq 1+\sum_{\gamma\in[t]\setminus
S}|C(\mathcal{B},X,\gamma)|+\sum_{\gamma\in
S^{\prime}}|D_{\gamma}|+\left(\sum_{\gamma\in S\setminus
S^{\prime}}(|D_{\gamma}|+1)-|S\setminus S^{\prime}|\right)$
$\displaystyle=|X|+b(\mathcal{B},X)+1-|S^{\prime}|-|S\setminus
S^{\prime}|=|X|+b(\mathcal{B},X)-s(\mathcal{B},X)+1,$

as required. ∎

We are now ready to prove Theorem 3.4, which completes the proof of Theorem
1.5.

###### Proof of Theorem 3.4.

Let $\mathcal{B}$ be any bad choice on $[m]$. It suffices to find a good
choice $\mathcal{B}^{\prime}$ on $[m]$ such that for all $X\subset[m]$,

$|X|+b(\mathcal{B},X)-s(\mathcal{B},X)+1\leq n(\mathcal{B}^{\prime},X)+|X|+1,$

where $n(\mathcal{B}^{\prime},X)$ is calculated as in Lemma 3.1. We will do
this by replacing each $B_{i,j,k}\in\mathcal{B}$ that is equal to $I$ or
$I^{c}$ with a configuration of $A_{2}$ to obtain a good choice
$\mathcal{B}^{\prime}$, such that for any $X\subset[m]$, every non-special
block on $X$ of size at least 2 contains a non-edge of
$\mathcal{D}_{\mathcal{B^{\prime}}}(X)$. Since there are
$b(\mathcal{B},X)-s(\mathcal{B},X)$ non-special block of size at least 2, we
get $n(\mathcal{B}^{\prime},X)\geq b(\mathcal{B},X)-s(\mathcal{B},X)$, as
required.

Order the blocks determined by $\mathcal{B}$ on $[m]$ as usual and call them
_original blocks_. Furthermore, fix an arbitrary ordering of the elements
inside each original block so that together with the ordering of the blocks,
we obtain a total order on $[m]$. Denote this order by $\prec$. For all
triples $i\prec j\prec k$ in $[m]$ such that $B_{i,j,k}=I$ or $I^{c}$, we
replace $B_{i,j,k}$ with $B^{\prime}_{i,j,k}$, which is a configuration of
$A_{2}$ that corresponds to 0-implications from $i$ to $k$ and from $j$ to
$k$. We claim that the choice $\mathcal{B}^{\prime}$ obtained in this way
works.

Indeed, let $X\subset[m]$ and let $D$ be a non-special block of size at least
2 on $X$ induced by $\mathcal{B}$. First suppose $D=\\{i,j\\}$ has size 2.
Since $D$ is a block, there is no directed $ij$ or $ji$ edge in
$\overline{\mathcal{D}}_{\mathcal{B}}(X)$. As every directed edge in
$\mathcal{D}_{\mathcal{B}}(X)$ is in
$\overline{\mathcal{D}}_{\mathcal{B}}(X)$, there is also no directed $ij$ or
$ji$ edge in $\mathcal{D}_{\mathcal{B}}(X)$. Moreover, for any $k$ not in $D$,
as $D$ is a non-special block, we have that $B_{i,j,k}$ is a configuration of
$A_{1}$ or $A_{2}$ that corresponds to no directed $ij$ or $ji$ edge. This
means that $B_{i,j,k}=B^{\prime}_{i,j,k}$ is unchanged for every $k$. Thus,
the replacements do not introduce any new directed $ij$ or $ji$ edge, so $ij$
is a non-edge of $\mathcal{D}_{\mathcal{B^{\prime}}}(X)$ as required.

On the other hand, if $|D|\geq 3$, let $i\prec j$ be the two smallest elements
in $D$ with respect to the order $\prec$. As above, there is no directed $ij$
or $ji$ edge in $\mathcal{D}_{\mathcal{B}}(X)$, and
$B_{i,j,k}=B^{\prime}_{i,j,k}$ for all $k\not\in D$. Suppose that
$B_{i,j,k}=I\text{ or }I^{c}$ for some $k\in D$, then $i\prec j\prec k$ and by
construction, replacing $B_{i,j,k}$ with $B_{i,j,k}^{\prime}$ adds directed
$ik$ and $jk$ edges to $\mathcal{D}_{\mathcal{B}}(X)$, but not any directed
$ij$ or $ji$ edge. Since this is true for all such $k\in D$, $ij$ forms a non-
edge in $\mathcal{D}_{\mathcal{B^{\prime}}}(X)$, as required. ∎

##  4 Upper bounds

In this section, we focus on upper bounds. For simplicity, we write
$H(m)=H(m,2)$ and $w(\mathcal{G})=w(\mathcal{G},2)$ throughout this section.
We first obtain an upper bound for $H(m)$ by proving Theorem 1.6. The values
of $H(m)$ and $h(m)=H(m)/m2^{m-1}$ (rounded to 3 decimals) for $1\leq m\leq 6$
are given in the table below.

$m$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
$H(m)$ | 0 | 1 | 4 | 12 | 30 | 73
$h(m)$ | 0.000 | 0.250 | 0.333 | 0.375 | 0.375 | 0.380

As the number of TCM on $[m]$ grows exponentially in $m$, it quickly becomes
infeasible to calculate $H(m)$ and $h(m)$ by brute force. Instead, we
introduce the concept of closed sets in Section 4.1, which helps us decompose
and better analyse triangular choice multigraphs. In Section 4.2, we prove a
key lemma which shows that there exists an extremal TCM such that all of its
maximal closed sets have size at least 2. Then, in Section 4.3, we use this
lemma to prove Theorem 1.6, and deduce from it Theorem 1.7, which gives an
upper bound on $\operatorname{forb}(m,r,M)$ for all $r\geq 3$.

###  4.1 Closed sets

######  Definition 4.1.

Given a triangular choice multigraph $\mathcal{G}$ on $[m]$, a subset $S$ of
$[m]$ is closed if for all distinct $x,y\in S$ and $z\not\in S$, the edge $xy$
is chosen in triangle $xyz$. A closed set $S$ is maximal if the only proper
closed subset of $[m]$ containing $S$ is $S$ itself.

For example, if $\mathcal{G}$ is a TCM on $[m]$, then the empty set, all
singletons and $[m]$ itself are all trivially closed. A two element set
$\\{x,y\\}$ is closed if and only if $m_{xy}=m-2$. A three element set
$\\{x,y,z\\}$ is closed if and only if two of $m_{xy},m_{xz},m_{yz}$ are equal
to $m-3$ and the other is equal to $m-2$. Figure 3 illustrates the closed sets
in a TCM with 5 vertices.

The following lemma shows that maximal closed sets provide a nice
decomposition of $\mathcal{G}$.

######  Lemma 4.2.

Let $S_{1},S_{2}$ be closed sets in $[m]$. If $S_{1}\cap S_{2}\neq\emptyset$,
then either $S_{1}\subset S_{2}$ or $S_{2}\subset S_{1}$. Consequently, the
maximal closed sets in $[m]$ form a partition of $[m]$.

###### Proof.

Let $x\in S_{1}\cap S_{2}$. If neither $S_{1}\subset S_{2}$ nor $S_{2}\subset
S_{1}$ holds, then there exists $y\in S_{1}\setminus S_{2}$ and $z\in
S_{2}\setminus S_{1}$. Now, $x,y\in S_{1}$ and $z\not\in S_{1}$ implies that
in triangle $xyz$ edge $xy$ is chosen, while $x,z\in S_{2}$ and $y\not\in
S_{2}$ implies that in triangle $xyz$ edge $xz$ is chosen, a contradiction. ∎

12345$m_{12}=3$$m_{23}=2$$m_{45}=3$$\small{m_{13}=2}$ Figure 3: An example TCM
$G$ with its closed sets identified. There are two maximal closed sets,
identified in dashed red, with other non-maximal closed sets being singletons
(trivially closed) or identified in dotted black.

###  4.2 Every maximal closed set has size at least 2

Recall that for every TCM $\mathcal{G}$ on $[m]$, we defined

$w(\mathcal{G})=w(\mathcal{G},2)=\sum_{xy\in[m]^{(2)}}2^{m^{\mathcal{G}}_{xy}},$

so that $H(m)=H(m,2)=\max\\{w(\mathcal{G})\colon\mathcal{G}\text{ is a TCM on
}[m]\\}$. The goal in this subsection is to prove that there exists a TCM
$\mathcal{G}$ on $[m]$ satisfying $w(\mathcal{G})=H(m)$, such that each of its
vertices is contained in a closed set of size 2 or 3. In particular, this
means that its vertices are partitioned into maximal closed sets of sizes at
least 2. The plan is to show that if $\mathcal{G}$ is an extremal TCM on
$[m]$, then either all vertices in $\mathcal{G}$ are contained in closed sets
of size 2 or 3, or we can change some edge choices to obtain another extremal
TCM $\mathcal{G}^{\prime}$ on $[m]$ that has strictly more vertices contained
in closed sets of size 2 or 3.

The next few lemmas identify several types of changes in edge choices we could
perform on a TCM $\mathcal{G}$ that does not decrease, or even strictly
increase, $w(\mathcal{G})$.

######  Lemma 4.3.

Let $\mathcal{G}$ be a TCM on $[m]$. Suppose $x,y,z$ are distinct vertices
such that $m_{xy}\geq m_{xz}-1$ and edge $xz$ is chosen in triangle $xyz$.
Then swapping the edge choice from $xz$ to $xy$ does not decrease
$w(\mathcal{G})$, and strictly increases it if $m_{xy}\geq m_{xz}$.

Therefore, if $\mathcal{G}$ is extremal and $x,y,z$ are distinct, then
$m_{xy}>m_{xz},m_{yz}$ if and only if $xy$ is the edge chosen in triangle
$xyz$.

###### Proof.

For the first part, let $\mathcal{G}^{\prime}$ be the new TCM obtained after
changing the edge choice on $xyz$ from $xz$ to $xy$. Then we have

$\displaystyle w(\mathcal{G}^{\prime})-w(\mathcal{G})$
$\displaystyle=2^{m_{xz}-1}+2^{m_{xy}+1}-2^{m_{xz}}-2^{m_{xy}}$
$\displaystyle=2^{m_{xy}}-2^{m_{xz}-1}$ $\displaystyle\geq
2^{m_{xz}-1}-2^{m_{xz}-1}=0,$

with equality only if $m_{xy}=m_{xz}-1$.

Now assume $\mathcal{G}$ is extremal. If $m_{xy}>m_{xz},m_{yz}$ and the edge
$e$ chosen on $xyz$ is $xz$ or $yz$, then by the above swapping the choice
from $e$ to $xy$ strictly increases $w(\mathcal{G})$, a contradiction.
Conversely, if $xy$ is chosen on $xyz$ but $m_{xy}\leq m_{e}$, where $e$ is
$xz$ or $yz$, then again by the above, switching the choice from $xy$ to $e$
strictly increases $w(\mathcal{G})$, a contradiction. ∎

######  Lemma 4.4.

Let $\mathcal{G}$ be a TCM on $[m]$, and let $x,y,z,w$ be distinct vertices in
$\mathcal{G}$. Assume that $m_{xy}=m_{xz}+1=m_{xw}+1$ and edge $xy$ is chosen
in both triangles $xyz$ and $xyw$. Let $\mathcal{G}^{\prime}$ be the TCM
obtained swapping the choice from edge $xy$ to edge $xz$ in triangle $xyz$ and
swapping from from $xy$ to $xw$ in triangle $xyw$, then
$w(\mathcal{G}^{\prime})>w(\mathcal{G})$.

###### Proof.

We have

$\displaystyle w(\mathcal{G}^{\prime})-w(\mathcal{G})$
$\displaystyle=2^{m_{xy}-2}+2^{m_{xz}+1}+2^{m_{xw}+1}-2^{m_{xy}}-2^{m_{xz}}-2^{m_{xw}}$
$\displaystyle=2^{m_{xy}-2}+2^{m_{xy}}+2^{m_{xy}}-2^{m_{xy}}-2^{m_{xy}-1}-2^{m_{xy}-1}$
$\displaystyle=2^{m_{xy}-2}>0,$

as required. ∎

######  Lemma 4.5.

Let $\mathcal{G}$ be a TCM on $[m]$, and let $t\geq 4$ be an integer. Suppose
there exist distinct vertices $x$ and $y_{3},\cdots,y_{t-1}$ in $\mathcal{G}$
such that

  * •

$m_{xy_{i}}=m-i$ for all $3\leq i\leq t-1$,

  * •

$y_{3},\cdots,y_{t-1}$ all belong to distinct closed sets
$Y_{3},\cdots,Y_{t-1}$ of size at least $2$,

  * •

$x$ is not in a closed set of size 2, and $x\not\in Y_{3}\cup\cdots\cup
Y_{t-1}$.

Then, $|Y_{i}|=2$ for every $3\leq i\leq t-1$. Furthermore, if either

  1. 1.

there exists $y_{t}\in Y_{i}$ for some $3\leq i\leq t-1$ such that
$m_{xy_{t}}=m-t$, or

  2. 2.

there exist distinct $y_{t},y_{t}^{\prime}$ such that
$m_{xy_{t}}=m_{xy^{\prime}_{t}}=m-t$.

Then, there is a series of swaps of edge choices that strictly increases
$w(\mathcal{G})$.

###### Proof.

First, we use induction to show that for each $3\leq i\leq t-1$, $|Y_{i}|=2$,
and the edge $xy_{i}$ is chosen in the triangle $xy_{i}y$ if and only if
$y\not\in\\{x,y_{3},\cdots,y_{i-1}\\}\cup Y_{i}$. For $i=3$, since $x\not\in
Y_{3}$ and $Y_{3}$ is closed, the edge $xy_{3}$ is not chosen in triangle
$xy_{3}y$ for any other vertex $y\in Y_{3}$. Since $m_{xy_{3}}=m-3$, we must
have $|Y_{3}|=2$ and that $xy_{3}$ is chosen in triangle $xy_{3}y$ for all
$y\not\in\\{x\\}\cup Y_{3}$. Suppose now $i\geq 4$ and this is true for all
smaller $i\geq 3$. Then by the induction hypothesis, the edge $xy_{i}$ is not
chosen in triangles $xy_{i}y_{j}$ for all $3\leq j<i$ and also not in
triangles $xy_{i}y$ for all $y\in Y_{i}$ not equal to $y_{i}$. So
$m-i=m_{xy_{i}}\leq m-2-(i-3)-(|Y_{i}|-1)$, implying that $|Y_{i}|=2$ and that
edge $xy_{i}$ is chosen in triangle $xy_{i}y$ for all
$y\not\in\\{x,y_{3},\cdots,y_{i-1}\\}\cup Y_{i}$, as required.

In the first case, the assumption implies, in particular, that
$Y_{i}=\\{y_{i},y_{t}\\}$. From above, $xy_{t}$ is not chosen in triangle
$xy_{t}y_{j}$ for all $3\leq j\leq t-1$. But $m_{xy_{t}}=m-t$, so there exists
a vertex $z\not\in\\{x,y_{3},\cdots,y_{t}\\}$ such that the edge $xy_{t}$ is
not chosen in triangle $xy_{t}z$. Let $e$ be the edge that is chosen in
$xy_{t}z$, so $e=xz$ or $y_{t}z$. If $m_{e}\leq m_{xy_{t}}$, then swapping the
choice from $e$ to $xy_{t}$ strictly increases $w(\mathcal{G})$ by Lemma 4.3,
as required, so we can assume $m_{e}>m_{xy_{t}}$. Say $m_{e}=m-k$ with $t>k$.
Since $x$ is not in a closed set of size 2, we have $m_{xz}\leq m-3$. Since
$Y_{i}$ is a closed set of size 2, $m_{y_{i}y_{t}}=m-2$, which means edge
$y_{i}y_{t}$ is chosen in triangle $y_{i}y_{t}z$. Hence, $m_{y_{t}z}\leq m-3$
and so $k\geq 3$. Apply the first part of Lemma 4.3 in triangles
$xy_{t}y_{t-1},xy_{t}y_{t-2},\cdots,xy_{t}y_{k}$ successively in this order,
swapping the choice from $xy_{j}$ to $xy_{t}$ for each $k\leq j\leq t-1$,
which changes $m_{xy_{t}}$ to $m-k$ while maintaining the value of
$w(\mathcal{G})$. Now we can swap the choice in triangle $xy_{t}z$ from $e$ to
$xy_{t}$, which by Lemma 4.3 strictly increases $w(\mathcal{G})$, as required.

In the second case, note that edge $xy_{t-1}$ is chosen in both triangles
$xy_{t-1}y_{t}$ and $xy_{t-1}y_{t}^{\prime}$ and
$m_{xy_{t-1}}=m-t+1=m_{xy_{t}}+1=m_{xy_{t}^{\prime}}+1$. Hence, we may apply
the two swaps given by Lemma 4.4 to strictly increase $w(\mathcal{G})$. ∎

The next lemma, roughly speaking, states that a vertex cannot have many edges
with large multiplicities incident with it.

######  Lemma 4.6.

Let $\mathcal{G}$ be a TCM on $[m]$ and let $x$ be a vertex in $\mathcal{G}$.
For every $j\geq 0$, let $d_{j}(x)$ denote the number of edges of multiplicity
$j$ incident with $x$. Then for every $0\leq t\leq m-1$ we have

$\sum_{j\geq t}d_{j}(x)\leq m-1-t$

###### Proof.

If there exists no edge incident with $x$ with multiplicity at least $t$ in
$\mathcal{G}$, then we are done. Otherwise, let $xy$ be an edge minimising
$m_{xy}$, subjected to the condition that $m_{xy}\geq t$. Then there exists
$m_{xy}\geq t$ vertices $z\not=x,y$ in $\mathcal{G}$ such that in triangle
$xyz$ the edge $xy$ is chosen. On the other hand, by Lemma 4.3, for any
$z\not=x,y$ satisfying $m_{xz}\geq m_{xy}$, the edge $xy$ is not chosen in
triangle $xyz$. There are $\sum_{j\geq m_{xy}}d_{j}(x)-1=\sum_{j\geq
t}d_{j}(x)-1$ such $z$. Hence, $\sum_{j\geq t}d_{j}(x)-1+m_{xy}\leq m-2$,
which gives $\sum_{j\geq t}d_{j}(x)\leq m-1-m_{xy}\leq m-1-t$. ∎

We are now ready to prove the main result of this subsection.

######  Proposition 4.7.

There exists a triangular choice multigraph $\mathcal{G}$ on $[m]$ with
$w(\mathcal{G})=H(m)$, such that every vertex in $\mathcal{G}$ is contained in
a closed set of size 2 or 3.

###### Proof.

Let $\mathcal{G}$ be a TCM on $[m]$ satisfying $w(\mathcal{G})=H(m)$ and
minimising the size of the set $S\subset[m]$ of vertices that are not
contained in a closed set of size 2 or 3. It suffices to show that $|S|=0$.
For a contradiction, suppose $|S|\geq 1$.

Case 1. $|S|\geq 2$. Let $xx^{\prime}$ be an edge between vertices in $S$
maximising $m_{xx^{\prime}}$, and suppose $m_{xx^{\prime}}=m-t$. Using Lemma
4.3 and the maximality of $m_{xx^{\prime}}$ and $w(\mathcal{G})$, we have that
if $z$ is another vertex such that edge $xx^{\prime}$ is not chosen on
triangle $xx^{\prime}z$, then $z\not\in S$. We may also assume that every edge
adjacent to either $x$ or $x^{\prime}$ has multiplicity at most $m-3$, as if,
say, $m_{xz}=m-2$ for some $z\not=x$, then $\\{x,z\\}$ is a closed set of size
2, contradicting $x\in S$. In particular, $t\geq 3$. If $t=3$, let $z$ be the
unique vertex such that edge $xx^{\prime}$ is not chosen in triangle
$xx^{\prime}z$. Say $xz$ is chosen in triangle $xx^{\prime}z$, then by Lemma
4.3, $m_{xz}>m_{xx^{\prime}}$, so $m_{xz}=m-2$. Thus, $\\{x,z\\}$ is a closed
set of size 2, contradicting $x\in S$. Hence, $t\geq 4$. We have two further
subcases.

Case 1.1. For at least one of $x$ and $x^{\prime}$, say $x$, there exist two
vertices $z,z^{\prime}$ such that $m_{xz}=m_{xz^{\prime}}=m-3$. By Lemma 4.3,
$m_{xz}=m_{xz^{\prime}}$ implies that $zz^{\prime}$ is the edge chosen in
triangle $xzz^{\prime}$ and $m_{zz^{\prime}}=m-2$. It follows that
$\\{x,z,z^{\prime}\\}$ form a closed set of size 3, contradicting $x\in S$.

Case 1.2. For each of $x$ and $x^{\prime}$, there is at most one edge of
multiplicity $m-3$ incident with it. Suppose there are $r-2$ vertices $y$ such
that edge $xy$ is chosen in triangle $xx^{\prime}y$. Let these $r-2$ vertices
be $y_{3},\cdots,y_{r}$ and assume that $m-3\geq m_{xy_{3}}\geq\cdots\geq
m_{xy_{r}}$. We claim that

$\sum_{j=3}^{r}2^{m_{xy_{j}}}\leq 2^{m-2}-2^{m-r}.$

If $r=3$ this follows from $m_{xy_{3}}\leq m-3$. If $r=4$, this follows from
$m_{xy_{4}}\leq m-4$, as otherwise there are two edges of multiplicities $m-3$
incident with $x$. For the $r\geq 5$ case, first suppose that $m_{xy_{j}}\geq
m-j$ for all $3\leq j\leq r$. Then using $w(\mathcal{G})=H(m)$ and Lemma 4.5,
we see inductively that $m_{xy_{j}}=m-j$ for all $3\leq j\leq r$ and each
$y_{j}$ belongs to a different closed set of size 2. Thus,
$\sum_{j=3}^{r}2^{m_{xy_{j}}}=\sum_{j=3}^{r}2^{m-j}=2^{m-2}-2^{m-r}$. If this
is not true, let $3\leq i\leq r$ be the smallest index such that
$m_{xy_{i}}<m-i$. Again by Lemma 4.5, we have $m_{xy_{j}}=m-j$ for all $3\leq
j\leq i-1$. By Lemma 4.6, for all $3\leq j\leq r$, there are at most $j-1$
edges incident with $x$ that has multiplicity at least $m-j$. Hence, the
sequence $(d_{j})_{j=3}^{r}$ given by $d_{j}=m-j$ for all $3\leq j\leq i-1$,
$d_{j}=m-i-1$ for all $i\leq j\leq i+2$ and $d_{j}=m-j+1$ for all $i+3\leq
j\leq r$ dominates the sequence $(m_{xy_{j}})_{j=3}^{r}$, in the sense that
$d_{j}\geq m_{xy_{j}}$ for all $3\leq j\leq r$. Thus,
$\sum_{j=3}^{r}2^{m_{xy_{j}}}\leq\sum_{j=3}^{r}2^{d_{j}}=2^{m-2}-2^{m-r+1}$,
as required.

Similarly, suppose there are $s-2$ vertices $y^{\prime}$ such that edge
$x^{\prime}y^{\prime}$ is chosen in triangle $xx^{\prime}y^{\prime}$. Let them
be $y^{\prime}_{3},\cdots,y^{\prime}_{s}$ and assume that $m-3\geq
m_{x^{\prime}y^{\prime}_{3}}\geq\cdots\geq m_{x^{\prime}y^{\prime}_{s}}$, then
$\sum_{j=3}^{s}2^{m_{x^{\prime}y^{\prime}_{j}}}\leq 2^{m-2}-2^{m-s}$. Note
that as $y_{3},\cdots,y_{r},y^{\prime}_{3},\cdots,y^{\prime}_{s}$ are all the
vertices $y$ such that edge $xx^{\prime}$ is not chosen in triangle
$xx^{\prime}y$, we have $r-2+s-2=t-2$. Consider the TCM $\mathcal{G}^{\prime}$
obtained from $\mathcal{G}$ by choosing edge $xx^{\prime}$ instead of $xy_{j}$
in triangles $xx^{\prime}y_{j}$ for all $3\leq j\leq r$ and choosing edge
$xx^{\prime}$ instead of $x^{\prime}y^{\prime}_{j}$ in triangles
$xx^{\prime}y^{\prime}_{j}$ for all $3\leq j\leq s$. Then

$\displaystyle w(\mathcal{G}^{\prime})-w(\mathcal{G})$
$\displaystyle=2^{m-2}+\sum_{j=3}^{r}2^{m_{xy_{j}}-1}+\sum_{j=3}^{s}2^{m_{x^{\prime}y^{\prime}_{j}}-1}-2^{m-t}-\sum_{j=3}^{r}2^{m_{xy_{j}}}-\sum_{j=3}^{s}2^{m_{x^{\prime}y^{\prime}_{j}}}$
$\displaystyle=2^{m-2}-2^{m-t}-\sum_{j=3}^{r}2^{m_{xy_{j}}-1}-\sum_{j=3}^{s}2^{m_{x^{\prime}y^{\prime}_{j}}-1}$
$\displaystyle\geq 2^{m-2}-2^{m-t}-(2^{m-3}-2^{m-r-1})-(2^{m-3}-2^{m-s-1})$
$\displaystyle=2^{m-r-1}+2^{m-s-1}-2^{m-r-s+2}>0,$

contradicting $w(\mathcal{G})=H(m)$.

Case 2. $|S|=1$. Let $x$ be the unique vertex in $S$ and let $z$ be a vertex
maximising $m_{xz}$. Since $|S|=1$, $z$ is in a closed set of size 2 or 3. Let
$m_{xz}=m-t$. If $t=2$, we have a contradiction as $\\{x,z\\}$ is a size 2
closed set. So $t\geq 3$.

Case 2.1. $z$ is in a closed set $C$ of size 3. Let $y_{3},y_{4}$ be the other
two vertices in $C$. Two of edges $zy_{3},zy_{4},y_{3}y_{4}$ have multiplicity
$m-3$ while the other has multiplicity $m-2$. If $m_{y_{3}y_{4}}=m-2$, do
nothing. If $m_{y_{3}y_{4}}=m-3$, then $y_{3}y_{4}$ is not chosen in triangle
$zy_{3}y_{4}$. Change the choice on $zy_{3}y_{4}$ so that $y_{3}y_{4}$ is
chosen. Then $m_{y_{3}y_{4}}=m-2$ and $w(\mathcal{G})$ is unchanged. In both
cases, we now have $m_{zy_{3}}=m_{zy_{4}}=m-3$. Also note that $t\geq 4$ as
edge $xz$ is not chosen in the triangles $xzy_{3}$, $xzy_{4}$. There are $t-2$
vertices $y$ such that edge $xz$ is not chosen in triangle $xzy$. Using
$w(\mathcal{G})=H(m)$ and Lemma 4.3, we see that for every such $y$, edge $zy$
is chosen in triangle $xzy$, as otherwise $m_{xy}>m_{xz}$, contradicting the
maximality of $m_{xz}$. Let these $t-2$ vertices be $y_{3},\cdots,y_{t}$ and
assume that $m_{zy_{3}}\geq\cdots\geq m_{zy_{t}}$. By Lemma 4.6,
$(m_{zy_{j}})_{j=3}^{t}$ is dominated by the sequence $(d_{j})_{j=3}^{t}$,
where $d_{3}=m-3$ and $d_{j}=m-j+1$ for all $4\leq j\leq t$. Thus,
$\sum_{j=3}^{t}2^{m_{zy_{j}}}\leq\sum_{j=3}^{t}2^{d_{j}}=2^{m-2}+2^{m-3}-2^{m-t+1}$.
Consider the TCM $\mathcal{G}^{\prime}$ obtained from $\mathcal{G}$ by picking
edge $xz$ instead of $zy_{j}$ in triangle $xzy_{j}$ for every $3\leq j\leq t$.
Then

$\displaystyle w(\mathcal{G}^{\prime})-w(\mathcal{G})$
$\displaystyle=2^{m-2}+\sum_{j=3}^{t}2^{m_{zy_{j}}-1}-2^{m-t}-\sum_{j=3}^{t}2^{m_{zy_{j}}}$
$\displaystyle=2^{m-2}-2^{m-t}-\sum_{j=3}^{t}2^{m_{zy_{j}}-1}$
$\displaystyle\geq 2^{m-2}-2^{m-t}-2^{m-3}-2^{m-4}+2^{m-t}$
$\displaystyle=2^{m-4}>0,$

contradicting $w(\mathcal{G})=H(m)$.

Case 2.2. $z$ is not in a closed set of size 3, so it is in a closed set $C$
of size 2. Let $z^{\prime}$ be the other vertex in $C$. Like in Case 2.1, if
$y$ is a vertex such that edge $xz$ is not chosen in triangle $xzy$, then $zy$
must be the edge chosen. Let the $t-2$ vertices $y$ such that edge $zy$ is
chosen in triangle $xzy$ be $y_{3},\cdots,y_{t}$, and assume that
$m_{zy_{3}}\geq\cdots\geq m_{zy_{t}}$. Then $z^{\prime}=y_{3}$ as
$m_{zz^{\prime}}=m-2$. We claim that $t=3$. Indeed, if $t\geq 4$, let
$C^{\prime}$ be a closed set of size 2 or 3 containing $y_{4}$. $C^{\prime}$
must be disjoint from $C$ as otherwise Lemma 4.2 implies that
$C^{\prime}=C\cup\\{y_{4}\\}=\\{z,z^{\prime},y_{4}\\}$, contradicting that $z$
is not contained in a closed set of size 3. Thus, $m_{zy_{4}}\leq m-4$ as edge
$zy_{4}$ is not chosen in triangle $zy_{4}z^{\prime}$ and
$zy_{4}y_{4}^{\prime}$, where $y_{4}^{\prime}$ is any vertex in $C^{\prime}$
other than $y_{4}$. By Lemma 4.6, $(m_{zy_{j}})_{j=3}^{t}$ is dominated by the
sequence $(d_{j})_{j=3}^{t}$, where $d_{3}=m-2$, $d_{4}=m-4$ and $d_{j}=m-j+1$
for all $5\leq j\leq t$. Thus,
$\sum_{j=4}^{t}2^{m_{zy_{j}}}\leq\sum_{j=4}^{t}2^{d_{j}}=2^{m-3}+2^{m-4}-2^{m-t+1}$.
Consider the TCM $\mathcal{G}^{\prime}$ obtained from $\mathcal{G}$ by picking
edge $xz$ instead of $zy_{j}$ in triangles $xzy_{j}$ for every $4\leq j\leq
t$. Then

$\displaystyle w(\mathcal{G}^{\prime})-w(\mathcal{G})$
$\displaystyle=2^{m-3}+\sum_{j=4}^{t}2^{m_{zy_{j}}-1}-2^{m-t}-\sum_{j=4}^{t}2^{m_{zy_{j}}}$
$\displaystyle=2^{m-3}-2^{m-t}-\sum_{j=4}^{t}2^{m_{zy_{j}}-1}$
$\displaystyle\geq 2^{m-3}-2^{m-t}-2^{m-4}-2^{m-5}+2^{m-t}$
$\displaystyle=2^{m-5}>0,$

contradicting $w(\mathcal{G})=H(m)$.

Hence, $t=3$ and $m_{xz}=m-3$. If $m_{xz^{\prime}}=m-3$, then
$\\{x,z,z^{\prime}\\}$ is a closed set of size 3, a contradiction. Thus,
$m_{xz^{\prime}}=m-t^{\prime}$ for some $t^{\prime}\geq 4$. Let
$w_{3},\cdots,w_{r}$ be all the vertices such that edge $xw_{j}$ is chosen in
the triangle $xz^{\prime}w_{j}$ for all $3\leq j\leq r$, and assume that
$m_{xw_{3}}\geq\cdots\geq m_{xw_{r}}$. In particular, $w_{3}=z$ and
$m-3=m_{xw_{3}}$. We claim that

$\sum_{j=4}^{r}2^{m_{xw_{j}}}\leq 2^{m-3}-2^{m-r}.$

This is trivial if $r=3$. If $r\geq 4$, since $m_{xz}=m-3$ and
$m_{zz^{\prime}}=m-2$, the edge $xz$ is chosen in triangle $xzw$ for all
$w\not=z^{\prime}$. So by Lemma 4.3, $m_{xw_{4}}\leq m_{xz}-1=m-4$, which in
particular proves the case when $r=4$. Suppose now $r\geq 5$. If
$m_{xw_{4}}=m_{xw_{5}}=m-4$, then by Lemma 4.4, there is a swap of choice that
strictly increase $w(\mathcal{G})$, a contradiction. Thus, $m_{xw_{5}}\leq
m-5$, and this allows us to use the same argument as in Case 1.2 to show that
$\sum_{j=4}^{r}2^{m_{xw_{j}}}\leq 2^{m-3}-2^{m-r}$.

Now let $w^{\prime}_{3},\cdots,w^{\prime}_{s}$ be all the vertices such that
edge $z^{\prime}w^{\prime}_{j}$ is chosen in the triangle
$xz^{\prime}w^{\prime}_{j}$ for all $3\leq j\leq s$, and assume that
$m_{z^{\prime}w^{\prime}_{3}}\geq\cdots\geq m_{z^{\prime}w^{\prime}_{s}}$. In
particular, $w^{\prime}_{3}=z$ and $m_{z^{\prime}w^{\prime}_{3}}=m-2$. We
claim that

$\sum_{j=4}^{s}2^{m_{z^{\prime}w^{\prime}_{j}}}\leq 2^{m-3}-2^{m-s}.$

This is trivial if $s=3$. If $s\geq 4$, $m_{z^{\prime}w^{\prime}_{4}}\not=m-2$
as $m_{z^{\prime}z}=m-2$. If $m_{z^{\prime}w^{\prime}_{4}}=m-3$, then as
$m_{z^{\prime}z}=m-2$ and $m_{xz}=m-3$, Lemma 4.4 implies there is an edge
swap that strictly increases $w(\mathcal{G})$, a contradiction. Hence
$m_{z^{\prime}w^{\prime}_{4}}\leq m-4$, and the $s=4$ case is proved. Assume
now $s\geq 5$. If
$m_{z^{\prime}w^{\prime}_{4}}=m_{z^{\prime}w^{\prime}_{5}}=m-4$, then we
change the edge choice on triangle $xzz^{\prime}$ from $zz^{\prime}$ to $xz$.
This maintains the value of $w(\mathcal{G})$, but now $m_{zz^{\prime}}=m-3$,
so we can apply Lemma 4.4 to find swap of choice that strictly increase
$w(\mathcal{G})$, a contradiction. Thus, $m_{z^{\prime}w^{\prime}_{5}}\leq
m-5$ and again this allows us to apply the same argument as in Case 1.2 to
show that $\sum_{j=4}^{s}2^{m_{z^{\prime}w^{\prime}_{j}}}\leq
2^{m-3}-2^{m-s}$. Note that $r-3+s-3=t^{\prime}-3$. Consider the TCM
$\mathcal{G}^{\prime}$ obtained from $\mathcal{G}$ by choosing edge
$xz^{\prime}$ instead of $xw_{j}$ in triangles $xz^{\prime}w_{j}$ for all
$4\leq j\leq r$ and choosing edge $xz^{\prime}$ instead of
$z^{\prime}w^{\prime}_{j}$ in triangles $xz^{\prime}w^{\prime}_{j}$ for all
$4\leq j\leq s$. We have

$\displaystyle w(\mathcal{G}^{\prime})-w(\mathcal{G})$
$\displaystyle=2^{m-3}+\sum_{j=4}^{r}2^{m_{xw_{j}}-1}+\sum_{j=4}^{s}2^{m_{z^{\prime}w^{\prime}_{j}}-1}-2^{m-t^{\prime}}-\sum_{j=4}^{r}2^{m_{xw_{j}}}-\sum_{j=4}^{s}2^{m_{z^{\prime}w^{\prime}_{j}}}$
$\displaystyle=2^{m-3}-2^{m-t^{\prime}}-\sum_{j=4}^{r}2^{m_{xw_{j}}-1}-\sum_{j=4}^{s}2^{m_{z^{\prime}w^{\prime}_{j}}-1}$
$\displaystyle\geq
2^{m-3}-2^{m-t^{\prime}}-(2^{m-4}-2^{m-r-1})-(2^{m-4}-2^{m-s-1})$
$\displaystyle=2^{m-r-1}+2^{m-s-1}-2^{m-r-s+3}>0,$

contradicting $w(\mathcal{G})=H(m)$. ∎

###  4.3 Proofs of Theorem 1.6 and Theorem 1.7

In this subsection, we prove Theorem 1.6 and Theorem 1.7. We begin by proving
several inequalities that will be needed in the proof of Theorem 1.6, all of
which are consequences of the well-known Karamata’s Inequality below.

######  Lemma 4.8 (Karamata’s Inequality, [7]).

Let $f$ be a real-valued convex function defined on some interval $I$. Suppose
$\lambda_{1}\geq\cdots\geq\lambda_{n}$ and $\mu_{1}\geq\cdots\geq\mu_{n}$ are
numbers in $I$, such that for every $k\in[n]$, we have

$\sum_{i=1}^{k}\lambda_{i}\leq\sum_{i=1}^{k}\mu_{i},$

then

$\sum_{i=1}^{n}f(\lambda_{i})\leq\sum_{i=1}^{n}f(\mu_{i}).$

######  Lemma 4.9.

Let $a_{1}\geq\cdots\geq a_{n}\geq 0$, $\lambda_{1}\geq\cdots\geq\lambda_{n}$
and $\mu_{1}\geq\cdots\geq\mu_{n}$. If for every $k\in[n]$, we have

$\sum_{i=1}^{k}\lambda_{i}\leq\sum_{i=1}^{k}\mu_{i},$

then

$\sum_{i=1}^{n}\lambda_{i}a_{i}\leq\sum_{i=1}^{n}\mu_{i}a_{i}.$

###### Proof.

Set $a_{n+1}=0$. For each $k\in[n]$, let $f_{k}(x)=(a_{k}-a_{k+1})x$, and note
that $f_{i}$ is convex. Then by Lemma 4.8, we have

$\sum_{i=1}^{k}(a_{k}-a_{k+1})\lambda_{i}=\sum_{i=1}^{k}f_{k}(\lambda_{i})\leq\sum_{i=1}^{k}f_{k}(\mu_{i})=\sum_{i=1}^{k}(a_{k}-a_{k+1})\mu_{i},$

for each $k\in[n]$. Summing these together, we obtain

$\sum_{i=1}^{n}a_{i}\lambda_{i}=\sum_{k=1}^{n}\sum_{i=1}^{k}(a_{k}-a_{k+1})\lambda_{i}\leq\sum_{k=1}^{n}\sum_{i=1}^{k}(a_{k}-a_{k+1})\mu_{i}=\sum_{i=1}^{n}a_{i}\mu_{i},$

as required. ∎

######  Lemma 4.10.

Let $n>n^{\prime}\geq 1$, $a_{k}\geq\cdots\geq a_{1}>0$ and
$x_{1},\cdots,x_{k}\geq 0$, such that $\sum_{j=1}^{k}a_{j}=n$,
$\sum_{j=1}^{k}x_{j}=n^{\prime}$ and $a_{j}\geq x_{j}$ for all $j\in[k]$. Let
$q\in[k]$ be the unique index satisfying $\sum_{j=1}^{q-1}a_{j}\leq
n^{\prime}<\sum_{j=1}^{q}a_{j}$, and let $y_{j}=a_{j}$ for all $j\in[q-1]$,
$y_{q}=n^{\prime}-\sum_{j=1}^{q-1}a_{j}$, and $y_{j}=0$ for all
$j\in[k]\setminus[q]$. Then

$\sum_{j=1}^{k}(a_{j}-x_{j})^{2}\leq\sum_{j=1}^{k}(a_{j}-y_{j})^{2}.$

###### Proof.

Let $\sigma$ be a permutation of $[k]$ such that
$a_{\sigma(1)}-x_{\sigma(1)}\leq\cdots\leq a_{\sigma(k)}-x_{\sigma(k)}$. For
each $k^{\prime}\in[q]$, we have

$\sum_{j=k^{\prime}}^{k}(a_{\sigma(j)}-x_{\sigma(j)})\leq\sum_{j=1}^{k}(a_{\sigma(j)}-x_{\sigma(j)})=\sum_{j=1}^{k}(a_{j}-x_{j})=n-n^{\prime}=\sum_{j=k^{\prime}}^{k}(a_{j}-y_{j}),$

as $a_{j}=y_{j}$ for all $j\in[q-1]$. While for each
$k^{\prime}\in[k]\setminus[q]$,

$\sum_{j=k^{\prime}}^{k}(a_{\sigma(j)}-x_{\sigma(j)})\leq\sum_{j=k^{\prime}}^{k}a_{\sigma(j)}\leq\sum_{j=k^{\prime}}^{k}a_{j}=\sum_{j=k^{\prime}}^{k}(a_{j}-y_{j}).$

Hence, applying Lemma 4.8 with the index order reversed, and using
$f(x)=x^{2}$ is convex, we have

$\sum_{j=1}^{k}(a_{j}-x_{j})^{2}=\sum_{j=1}^{k}(a_{\sigma(j)}-x_{\sigma(j)})^{2}\leq\sum_{j=1}^{k}(a_{j}-y_{j})^{2},$

as required. ∎

######  Lemma 4.11.

Let $\mathcal{G}$ be a TCM. Let $A_{1},\cdots,A_{k}$ be the maximal closed
sets in $\mathcal{G}$ and suppose they have sizes $a_{1}\leq\cdots\leq a_{k}$,
respectively. Fix an $i\in[k]$ and $v_{i}\in A_{i}$. For each
$j\in[k]\setminus\\{i\\}$, let
$s_{j}=\sum_{j^{\prime}\in[j]\setminus\\{i\\}}a_{j^{\prime}}$. Then, we have

$\sum_{u\not\in
A_{i}}2^{m^{\mathcal{G}}_{uv_{i}}}\leq\sum_{j\in[k]\setminus\\{i\\}}a_{j}2^{m-a_{i}-s_{j}}.$
(5)

###### Proof.

Let $n=m-a_{i}$. Order the $n$ vertices $u\not\in A_{i}$ in decreasing order
of $m_{uv_{i}}^{\mathcal{G}}$ as $u_{1},\cdots,u_{n}$, and let
$\lambda_{\ell}=m^{\mathcal{G}}_{u_{\ell}v_{i}}$ for all $\ell\in[n]$. For
every $j\in[k]\setminus\\{i\\}$, let $\mu_{\ell}=m-a_{i}-s_{j}$ for all
$1+s_{j}-a_{j}\leq\ell\leq s_{j}$. Then (5) is equivalent to

$\sum_{\ell=1}^{n}2^{\lambda_{\ell}}\leq\sum_{\ell=1}^{n}2^{\mu_{\ell}}.$

Since both $(\lambda_{\ell})$ and $(\mu_{\ell})$ are decreasing sequences and
$2^{x}$ is a convex function, by Lemma 4.8, it suffices to show for all
$n^{\prime}\in[n]$ we have

$\sum_{\ell=1}^{n^{\prime}}\lambda_{\ell}\leq\sum_{\ell=1}^{n^{\prime}}\mu_{\ell}.$

Fix any $n^{\prime}\in[n]$. Suppose that among $u_{1},\cdots,u_{n^{\prime}}$,
there are $x_{j}$ of these vertices belonging to $A_{j}$ for each
$j\in[k]\setminus\\{i\\}$. Then, we claim that

$\sum_{\ell=1}^{n^{\prime}}\lambda_{\ell}\leq\sum_{j\in[k]\setminus\\{i\\}}x_{j}(m-a_{j}-a_{i})-\sum_{\begin{subarray}{c}1\leq
j<j^{\prime}\leq k\\\ j,j^{\prime}\not=i\end{subarray}}x_{j}x_{j^{\prime}}.$
(6)

Indeed, since $A_{i}$ and $A_{j}$ are closed sets, if $u_{\ell}\in A_{j}$,
then $\lambda_{\ell}=m^{\mathcal{G}}_{u_{\ell}v_{i}}\leq m-a_{j}-a_{i}$.
Furthermore, for any distinct $j,j^{\prime}\in[k]$ not equal to $i$, if
$u_{\ell}\in A_{j}$ and $u_{\ell^{\prime}}\in A_{j^{\prime}}$, then at least
one of edge $u_{\ell}v_{i}$ and $u_{\ell^{\prime}}v_{i}$ is not chosen in
triangle $u_{\ell}u_{\ell^{\prime}}v_{i}$, proving (6).

If $n=n^{\prime}$, then $x_{j}=a_{j}$ for all $j\in[k]\setminus\\{i\\}$ and
(6) implies

$\displaystyle\sum_{\ell=1}^{n}\lambda_{\ell}$
$\displaystyle\leq\sum_{j\in[k]\setminus\\{i\\}}a_{j}(m-a_{j}-a_{i})-\sum_{\begin{subarray}{c}1\leq
j<j^{\prime}\leq k\\\ j,j^{\prime}\not=i\end{subarray}}a_{j}a_{j^{\prime}}$
$\displaystyle=\sum_{j\in[k]\setminus\\{i\\}}a_{j}(m-a_{i}-s_{j})=\sum_{\ell=1}^{n}\mu_{\ell},$

as required. If $n>n^{\prime}$, Continuing from (6), we have

$\displaystyle\sum_{\ell=1}^{n^{\prime}}\lambda_{\ell}$
$\displaystyle\leq\sum_{j\in[k]\setminus\\{i\\}}x_{j}(m-a_{j}-a_{i})-\sum_{\begin{subarray}{c}1\leq
j<j^{\prime}\leq k\\\ j,j^{\prime}\not=i\end{subarray}}x_{j}x_{j^{\prime}}$
$\displaystyle=\sum_{j\in[k]\setminus\\{i\\}}x_{j}(m-a_{i})-\sum_{j\in[k]\setminus\\{i\\}}x_{j}a_{j}-\frac{1}{2}\left(\sum_{j\in[k]\setminus\\{i\\}}x_{j}\right)^{2}+\frac{1}{2}\sum_{j\in[k]\setminus\\{i\\}}x_{j}^{2}$
$\displaystyle=n^{\prime}(m-a_{i})-\frac{1}{2}n^{\prime
2}-\frac{1}{2}\sum_{j\in[k]\setminus\\{i\\}}a_{j}^{2}+\frac{1}{2}\sum_{j\in[k]\setminus\\{i\\}}(a_{j}-x_{j})^{2}$

Hence, if we let $q\in[k]\setminus\\{i\\}$ be the unique index satisfying
$s_{q}-a_{q}\leq n^{\prime}<s_{q}$, then by Lemma 4.10, the maximum on the
right hand side of (6) is achieved when $x_{j}=a_{j}$ for all
$j\in[q-1]\setminus\\{i\\}$, $x_{q}=n^{\prime}-s_{q}+a_{q}$, and $x_{j}=0$ for
all $j\in[k]\setminus([q]\cup\\{i\\})$. Therefore, we have

$\displaystyle\sum_{\ell=1}^{n^{\prime}}\lambda_{\ell}$ $\displaystyle\leq
x_{q}(m-a_{q}-a_{i})+\sum_{\begin{subarray}{c}j\in[q-1]\\\
j\not=i\end{subarray}}a_{j}(m-a_{j}-a_{i})-\sum_{\begin{subarray}{c}j\in[q-1]\\\
j\not=i\end{subarray}}a_{j}x_{q}-\sum_{\begin{subarray}{c}1\leq
j<j^{\prime}\leq q-1\\\ j,j^{\prime}\not=i\end{subarray}}a_{j}a_{j^{\prime}}$
$\displaystyle=x_{q}(m-a_{i}-s_{q})+\sum_{\begin{subarray}{c}j\in[q-1]\\\
j\not=i\end{subarray}}a_{j}(m-a_{i}-s_{j})=\sum_{\ell=1}^{n^{\prime}}\mu_{\ell},$

which proves the lemma. ∎

We are now ready to prove Theorem 1.6.

###### Proof of Theorem 1.6.

Let $\mathcal{G}$ be a TCM on $[m]$ with $w(\mathcal{G})=H(m)$. Let the
maximal closed sets in $\mathcal{G}$ be $A_{1},\cdots,A_{k}$. For each
$i\in[k]$, let $|A_{i}|=a_{i}$ so that $\sum_{i=1}^{k}a_{i}=m$, and assume
$a_{1}\leq\cdots\leq a_{k}$. By Proposition 4.7 we may assume $a_{i}\geq 2$
for all $i\in[k]$. Recall that $h(m)=\frac{H(m)}{m2^{m-1}}$, we will show
$h(m)\leq\frac{83}{192}$.

We can divide every edge in $\mathcal{G}$ into two types, either it is within
a closed set, or it goes between two closed sets. For each $i\in[k]$, all
edges within $A_{i}$ together contribute at most

$\sum_{xy\in A_{i}^{(2)}}2^{m_{xy}^{\mathcal{G}}}=\sum_{xy\in
A_{i}^{(2)}}2^{m_{xy}^{\mathcal{G}[A_{i}]}+m-a_{i}}\leq H(a_{i})2^{m-a_{i}}.$

For each $i\in[k]$ and any vertex $v_{i}\in A_{i}$, by Lemma 4.11, edges of
the form $v_{i}u$ with $u\not\in A_{i}$ contribute at most

$\sum_{1\leq j<i}a_{j}2^{m-a_{i}-\sum_{\ell=1}^{j}a_{\ell}}+\sum_{i<j\leq
k}a_{j}2^{m-\sum_{\ell=1}^{j}a_{\ell}}.$

Hence, the total contribution from all edges going across closed sets is at
most

$\displaystyle N$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{k}a_{i}\left(\sum_{1\leq
j<i}a_{j}2^{m-a_{i}-\sum_{\ell\in[j]}a_{\ell}}+\sum_{i<j\leq
k}a_{j}2^{m-\sum_{\ell\in[j]}a_{\ell}}\right)$
$\displaystyle=2^{m-1}\sum_{1\leq i<j\leq
k}a_{i}a_{j}\left(\frac{1}{2^{\sum_{\ell=1}^{j}a_{\ell}}}+\frac{1}{2^{a_{j}+\sum_{\ell=1}^{i}a_{\ell}}}\right)$
$\displaystyle=2^{m-1}\sum_{j=2}^{k}\frac{a_{j}}{2^{a_{j}}}\sum_{i=1}^{j-1}\left(\frac{a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}}}+\frac{a_{i}}{2^{\sum_{\ell=1}^{j-1}a_{\ell}}}\right),$

where we have $\frac{1}{2}$ factor in front of the first sum as it counts the
contribution from each edge twice. We claim that

$N\leq 2^{m-1}\sum_{j=1}^{k}\frac{2}{3}\frac{a_{j}}{2^{a_{j}}},$

where observe that we have added an additional $j=1$ term in this sum. First
note that $(a_{j}/2^{a_{j}})$ is a decreasing sequence. Let
$\mu_{2}=\frac{4}{3}$, and let $\mu_{j}=\frac{2}{3}$ for all $3\leq j\leq k$.
Let

$\lambda_{j}=\sum_{i=1}^{j-1}\left(\frac{a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}}}+\frac{a_{i}}{2^{\sum_{\ell=1}^{j-1}a_{\ell}}}\right)$

for all $2\leq j\leq k$. Note that since both $(\mu_{j})$ and $(\lambda_{j})$
are decreasing sequences, it suffices to show that

$\sum_{j=2}^{k^{\prime}}\lambda_{j}\leq\frac{2k^{\prime}}{3}=\sum_{j=2}^{k^{\prime}}\mu_{j}$
(7)

for all $2\leq k^{\prime}\leq k$, as then by Lemma 4.9, we have

$N=2^{m-1}\sum_{j=2}^{k}\lambda_{j}\frac{a_{j}}{2^{a_{j}}}\leq
2^{m-1}\sum_{j=2}^{k}\mu_{j}\frac{a_{j}}{2^{a_{j}}}\leq
2^{m-1}\sum_{j=1}^{k}\frac{2}{3}\frac{a_{j}}{2^{a_{j}}}.$

We now prove (7). Indeed, for every $2\leq k^{\prime}\leq k$, we have

$\displaystyle\sum_{j=2}^{k^{\prime}}\lambda_{j}$
$\displaystyle=\sum_{j=2}^{k^{\prime}}\sum_{i=1}^{j-1}\frac{a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}}}+\sum_{j=2}^{k^{\prime}}\sum_{i=1}^{j-1}\frac{a_{i}}{2^{\sum_{\ell=1}^{j-1}a_{\ell}}}$
$\displaystyle=\sum_{i=1}^{k^{\prime}-1}\frac{(k^{\prime}-i)a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}}}+\sum_{j=2}^{k^{\prime}}\frac{\sum_{i=1}^{j-1}a_{\ell}}{2^{\sum_{\ell=1}^{j-1}a_{\ell}}}.$

We claim that if $a_{t}\geq 3$ for some $t\in[k^{\prime}]$, then both sums
increase if we decrease $a_{t}$ by 1. Indeed, this increases the second sum as
$f(x)=x/2^{x}$ is a decreasing function. This also increases the first sum as

$\frac{(k^{\prime}-t)a_{t}}{2^{\sum_{\ell=1}^{t}a_{\ell}}}\leq\frac{(k^{\prime}-t)(a_{t}-1)}{2^{\sum_{\ell=1}^{t}a_{\ell}-1}}$

and

$\frac{(k^{\prime}-i)a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}}}\leq\frac{(k^{\prime}-i)a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}-1}}$

for all $t<i\leq k^{\prime}-1$. Therefore, by repeatedly applying this until
$a_{i}=2$ for all $i\in[k^{\prime}]$, we have

$\displaystyle\sum_{j=2}^{k^{\prime}}\lambda_{j}$
$\displaystyle=\sum_{i=1}^{k^{\prime}-1}\frac{(k^{\prime}-i)a_{i}}{2^{\sum_{\ell=1}^{i}a_{\ell}}}+\sum_{j=2}^{k^{\prime}}\frac{\sum_{i=1}^{j-1}a_{\ell}}{2^{\sum_{\ell=1}^{j-1}a_{\ell}}}$
$\displaystyle\leq\sum_{i=1}^{k^{\prime}-1}\frac{2k^{\prime}-2i}{2^{2i}}+\sum_{j=2}^{k^{\prime}}\frac{2j-2}{2^{2j-2}}$
$\displaystyle=\sum_{j=1}^{k^{\prime}-1}\frac{2k^{\prime}-2j}{2^{2j}}+\sum_{j=1}^{k^{\prime}-1}\frac{2j}{2^{2j}}$
$\displaystyle=\sum_{j=1}^{k^{\prime}-1}\frac{2k^{\prime}}{2^{2j}}\leq\frac{2k^{\prime}}{3}=\sum_{j=2}^{k^{\prime}}\mu_{j},$

as claimed.

It follows that

$H(m)\leq\max\left\\{\sum_{i=1}^{k}H(a_{i})2^{m-a_{i}}+2^{m-1}\sum_{i=1}^{k}\frac{2}{3}\frac{a_{i}}{2^{a_{i}}}\colon\sum_{i=1}^{k}a_{i}=m,a_{i}\geq
2\mbox{ }\forall i\in[k]\right\\},$

and therefore

$\displaystyle h(m)$
$\displaystyle\leq\max\left\\{\sum_{i=1}^{k}\frac{a_{i}h(a_{i})}{m}+\sum_{i=1}^{k}\frac{2}{3}\frac{a_{i}}{m2^{a_{i}}}\colon\sum_{i=1}^{k}a_{i}=m,a_{i}\geq
2\mbox{ }\forall i\in[k]\right\\}$
$\displaystyle=\max\left\\{\sum_{i=1}^{k}\frac{a_{i}}{m}\left(h(a_{i})+\frac{2}{3}\frac{1}{2^{a_{i}}}\right)\colon\sum_{i=1}^{k}a_{i}=m,a_{i}\geq
2\mbox{ }\forall i\in[k]\right\\}.$

Define a function $\varepsilon:\mathbb{N}\to\mathbb{R}$ by $\varepsilon(m)=0$
for $m\in[6]$, and $\varepsilon(m)=\sum_{j=7}^{m}\frac{1}{2^{j}}$ for $m\geq
7$. We use induction to show that
$h(m)+\frac{2}{3}\frac{1}{2^{m}}\leq\frac{5}{12}+\varepsilon(m)$ for all
$m\geq 2$. The base cases when $1\leq m\leq 6$ follows from the following
table, which shows $h(m)+\frac{2}{3}\frac{1}{2^{m}}$ is maximised by $m=2$ in
this range.

$m$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
$h(m)$ | 0 | 0.25 | 0.333 | 0.375 | 0.375 | 0.380
$h(m)+\frac{2}{3}\frac{1}{2^{m}}$ | 0.333 | 0.417 | 0.417 | 0.417 | 0.396 | 0.391

Assume this is true for all smaller $m$, and let $a_{1},\cdots,a_{k}$ be such
that $\sum_{i=1}^{k}a_{i}=m$ and $a_{i}\geq 2$ for all $i\in[k]$. Then by
induction hypothesis, we have

$\displaystyle\sum_{i=1}^{k}\frac{a_{i}}{m}\left(h(a_{i})+\frac{2}{3}\frac{1}{2^{a_{i}}}\right)+\frac{2}{3}\frac{1}{2^{m}}$
$\displaystyle\leq\sum_{i=1}^{k}\frac{a_{i}}{m}\left(\frac{5}{12}+\varepsilon(a_{i})\right)+\frac{2}{3}\frac{1}{2^{m}}$
$\displaystyle=\frac{5}{12}+\sum_{i=7}^{k}\frac{a_{i}}{m}\sum_{j=7}^{a_{i}}\frac{1}{2^{j}}+\frac{2}{3}\frac{1}{2^{m}}$
$\displaystyle=\frac{5}{12}+\sum_{j=7}^{m-1}\frac{1}{2^{j}}\sum_{i:a_{i}\geq
j}\frac{a_{i}}{m}+\frac{2}{3}\frac{1}{2^{m}}$
$\displaystyle\leq\frac{5}{12}+\sum_{j=7}^{m-1}\frac{1}{2^{j}}+\frac{1}{2^{m}}$
$\displaystyle\leq\frac{5}{12}+\varepsilon(m).$

Since this is true for any such $a_{1},\cdots,a_{k}$, we get
$h(m)+\frac{2}{3}\frac{1}{2^{m}}\leq\frac{5}{12}+\varepsilon(m)$, as required.
Finally, note that $\varepsilon(m)<\frac{1}{2^{6}}$ for all $m$, hence
$h(m)\leq\frac{5}{12}+\varepsilon(m)-\frac{2}{3}\frac{1}{2^{m}}<\frac{83}{192}$
for all $m$. ∎

We deduce Theorem 1.7 as a corollary of Theorem 1.6.

###### Proof of Theorem 1.7.

The case when $r=3$ follows from Theorem 1.5 and Theorem 1.6. Now let $r\geq
4$, and let $A\in\operatorname{Avoid}(m,r,M)$.

For every column $c$ in $A$, define the _3-support_ of $c$ to be the index set
of its entries that are equal to 0, 1 or 2. For every $X\subset[m]$ of size
$k$, let $C^{*}_{3}(X)$ be the set of columns in $A$ with 3-support equal to
$X$, and let $C_{3}(X)$ be the set of distinct (0,1,2)-columns formed by
restricting columns in $C^{*}_{3}(X)$ to rows with indices in $X$. Viewing
$C_{3}(X)$ as a $k$-rowed $(0,1,2)$-matrix, we must have
$C_{3}(X)\in\operatorname{Avoid}(k,3,M)$. Hence,
$|C_{3}(X)|\leq\operatorname{forb}(k,3,M)$, and thus
$|C^{*}_{3}(X)|\leq\operatorname{forb}(k,3,M)(r-3)^{m-k}$. Therefore, we have

$\displaystyle|A|$
$\displaystyle=\sum_{X\subset[m]}|C^{*}_{3}(X)|\leq\sum_{k=0}^{m}\binom{m}{k}\operatorname{forb}(k,3,M)(r-3)^{m-k}$
$\displaystyle\leq\sum_{k=0}^{m}\binom{m}{k}\left(1+\frac{83}{192}\right)k2^{k-1}(r-3)^{m-k}+\sum_{k=0}^{m}\binom{m}{k}2^{k}(r-3)^{m-k}$
$\displaystyle=\left(1+\frac{83}{192}\right)m(r-1)^{m-1}+(r-1)^{m}.$

Since this is true for all $A\in\operatorname{Avoid}(m,r,M)$, we have
$\operatorname{forb}(m,r,M)\leq\left(1+\frac{83}{192}\right)m(r-1)^{m-1}+(r-1)^{m}$,
as required. ∎

##  5 Lower bounds

In this section we prove Theorem 1.8, which bounds $H_{2}(m,\alpha)$ and
$\operatorname{forb}(m,r,M)$ from below with an explicit construction, and
Theorem 1.9, which determines $H_{2}(m,2)$. If $\alpha\not=0$, let
$h_{2}(m,\alpha)=2H_{2}(m,\alpha)/m\alpha^{m}$ for all $m\geq 1$. We begin by
showing $H_{2}(m,\alpha)$ and $h_{2}(m,\alpha)$ satisfy the following
recurrence relations.

######  Lemma 5.1.

For all $m\geq 3$, we have

$H_{2}(m,\alpha)=\max\left\\{H_{2}(a,\alpha)\alpha^{m-a}+H_{2}(b,\alpha)\alpha^{m-b}+ab\colon
a+b=m\right\\},$
$h_{2}(m,\alpha)=\max\left\\{\frac{ah_{2}(a,\alpha)}{m}+\frac{bh_{2}(b,\alpha)}{m}+\frac{2ab}{m\alpha^{m}}\colon
a+b=m\right\\}.$

###### Proof.

Let $\mathcal{G}$ be a 2-recursive TCM on $[m]$ with
$w(\mathcal{G},\alpha)=H_{2}(m,\alpha)$. Let $m=V_{1}\cup V_{2}$,
$\mathcal{G}_{1}$, $\mathcal{G}_{2}$ and $\mathcal{G}_{3}$ be as in Definition
1.3, and let $m^{\prime}=|V_{1}|$. Then
$m^{\mathcal{G}}_{xy}=m^{\mathcal{G}_{1}}_{xy}+m-m^{\prime}$ for all distinct
$x,y\in V_{1}$, $m^{\mathcal{G}}_{xy}=m^{\mathcal{G}_{2}}_{xy}+m^{\prime}$ for
all distinct $x,y\in V_{2}$, and $m^{\mathcal{G}}_{xy}=0$ for all $x\in
V_{1},y\in V_{2}$. Hence

$\displaystyle H_{2}(m,\alpha)$
$\displaystyle=w(\mathcal{G},\alpha)=\sum_{xy\in[m]^{(2)}}\alpha^{m^{\mathcal{G}}_{xy}}$
$\displaystyle=\sum_{xy\in
V_{1}^{(2)}}\alpha^{m^{\mathcal{G}_{1}}_{xy}+m-m^{\prime}}+\sum_{xy\in
V_{2}^{(2)}}\alpha^{m^{\mathcal{G}_{2}}_{xy}+m^{\prime}}+\sum_{x\in V_{1},y\in
V_{2}}1$ $\displaystyle\leq
H_{2}(m^{\prime},\alpha)\alpha^{m-m^{\prime}}+H_{2}(m-m^{\prime},\alpha)\alpha^{m^{\prime}}+m^{\prime}(m-m^{\prime}),$

which is at most the right hand side.

On the other hand, for every $a+b=m$, let $\mathcal{G}_{a},\mathcal{G}_{b}$ be
2-recursive triangular multigraphs on vertex sets $[a]$ and $[m]\setminus[a]$,
respectively, with $w(\mathcal{G}_{a})=H_{2}(a,\alpha)$ and
$w(\mathcal{G}_{b})=H_{2}(b,\alpha)$. Let $\mathcal{G}$ be the 2-recursive TCM
formed as in Definition 1.3 by taking $[m]=[a]\cup([m]\setminus[a])$,
$\mathcal{G}_{1}=\mathcal{G}_{a}$ and $\mathcal{G}_{2}=\mathcal{G}_{b}$. Then
a calculation similar to above shows

$H_{2}(a,\alpha)\alpha^{m-a}+H_{2}(b,\alpha)\alpha^{m-b}+ab=\sum_{xy\in[m]^{(2)}}\alpha^{m^{\mathcal{G}}_{xy}}=w(\mathcal{G},\alpha)\leq
H_{2}(m,\alpha),$

proving the recurrence formula for $H_{2}(m,\alpha)$. The recurrence formula
for $h_{2}(m,\alpha)$ follows after dividing through by $m\alpha^{m}/2$. ∎

Lemma 5.1 implies that to compute $H_{2}(m,\alpha)$ and $h_{2}(m,\alpha)$, it
suffices to determine for each $m\geq 3$, which split of $m$ into $a+b$
achieves the maximum on the right hand side of the recurrence formulas. In
Section 5.1, we prove Theorem 1.8 by obtaining lower bounds for these two
quantities using a specific split. Then, in Section 5.2, we prove Theorem 1.9
by showing that this split is indeed optimal in the case when $r=3$ and
$\alpha=2$.

###  5.1 Lower bound construction

For every $m\geq 3$, let $k=k(m)$ be the unique integer such that
$2^{k}+2^{k-1}\leq m<2^{k}+2^{k+1}$. Define inductively a 2-recursive TCM
$\mathcal{G}(m)$ on $[m]$ for every $m\geq 1$ as follows. For $m=1,2$, let
$\mathcal{G}(m)$ be the empty graph. For $m\geq 3$, let $\mathcal{G}(m)$ be
the 2-recursive TCM formed as in Definition 1.3 by taking
$[m]=[2^{k}]\cup([m]\setminus[2^{k}])$, $\mathcal{G}_{1}=\mathcal{G}(2^{k})$
and taking $\mathcal{G}_{2}$ isomorphic to $\mathcal{G}(m-2^{k})$.

For every $m\geq 1$ and $\alpha\not=0$, let
$\overline{H}_{2}(m,\alpha)=\sum_{xy\in[m]^{2}}\alpha^{m^{\mathcal{G}(m)}_{xy}}$
and $\overline{h}_{2}(m,\alpha)=2\overline{H}_{2}(m,\alpha)/m\alpha^{m}$. By
the construction above, and using calculation similar to the proof of Lemma
5.1 above, we have

$\overline{h}_{2}(m,\alpha)=\frac{2^{k}\overline{h}_{2}(2^{k},\alpha)}{m}+\frac{(m-2^{k})\overline{h}_{2}(m-2^{k},\alpha)}{m}+\frac{2^{k+1}(m-2^{k})}{m\alpha^{m}}.$
(8)

Moreover, since each $\mathcal{G}(m)$ is a 2-recursive TCM, we have that
$\overline{H}_{2}(m,\alpha),\overline{h}_{2}(m,\alpha)$ are lower bounds for
$H_{2}(m,\alpha)$ and $h_{2}(m,\alpha)$, respectively.

We first show that $\overline{h}_{2}(m,\alpha)$ has a nice formula when $m$ is
a power of 2.

######  Lemma 5.2.

For every $k\geq 0$ and $\alpha\not=0$,
$\overline{h}_{2}(2^{k},\alpha)=\sum_{j=1}^{k}2^{j-1}/\alpha^{2^{j}}$.

###### Proof.

We use induction on $k$. The cases when $k=0,1$ follow from
$\overline{H}_{2}(1,\alpha)=0,\overline{H}_{2}(2,\alpha)=1$. Now assume $k\geq
2$. Then, by induction and (8), we have

$\displaystyle\overline{h}_{2}(2^{k},\alpha)$
$\displaystyle=2\cdot\frac{2^{k-1}\overline{h}_{2}(2^{k-1},\alpha)}{2^{k}}+\frac{2^{k}\cdot
2^{k-1}}{2^{k}\alpha^{2^{k}}}$
$\displaystyle=\sum_{j=1}^{k-1}\frac{2^{j-1}}{\alpha^{2^{j}}}+\frac{2^{k-1}}{\alpha^{2^{k}}}=\sum_{j=1}^{k}\frac{2^{j-1}}{\alpha^{2^{j}}},$

as required. ∎

Motivated by this, let $g(k,\alpha)=\sum_{j=1}^{k}2^{j-1}/\alpha^{2^{j}}$ for
every $\alpha\not=0$, and let
$\lambda(\alpha)=\sum_{j=1}^{\infty}2^{j-1}/\alpha^{2^{j}}=\lim_{k\to\infty}g(k,\alpha)$
for every $\alpha>1$. Roughly speaking, the following lemma shows that
$\overline{h_{2}}(m,\alpha)$ do not deviate much from
$g(\left\lfloor\log_{2}m\right\rfloor,\alpha)$.

######  Lemma 5.3.

For every $k\geq 1$ and $\alpha\not=0$, let
$\widetilde{g}(k,\alpha)=\min\\{\overline{h}_{2}(m,\alpha)\colon 2^{k}\leq
m<2^{k+1}\\}$. Then,

$\widetilde{g}(k+1,\alpha)\geq\min\left\\{\frac{g(k,\alpha)}{3}+\frac{2\widetilde{g}(k,\alpha)}{3},\frac{g(k+1,\alpha)}{2}+\frac{\widetilde{g}(k,\alpha)}{2}\right\\}.$

Therefore, for all $\alpha>1$,
$\lim_{k\to\infty}\widetilde{g}(k,\alpha)=\lim_{k\to\infty}g(k,\alpha)=\liminf_{m\to\infty}\overline{h}_{2}(m,\alpha)=\lambda(\alpha)$.

###### Proof.

Let $k\geq 1$ and let $2^{k+1}\leq m<2^{k+2}$. Note that
$\widetilde{g}(k,\alpha)\leq\overline{h}_{2}(2^{k},\alpha)=g(k,\alpha)$.

Case 1. If $2^{k+1}\leq m<2^{k}+2^{k+1}$, set $c=m-2^{k}$ and note that
$2^{k}\leq c<2^{k+1}$. By (8), Lemma 5.2 and the definition of
$\widetilde{g}(k,\alpha)$, we have

$\displaystyle\overline{h}_{2}(m,\alpha)$
$\displaystyle\geq\frac{2^{k}\overline{h}_{2}(2^{k},\alpha)}{m}+\frac{c\overline{h}_{2}(c,\alpha)}{m}=\frac{2^{k}g(k,\alpha)}{m}+\frac{c\overline{h}_{2}(c,\alpha)}{m}$
$\displaystyle\geq\frac{2^{k}g(k,\alpha)}{m}+\frac{c\widetilde{g}(k,\alpha)}{m}\geq\frac{g(k,\alpha)}{3}+\frac{2\widetilde{g}(k,\alpha)}{3}.$

Case 2. If $2^{k}+2^{k+1}\leq m<2^{k+2}$, set $c=m-2^{k+1}$ and note that
$2^{k}\leq c<2^{k+1}$. Again, by (8). Lemma 5.2 and the definition of
$\widetilde{g}(k)$, we have

$\displaystyle\overline{h}_{2}(m,\alpha)$
$\displaystyle\geq\frac{2^{k+1}\overline{h}_{2}(2^{k+1},\alpha)}{m}+\frac{c\overline{h}_{2}(c,\alpha)}{m}=\frac{2^{k+1}g(k+1,\alpha)}{m}+\frac{c\overline{h}_{2}(c,\alpha)}{m}$
$\displaystyle\geq\frac{2^{k+1}g(k+1,\alpha)}{m}+\frac{c\widetilde{g}(k,\alpha)}{m}\geq\frac{g(k+1,\alpha)}{2}+\frac{\widetilde{g}(k,\alpha)}{2}.$

Hence, for all $k\geq 1$, we have
$\widetilde{g}(k+1,\alpha)=\min\\{\overline{h}_{2}(m,\alpha)\colon 2^{k+1}\leq
m<2^{k+2}\\}\geq\min\\{\frac{1}{3}g(k,\alpha)+\frac{2}{3}\widetilde{g}(k,\alpha),\frac{1}{2}g(k+1,\alpha)+\frac{1}{2}\widetilde{g}(k,\alpha)\\}$,
as claimed.

Moreover, it follows that for every $k\geq 1$, we have
$\widetilde{g}(k+1,\alpha)-\widetilde{g}(k,\alpha)\geq\frac{1}{3}(g(k,\alpha)-\widetilde{g}(k,\alpha))$
and
$\widetilde{g}(k+1,\alpha)-\widetilde{g}(k,\alpha)\geq\frac{1}{2}(g(k+1,\alpha)-\widetilde{g}(k,\alpha))$,
both of them imply that
$\widetilde{g}(k+1,\alpha)\geq\widetilde{g}(k,\alpha)$. When $\alpha>1$, this
means $\widetilde{g}(k,\alpha)$ is increasing in $k$ and bounded above by
$\lambda(\alpha)$, so $\lim_{k\to\infty}\widetilde{g}(k,\alpha)$ exists.
Taking limit on both sides of
$\widetilde{g}(k+1,\alpha)\geq\min\\{\frac{1}{3}g(k,\alpha)+\frac{2}{3}\widetilde{g}(k,\alpha),\frac{1}{2}g(k+1,\alpha)+\frac{1}{2}\widetilde{g}(k,\alpha)\\}$,
we see that in fact
$\lim_{k\to\infty}\widetilde{g}(k,\alpha)=\lim_{k\to\infty}g(k,\alpha)=\lambda(\alpha)$.
Finally,
$\liminf_{m\to\infty}\overline{h}_{2}(m,\alpha)=\lim_{m\to\infty}\inf_{n\geq
m}\overline{h}_{2}(n,\alpha)=\lim_{k\to\infty}\inf_{n\geq
2^{k}}\overline{h}_{2}(n,\alpha)=\lim_{k\to\infty}\inf_{k^{\prime}\geq
k}\widetilde{g}(k^{\prime},\alpha)=\lim_{k\to\infty}\widetilde{g}(k,\alpha)=\lambda(\alpha)$.
∎

We can now quickly deduce Theorem 1.8.

###### Proof of Theorem 1.8.

For every $\alpha>1$,
$\liminf_{n\to\infty}\overline{h}_{2}(m,\alpha)=\lambda(\alpha)$ by Lemma 5.3.
Therefore, for every $\epsilon>0$ and all sufficiently large $m$, we have
$\overline{h}_{2}(m,\alpha)>\lambda(\alpha)-\epsilon$, and thus
$H_{2}(m,\alpha)\geq\overline{H}_{2}(m,\alpha)>(\lambda(\alpha)-\epsilon)m\alpha^{m}/2$.

For every $r\geq 3$, apply the above to $\alpha_{r}=\frac{r-1}{r-2}$. Then, by
Theorem 1.5, for every $\epsilon>0$ and all sufficiently large $m$ we have

$\displaystyle\operatorname{forb}(m,r,M)$
$\displaystyle\geq(r-1)^{m}+m(r-1)^{m-1}+H_{2}(m,\alpha_{r})(r-2)^{m-2}$
$\displaystyle\geq(r-1)^{m}+m(r-1)^{m-1}+\overline{H}_{2}(m,\alpha_{r})(r-2)^{m-2}$
$\displaystyle\geq(r-1)^{m}+m(r-1)^{m-1}+m(r-1)^{m-1}(\lambda(\alpha_{r})-\epsilon)\frac{r-1}{2(r-2)^{2}}$
$\displaystyle\geq(r-1)^{m}+m(r-1)^{m-1}\left(1+\frac{r-1}{2(r-2)^{2}}\lambda\left(\frac{r-1}{r-2}\right)-\epsilon\right),$

as required. ∎

###  5.2 Optimal splits

In this subsection, we show that in the case when $\alpha=2$, the split we
used in the lower bound construction in Section 5.1 is actually optimal with
the exception when $m=6$, which proves Theorem 1.9.

For simplicity, write $H_{2}(m)=H_{2}(m,2)$ and $h_{2}(m)=h_{2}(m,2)$. A table
of values of $H_{2}(m)$ and $h_{2}(m)$, rounded to 3 decimals, for small $m$
is given below.

$m$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
$H_{2}(m)$ | 0 | 1 | 4 | 12 | 30 | 73 | 172 | 400
$h_{2}(m)$ | 0.000 | 0.250 | 0.333 | 0.375 | 0.375 | 0.380 | 0.384 | 0.391

######  Theorem 5.4.

For all $m\geq 2$ except 6, we have

$h_{2}(m)=\frac{2^{k}h_{2}(2^{k})}{m}+\frac{(m-2^{k})h_{2}(m-2^{k})}{m}+\frac{2^{k}(m-2^{k})}{m2^{m-1}},$

where $k$ is the unique integer such that $2^{k}+2^{k-1}\leq m<2^{k}+2^{k+1}$.

###### Proof.

We use induction on $m$. It is easy to verify this using the recurrence
relation of $h_{2}(m)$ and the initial values given above for all $m\leq 48$.
Hence, we only need to prove the theorem for all $k\geq 5$ and all
$2^{k-1}+2^{k}\leq m<2^{k}+2^{k+1}$.

Fix some $k\geq 5$ and $2^{k-1}+2^{k}\leq m<2^{k}+2^{k+1}$. Assume inductively
that the result holds for all smaller values of $k,m$. We need to show that
for all positive integers $a\leq b$ satisfying $a+b=m$, we have

$2^{k}h_{2}(2^{k})+(m-2^{k})h_{2}(m-2^{k})+\frac{2^{k}(m-2^{k})}{2^{m-1}}\geq
ah_{2}(a)+bh_{2}(b)+\frac{ab}{2^{m-1}}.$ (9)

Let $c=m-2^{k}$. Depending on the values of $a,b,c,m$, we will split into
twelve subcases. The proofs of all subcases follow the same general recipe,
which will be described and demonstrated below. However, the calculations
involved are long and somewhat tedious, so we will only show the full proofs
for four of them and sketch the rest.

We begin by introducing some terminologies and notations. For positive
integers $x,y,n$, we say that $x$ and $y$ form a split of $n$ if $x\leq y$ and
$x+y=n$. In this case, by definition we have $nh_{2}(n)\geq
xh_{2}(x)+yh_{2}(y)+xy/2^{n-1}$. We say that $x$ and $y$ form an optimal split
of $n$ if they form a split of $n$ and
$nh_{2}(n)=xh_{2}(x)+yh_{2}(y)+xy/2^{n-1}$. We call a term of the form
$xh_{2}(x)$ a major term, and denote it by $[x]$. In contrast, a term of the
form $xy/2^{n-1}$ (with $n=x+y$) is called a minor term, and is denoted by
$[x,y]$. In this language, if $x$ and $y$ form a split of $n$, then
$[n]\geq[x]+[y]+[x,y]$, with equality if $x$ and $y$ form an optimal split.
Our goal (9) is equivalent to

$[2^{k}]+[c]+[2^{k},c]\geq[a]+[b]+[a,b]$ (10)

The general recipe for proving each subcase consists of two steps. We first
focus on the major terms. The aim is to find a series of intermediate splits,
often optimal ones, with the help of the induction hypothesis, so that when we
substitute them into (10) the major terms all cancel out. Then we deal with
the remaining minor terms. Some computations and estimates are needed here to
show that we do have the desired inequalities, but across subcases the
calculations all follow a similar pattern.

We now list all the subcases and prove a few of them in detail. For the
remaining ones, we will give the intermediate splits needed to cancel out the
major terms, but leave out the minor terms calculations.

Case 1. $2^{k+1}\leq m<2^{k}+2^{k+1}$. Then $2^{k}\leq b<2^{k}+2^{k+1}$.

Case 1.1.  $2^{k-1}+2^{k}\leq b<2^{k}+2^{k+1}$. Then $a<2^{k-1}+2^{k}$ as
$a+b=m<2^{k}+2^{k+1}$. There are two subcases.

Case 1.1.1. $a<2^{k}$. By induction hypothesis, $2^{k}$ and $b-2^{k}$ form an
optimal split of $b$. Also $a+(b-2^{k})=m-2^{k}=c$, so $a$ and $b-2^{k}$ form
a split of $c$. Hence, we have

$\displaystyle[b]$ $\displaystyle=[2^{k}]+[b-2^{k}]+[2^{k},b-2^{k}],$
$\displaystyle[c]$ $\displaystyle\geq[a]+[b-2^{k}]+[a,b-2^{k}].$

Substitute these into (10), we see that all the major terms cancel out and it
suffices now to show that the remaining minor terms satisfy
$[2^{k},c]+[a,b-2^{k}]\geq[2^{k},b-2^{k}]+[a,b]$. Expand and simplify, this is
equivalent to showing $2^{k}c+2^{2^{k}}a(b-2^{k})\geq 2^{k}2^{a}(b-2^{k})+ab$.
To simplify notations, let $s=2^{k}$, $t=a$ and $r=b-2^{k}$. Then $0\leq t<s$,
$s/2\leq r<2s$, $c=a+b-2^{k}=r+t$, and we need to show $s(r+t)+tr2^{s}\geq
sr2^{t}+(s+r)t$. Equivalently, we need $(s-t)r+r(t2^{s}-s2^{t})\geq 0$. If
$t=0$, both sides are 0. Otherwise, it follows from the fact that the sequence
$(x_{n})_{n=1}^{\infty}$ given by $x_{n}=2^{n}/n$ satisfies
$x_{1}=x_{2}<x_{3}<x_{4}<\cdots$.

Case 1.1.2. $2^{k}\leq a<2^{k-1}+2^{k}$. Then $b=m-a<2^{k+1}$. Also, we have
$2^{k-1}+2^{k}\leq c=a+b-2^{k}=m-2^{k}<2^{k+1}$. Hence by induction
hypothesis, we know optimal splits of $a,b,c$ and $2^{k}$, which gives

$\displaystyle[a]$ $\displaystyle=[2^{k-1}]+[a-2^{k-1}]+[2^{k-1},a-2^{k-1}],$
$\displaystyle[b]$ $\displaystyle=[2^{k}]+[b-2^{k}]+[2^{k},b-2^{k}],$
$\displaystyle[c]$ $\displaystyle=[2^{k}]+[c-2^{k}]+[2^{k},c-2^{k}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}].$

Moreover, we have $2^{k}\leq c-2^{k-1}=(a-2^{k-1})+(b-2^{k})<2^{k-1}+2^{k}$,
so by induction hypothesis,

$\displaystyle[c-2^{k-1}]$
$\displaystyle=[2^{k-1}]+[c-2^{k}]+[2^{k-1},c-2^{k}]$
$\displaystyle\geq[a-2^{k-1}]+[b-2^{k}]+[a-2^{k-1},b-2^{k}].$

Substitute these into (10), we see that all the major terms cancel out, and it
suffices to show that the remaining minor terms satisfy

$\displaystyle\phantom{==}[2^{k},c]+[c-2^{k},2^{k}]+[2^{k-1},2^{k-1}]+[a-2^{k-1},b-2^{k}]$
$\displaystyle\geq[a,b]+[b-2^{k},2^{k}]+[a-2^{k-1},2^{k-1}]+[2^{k-1},c-2^{k}].$

Expand and simplify, this is equivalent to

$\displaystyle\phantom{==}c2^{k}+(c-2^{k})2^{k}2^{2^{k}}+2^{2k-2}2^{c}+(a-2^{k-1})(b-2^{k})2^{3\cdot
2^{k-1}}$ $\displaystyle\geq
ab+(b-2^{k})2^{k}2^{a}+(a-2^{k-1})2^{k-1}2^{b}+2^{k-1}(c-2^{k})2^{3\cdot
2^{k-1}}.$

We perform similar substitutions $s=2^{k-1}$, $t=a-2^{k}$ and
$r=b-2^{k-1}-2^{k}$ to simplify notations. Note that $0\leq r,t<s$ and
$c=3s+t+r$. Then it suffices to show

$\displaystyle\phantom{==}2s(3s+t+r)+2s(s+t+r)2^{2s}+s^{2}2^{3s+t+r}+(s+t)(s+r)2^{3s}$
$\displaystyle\geq(2s+t)(3s+r)+2s(s+r)2^{2s+t}+s(s+t)2^{3s+r}+s(s+t+r)2^{3s}.$

Expand and simplify, this is equivalent to

$(s2^{2s+r}-(2s+r)2^{s})(s2^{s+t}-(s+t)2^{s})+2^{2s}r(t2^{s}-s2^{t}+s-t)\geq
st+rt.$

Again, each term on the left hand side is non-negative as the sequence
$(x_{n})=(2^{n}/n)$ is decreasing. If $t=0$, then both sides are 0. Otherwise,
since $s=2^{k-1}\geq 16$, the left hand side is at least $s2^{s}(2^{s}-3)\cdot
1+0\geq 2s^{2}\geq st+rt$, which proves this subcase.

Case 1.2. $2^{k}\leq b<2^{k-1}+2^{k}$. Then we have $2^{k-1}\leq m-b=a\leq
b<2^{k-1}+2^{k}$. Split into two subcases.

Case 1.2.1. $2^{k}\leq a<2^{k-1}+2^{k}$. By induction hypothesis, we have

$\displaystyle[a]$ $\displaystyle=[2^{k-1}]+[a-2^{k-1}]+[2^{k-1},a-2^{k-1}],$
$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}].$

Moreover, $(a-2^{k-1})+(b-2^{k-1})=m-2^{k}=c$, so

$[c]\geq[a-2^{k-1}]+[b-2^{k-1}]+[a-2^{k-1},b-2^{k-1}].$

Substitute these into (10) and simplify, we see that it suffices to show

$2^{c}2^{2k-2}+2^{k}c+(a-2^{k-1})(b-2^{k-1})2^{2^{k}}\geq
ab+(a-2^{k-1})2^{k-1}2^{b}+(b-2^{k-1})2^{k-1}2^{a}.$

To simplify notations, let $s=2^{k-1},t=a-s,r=b-s$. Then $s\leq r,t<2s$ and
$c=t+r$. It now suffices to show
$s^{2}2^{t+r}+2s(t+r)+tr2^{2s}\geq(s+t)(s+r)+st2^{s+r}+sr2^{s+t}$. This is
equivalent to $(2^{t}s-2^{s}t)(2^{r}s-2^{s}r)\geq(t-s)(r-s)$. Since the
function $(2^{x}+1)/x$ is increasing on $[2,\infty)$ and $t\geq s=2^{k-1}\geq
16$, we have $(2^{t}+1)/t\geq(2^{s}+1)/s$. Hence $2^{t}s-2^{s}t\geq t-s$.
Similarly, $2^{r}s-2^{s}r\geq r-s$, which finishes the proof of this subcase.

Case 1.2.2. $2^{k-1}\leq a<2^{k}$. Then $2^{k}\leq
m-2^{k}=c=a+b-2^{k}<2^{k-1}+2^{k}$. So by induction hypothesis, we have

$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[c]$ $\displaystyle=[2^{k-1}]+[c-2^{k-1}]+[2^{k-1},c-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}].$

Moreover, $2^{k-1}+2^{k}\leq c+2^{k-1}<2^{k+1}$ and $a+(b-2^{k-1})=c+2^{k-1}$.
So

$\displaystyle[c+2^{k-1}]$
$\displaystyle=[2^{k}]+[c-2^{k-1}]+[2^{k},c-2^{k-1}]$
$\displaystyle\geq[a]+[b-2^{k-1}]+[a,b-2^{k-1}].$

Substitute these into (10), we see that it suffices to prove

$\displaystyle\phantom{==}a(b-2^{k-1})2^{2^{k-1}}+(c-2^{k-1})2^{k-1}2^{2^{k}}+c2^{k}$
$\displaystyle\geq(c-2^{k-1})2^{k}2^{2^{k-1}}+(b-2^{k-1})2^{k-1}2^{a}+ab.$

Let $s=2^{k-1},t=a-s,r=b-2s$. Then $c=s+t+r$ and $0\leq t,r<s$. Substitute and
simplify, we see that it suffices to show

$s(t+r)2^{2s}+(s+t)(s+r)2^{s}+(s-t)r\geq s(s+r)2^{s+t}+2s(t+r)2^{s}.$

Note that $(s-t)r\geq 0$, so after some rearrangement it suffices to show

$s(2^{s}-2)(r(2^{s}-2^{t})+(t2^{s}-s2^{t}))+(s+r)2^{-s}((s+t)2^{2s}-2s2^{s+t})\geq
0,$

which is true as each term is non-negative, proving this subcase.

Case 2. $2^{k-1}+2^{k}\leq m<2^{k+1}$. Then $2^{k-2}+2^{k-1}\leq b<2^{k+1}$.

Case 2.1. $2^{k-1}+2^{k}\leq b<2^{k+1}$. Then $1\leq a<2^{k-1}$. Use

$\displaystyle[b]$ $\displaystyle=[2^{k}]+[b-2^{k}]+[2^{k},b-2^{k}],$
$\displaystyle[c]$ $\displaystyle\geq[a]+[b-2^{k}]+[a,b-2^{k}].$

Case 2.2. $2^{k-2}+2^{k}\leq b<2^{k-1}+2^{k}$. Then $1\leq a<2^{k-2}+2^{k-1}$.

Case 2.2.1. $2^{k-1}\leq a<2^{k-2}+2^{k-1}$. Use

$\displaystyle[a]$ $\displaystyle=[2^{k-2}]+[a-2^{k-2}]+[2^{k-2},a-2^{k-2}],$
$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[b-2^{k-1}]$
$\displaystyle=[2^{k-1}]+[b-2^{k}]+[2^{k-1},b-2^{k}],$ $\displaystyle[c]$
$\displaystyle=[2^{k-1}]+[c-2^{k-1}]+[2^{k-1},c-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$
$\displaystyle[2^{k-1}]$
$\displaystyle=[2^{k-2}]+[2^{k-2}]+[2^{k-2},2^{k-2}],$
$\displaystyle[c-2^{k-2}]$
$\displaystyle=[2^{k-2}]+[c-2^{k-1}]+[2^{k-2},c-2^{k-1}]$
$\displaystyle\geq[a-2^{k-2}]+[b-2^{k}]+[a-2^{k-2},b-2^{k}].$

Case 2.2.2. $1\leq a<2^{k-1}$. Use

$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[b-2^{k-1}]$
$\displaystyle=[2^{k-1}]+[b-2^{k}]+[2^{k-1},b-2^{k}],$ $\displaystyle[2^{k}]$
$\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$ $\displaystyle[c]$
$\displaystyle\geq[a]+[b-2^{k}]+[a,b-2^{k}].$

Case 2.3. $2^{k}\leq b<2^{k-2}+2^{k}$. Then $2^{k-2}\leq a<2^{k}$.

Case 2.3.1. $2^{k-2}+2^{k-1}\leq a<2^{k}$. Use

$\displaystyle[a]$ $\displaystyle=[2^{k-1}]+[a-2^{k-1}]+[2^{k-1},a-2^{k-1}],$
$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[b-2^{k-1}]$ $\displaystyle=[2^{k-2}]+[b-3\cdot
2^{k-2}]+[2^{k-2},b-3\cdot 2^{k-2}],$ $\displaystyle[c]$
$\displaystyle=[2^{k-1}]+[c-2^{k-1}]+[2^{k-1},c-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$
$\displaystyle[2^{k-1}]$
$\displaystyle=[2^{k-2}]+[2^{k-2}]+[2^{k-1},2^{k-2}],$
$\displaystyle[c-2^{k-2}]$
$\displaystyle=[2^{k-2}]+[c-2^{k-1}]+[2^{k-2},c-2^{k-1}]$
$\displaystyle\geq[a-2^{k-1}]+[b-3\cdot 2^{k-2}]+[a-2^{k-1},b-3\cdot
2^{k-2}].$

Case 2.3.2. $2^{k-1}\leq a<2^{k-2}+2^{k-1}$. Use

$\displaystyle[a]$ $\displaystyle=[2^{k-2}]+[a-2^{k-2}]+[2^{k-2},a-2^{k-2}],$
$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[b-2^{k-1}]$ $\displaystyle=[2^{k-2}]+[b-3\cdot
2^{k-2}]+[2^{k-2},b-3\cdot 2^{k-2}],$ $\displaystyle[2^{k}]$
$\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$
$\displaystyle[2^{k-1}]$
$\displaystyle=[2^{k-2}]+[2^{k-2}]+[2^{k-1},2^{k-2}],$ $\displaystyle[c]$
$\displaystyle\geq[a-2^{k-2}]+[b-3\cdot 2^{k-2}]+[a-2^{k-2},b-3\cdot
2^{k-2}].$

Case 2.3.3. $2^{k-2}\leq a<2^{k-1}$. Use

$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$
$\displaystyle[c+2^{k-1}]$ $\displaystyle=[2^{k-1}]+[c]+[c,2^{k-1}]$
$\displaystyle\geq[a]+[b-2^{k-1}]+[a,b-2^{k-1}].$

Case 2.4. $2^{k-2}+2^{k-1}\leq b<2^{k}$. Then $2^{k-1}\leq a<2^{k}$.

Case 2.4.1. $2^{k-2}+2^{k-1}\leq a<2^{k}$. Use

$\displaystyle[a]$ $\displaystyle=[2^{k-1}]+[a-2^{k-1}]+[2^{k-1},a-2^{k-1}],$
$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$
$\displaystyle[c]$
$\displaystyle\geq[a-2^{k-1}]+[b-2^{k-1}]+[a-2^{k-1},b-2^{k-1}].$

Case 2.4.2. $2^{k-1}\leq a<2^{k-2}+2^{k-1}$. Use

$\displaystyle[a]$ $\displaystyle=[2^{k-2}]+[a-2^{k-2}]+[2^{k-2},a-2^{k-2}],$
$\displaystyle[b]$ $\displaystyle=[2^{k-1}]+[b-2^{k-1}]+[2^{k-1},b-2^{k-1}],$
$\displaystyle[2^{k}]$ $\displaystyle=[2^{k-1}]+[2^{k-1}]+[2^{k-1},2^{k-1}],$
$\displaystyle[c]$ $\displaystyle=[2^{k-2}]+[c-2^{k-2}]+[2^{k-2},c-2^{k-2}],$
$\displaystyle[c+2^{k-2}]$
$\displaystyle=[2^{k-1}]+[c-2^{k-2}]+[2^{k-1},c-2^{k-2}]$
$\displaystyle\geq[a-2^{k-2}]+[b-2^{k-1}]+[a-2^{k-2},b-2^{k-1}].\qed$

Theorem 5.4 proves the first part of Theorem 1.9 with the exception of $m=6$.
To prove the second part about the limiting behaviour of $H_{2}(m)$, we need
the following lemma. Let $g(k)=g(k,2)=\sum_{j=1}^{k}2^{j-1}/2^{2^{j}}$ and
$\lambda=\lambda(2)=\sum_{j=1}^{\infty}2^{j-1}/2^{2^{j}}$.

######  Lemma 5.5.

For all positive integers $m$ except $3,6$ and $7$, we have

$h_{2}(m)\leq g(\left\lfloor\log_{2}m\right\rfloor),$

with equality if and only if $m=5$ or $m$ is a power of $2$. In particular,
$\limsup_{m\to\infty}h_{2}(m)=\lambda$.

###### Proof.

We will use induction on $m$. Using the recurrence relation given by Theorem
5.4 and the initial values of $h_{2}(m)$ given in the table above, it is easy
to verify the claim for all $1\leq m\leq 23$. Now assume $m\geq 24$ and the
results holds all smaller $m$. Let $k$ be the unique integer such that
$2^{k-1}+2^{k}\leq m<2^{k}+2^{k+1}$, and note that $k\geq 4$. Let
$c=m-2^{k}\geq 8$. By Theorem 5.4, it suffices to show that

$2^{k}h_{2}(2^{k})+ch_{2}(c)+\frac{2^{k}c}{2^{m-1}}\leq
mg(\left\lfloor\log_{2}m\right\rfloor).$

Case 1. $2^{k-1}+2^{k}\leq m<2^{k+1}$. Then
$\left\lfloor\log_{2}m\right\rfloor=k$ and
$\left\lfloor\log_{2}c\right\rfloor=k-1$. By induction hypothesis, we have

$\displaystyle 2^{k}h_{2}(2^{k})+ch_{2}(c)+\frac{2^{k}c}{2^{m-1}}$
$\displaystyle\leq 2^{k}g(k)+cg(k-1)+\frac{2^{k}c}{2^{m-1}}$
$\displaystyle=mg(k-1)+2^{k}\frac{2^{k-1}}{2^{2^{k}}}+\frac{2^{k}c}{2^{m-1}}$
$\displaystyle\leq
mg(k-1)+2^{k}\frac{2^{k-1}}{2^{2^{k}}}+c\frac{2^{k-1}}{2^{2^{k}}}$
$\displaystyle=mg(k).$

Note that the first inequality is strict by induction hypothesis unless
$c=2^{k-1}$. But in that case the second inequality is strict.

Case 2. $2^{k+1}\leq m<2^{k}+2^{k+1}$. Then
$\left\lfloor\log_{2}m\right\rfloor=k+1$ and
$\left\lfloor\log_{2}c\right\rfloor=k$. By induction hypothesis, we have

$\displaystyle 2^{k}h_{2}(2^{k})+ch_{2}(c)+\frac{2^{k}c}{2^{m-1}}$
$\displaystyle\leq 2^{k}g(k)+cg(k)+\frac{2^{k}c}{2^{m-1}}$
$\displaystyle=mg(k)+\frac{2^{k}c}{2^{m-1}}$ $\displaystyle\leq
mg(k)+m\frac{2^{k}}{2^{2^{k+1}}}$ $\displaystyle=mg(k+1).$

Note that the first inequality is strict unless $c=2^{k}$. In that case both
inequalities are tight and $m=2^{k+1}$ is a power of 2.

Therefore, $\limsup_{m\to\infty}h_{2}(m)\leq\lim_{k\to\infty}g(k)=\lambda$.
Then, as $h_{2}(2^{k})=g(k)$ for every $k\geq 1$, we must have
$\limsup_{m\to\infty}h_{2}(m)=\lambda$. ∎

We can now put everything together and prove Theorem 1.9.

###### Proof of Theorem 1.9.

The first part of Theorem 1.9 when $m\not=6$ follows from
$h_{2}(m)=H_{2}(m)/m2^{m-1}$ and Theorem 5.4, while for $m=6$, it is easy to
verify that the optimal split is $6=3+3$.

For the second part, Lemma 5.5 gives that
$\limsup_{m\to\infty}h_{2}(m)=\lambda=\lambda(2)$, while Lemma 5.3 implies
$\liminf_{m\to\infty}h_{2}(m)\geq\liminf_{m\to\infty}\overline{h}_{2}(m,2)=\lambda(2)$.
Hence, $\lim_{m\to\infty}H_{2}(m)/m2^{m-1}=\lim_{m\to\infty}h_{2}(m)$ exists
and is equal to $\lambda(2)$. ∎

##  6 Further results and open questions

By suitably modifying Section 4 and Section 5, we can also prove the following
generalisation of Theorem 1.6 and Theorem 1.9 for all $\alpha\geq 2$.

######  Theorem 6.1.

For every $m\geq 3$ and $\alpha\geq 2$, we have

$H(m,\alpha)\leq\frac{\alpha^{6}+\alpha^{4}+\alpha+1}{\alpha^{6}(\alpha^{2}-1)}\cdot\frac{m\alpha^{m}}{2}.$

######  Theorem 6.2.

For every $m\geq 3$ except 6, let $k=k(m)$ be the unique integer such that
$2^{k}+2^{k-1}\leq m<2^{k}+2^{k+1}$. For $m=6$, let $k=k(6)=3$ if
$2\leq\alpha<\sqrt{2}+1$, and let $k=k(6)=4$ if $\alpha\geq\sqrt{2}+1$. Then
for all $\alpha\geq 2$, we have

$H_{2}(m,\alpha)=H_{2}(2^{k},\alpha)\alpha^{m-2^{k}}+H_{2}(m-2^{k},\alpha)\alpha^{2^{k}}+2^{k}(m-2^{k}).$

Moreover, if $\lambda(\alpha)=\sum_{j=1}^{\infty}2^{j-1}/\alpha^{2^{j}}$, then
$\lim_{m\to\infty}\frac{2H_{2}(m,\alpha)}{m\alpha^{m}}=\lambda(\alpha)$.

We also conjecture that the following generalised version of Conjecture 1.10
holds as well.

######  Conjecture 6.3.

$H(m,\alpha)=H_{2}(m,\alpha)$ for all $m\geq 3$ and $\alpha\geq 2$. In
particular,

$\lim_{m\to\infty}\frac{2H(m,\alpha)}{m\alpha^{m}}=\lim_{m\to\infty}\frac{2H_{2}(m,\alpha)}{m\alpha^{m}}=\lambda(\alpha).$

Observe that
$\frac{\alpha^{6}+\alpha^{4}+\alpha+1}{\alpha^{6}(\alpha^{2}-1)}\sim\alpha^{-2}$
and $\lambda(\alpha)\sim\alpha^{-2}$ as $\alpha\to\infty$, which lends some
support for our conjecture. One possible approach towards proving this
conjecture is to show that for every $[m]$, there exists an extremal TCM on
$[m]$ with exactly two maximal closed sets, as that would imply that there is
always an extremal TCM that is 2-recursive. To this end, it seems possible to
use similar arguments to those in the proof of Proposition 4.7, to either show
that every vertex in an extremal TCM must be contained in a closed set of
increasingly larger size, or show that if an extremal TCM is partitioned into
at least three closed sets, at least two of them can be combined into a larger
closed set.

In the cases when $r\geq 4$ and $1<\alpha<2$, the arguments proving Theorem
6.1 fail at some point and we do not have a good conjecture on when
$\operatorname{forb}(m,r,M),H(m,\alpha)$ are attained, although part of the
argument proving Theorem 6.2 still works for sufficiently large $m$, so it is
plausible that we still have
$\lim_{m\to\infty}2H_{2}(m,\alpha)/m\alpha^{m}=\lambda(\alpha)$. The values of
$H(m,\alpha)$ and $H_{2}(m,\alpha)$ when $\alpha<1$ are also of independent
interest, but we haven’t investigated them much as they do not correspond to
forbidden matrix problems.

## References

  * [1] N. Alon.  On the density of sets of vectors.  Discrete Mathematics, 46(2):199–202, 1983.
  * [2] R. Anstee.  A survey of forbidden configuration results.  The Electronic Journal of Combinatorics, 20(1), 2013.
  * [3] R. Anstee, J. Dawson, L. Lu, and A. Sali.  Multivalued matrices and forbidden configurations.  Discrete Mathematics, 346(9):113492, 2023.
  * [4] T. Dillon and A. Sali.  Exponential multivalued forbidden configurations.  Discrete Mathematics & Theoretical Computer Science, 23(1), 2021.
  * [5] K. Ellis, B. Liu, and A. Sali.  Multi-symbol forbidden configurations.  Discrete Applied Mathematics, 276:24–36, 2020.
  * [6] Z. Füredi and A. Sali.  Optimal multivalued shattering.  SIAM Journal on Discrete Mathematics, 26:737–744, 2012.
  * [7] J. Karamata.  Sur une inegalite relative aux fonctions convexes.  Publications de l’Institut Mathématique, 1(1):145–148, 1932.
  * [8] N. Sauer.  On the density of families of sets.  Journal of Combinatorial Theory, Series A, 13:145–147, 1972.
  * [9] S. Shelah.  A combinatorial problem: Stability and order for models and theories in infinitary language.  Pacific Journal of Mathematics, 41:247–261, 1972.
  * [10] V. Vapnik and A. Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  Theory of Probability and Its Applications, 16:264–280, 1971.