left-hand side has coefficient at least $\log f$ and thus $\ell^{\rm
max}_{I_{2}}(\bm{k})$ is at most the right-hand side, which is
$\frac{129}{100}+\frac{29}{100}\log 3<\frac{7}{4}$. So

$2d_{2}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+7d_{7}\geq\frac{69}{20}$ (45)

is a valid constraint. As above, this implies that for every
$ij\in\binom{[7]}{2}$ and
$(r,\phi,\bm{\alpha})\in\mathop{\textsc{feas}}^{*}(\bm{k})$, which is a
realisation of some $\bm{d}$, we have
$d(H^{n}_{i}(\phi,\bm{\alpha}))+d(H^{n}_{j}(\phi,\bm{\alpha}))\geq\frac{69}{20}-\frac{5}{2}+o_{n}(1)=\frac{19}{20}+o_{n}(1)$.
Thus Lemma 3.3 implies that
$d(H^{n}_{ij}(\phi,\bm{\alpha}))\leq\frac{3}{4}+o_{n}(1)$ for every $ij$. So

$11d_{2}+15d_{3}+18d_{4}+20d_{5}+21d_{6}+21d_{7}\leq\binom{7}{2}\frac{3}{4}$
(46)

is a valid constraint. Finally, consider the constraint set $I_{3}$ consisting
of the two valid constraints: (46) and $2d_{2}+\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt+7d_{7}\leq\frac{7}{2}$, the original universal
constraint in Problem $L$. Multiply the original constraint by
$\frac{1}{7}\log\frac{343}{128}$ and (46) by $\frac{1}{21}\log\frac{128}{49}$,
and add these together. Then each $d_{f}$ on the left-hand side has
coefficient at least $\log f$ and thus $\ell^{\rm max}_{I_{3}}(\bm{k})$ is at
most the right-hand side, which is $\frac{7}{4}$. Moreover, the coefficient of
$d_{f}$ is strictly greater than $\log f$ unless $f=4$, so every optimal
solution has $d_{f}=0$ for all $f\neq 4$. Thus the unique optimiser has
$4d_{4}=\frac{7}{2}$, and all other entries equal to $0$. This completes the
proof of (ii).

The same argument works for $s=6$ to prove (i). Here $(i_{2},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,i_{6})=(9,12,14,15,15)$. Again,
$d_{1}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+d_{6}\leq 1$ is a
valid constraint. We see that $2d_{2}+\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt+6d_{6}\geq\frac{289}{100}$ is a valid constraint, since its
negation alone implies that $\ell(\bm{d})=\sum_{2\leq f\leq
s}fd_{f}\cdot\frac{\log f}{f}\leq\frac{289}{100}\cdot\frac{\log
3}{3}\leq\frac{1}{2}\log 3+\frac{3}{4}$. From this, the sum of densities of
any pair of colour graphs is at most
$\frac{289}{100}-4\cdot\frac{1}{2}=\frac{89}{100}$ and so Lemma 3.3 implies
that their union has density at most $\frac{19}{25}$. Thus

$9d_{2}+12d_{3}+14d_{4}+15d_{5}+15d_{6}\leq\binom{6}{2}\frac{19}{25}$ (47)

is a valid constraint. This implies that

$2d_{2}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+6d_{6}\geq\frac{59}{20}$ (48)

is a valid constraint. Indeed, if we add $\frac{1}{3}\log\frac{9}{8}$ times
(47) plus $4-\frac{7}{3}\log 3$ times the negation of (48), we see
$\ell(\bm{d})\leq\frac{2}{5}+\frac{43}{60}\log 3<\frac{1}{2}\log
3+\frac{3}{4}$. Now the sum of densities of any pair of colour graphs is at
most $\frac{59}{20}-4\cdot\frac{1}{2}=\frac{19}{20}$ and so Lemma 3.3 implies
that their union has density at most $\frac{3}{4}$. Thus

$9d_{2}+12d_{3}+14d_{4}+15d_{5}+15d_{6}\leq\binom{6}{2}\frac{3}{4}$ (49)

is a valid constraint. Finally, we consider Problem $L$ with the set of two
valid constraints: (49) and $2d_{2}+\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt+6d_{6}\leq 3$, the original universal constraint in Problem
$L$. Multiply (49) by $\frac{1}{3}\log\frac{9}{8}$ and the original constraint
by $4-\frac{7}{3}$ and add these together to see that each $d_{f}$ on the
left-hand side has coefficient at least $\log f$, and is strictly greater than
$\log f$ only for $f=2,5,6$, and the right-hand side is $\frac{1}{2}\log
3+\frac{3}{4}$. Thus the unique optimal solution is $\ell^{\rm
max}_{I}(\bm{k})=\frac{1}{2}\log 3+\frac{3}{4}$ and the unique optimiser has
$d_{2}=d_{5}=d_{6}=0$ and is therefore
$\bm{d}=(0,\frac{1}{2},\frac{3}{8},0,0)$.

Proof of Theorem 3.1. This follows immediately from Lemmas 3.6 and 3.8.

Proof of Theorem 3.2. We need to show that every
$(r,\phi,\bm{\alpha})\in\mathop{\textsc{opt}}^{*}(\bm{k})$ is as described.
Lemma 3.8(i) implies that $Q(\bm{k})\leq\frac{1}{2}\log 3+\frac{3}{4}$, and
that, if there is equality, any optimal $(r,\phi,\bm{\alpha})$ is the
realisation of $\bm{d}=(0,\frac{1}{2},\frac{3}{8},0,0)$. Since
$\|\bm{d}\|_{1}=\frac{7}{8}$, Observation (B) implies that $r\geq 8$. Suppose
that $|\phi(1i)|=4$ for $i=2,3,4,5$. Then for all distinct
$i,i^{\prime}\in\\{2,3,4,5\\}$, we have $\phi(1i)\neq\phi(1i^{\prime})$,
otherwise $|\phi(ii^{\prime})|\leq 2$ (or there would be a monochromatic
triangle). Let
$\psi(ii^{\prime}):=\\{j\in[6]:j\notin\phi(1i)\cap\phi(1i^{\prime})\\}$. Then
$\phi(ii^{\prime})\subseteq\psi(ii^{\prime})$. We use a computer to obtain all
$\binom{15}{4}$ possible $\phi(12),\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,\phi(15)$ and corresponding $\\{\psi(ii^{\prime})\\}$. Then
check each triple $ii^{\prime}i^{\prime\prime}$: suppose
$\psi(ii^{\prime}),\psi(i^{\prime}i^{\prime\prime}),\psi(i^{\prime\prime}i^{\prime})$
share an element $j$. If they each have size three we have a contradiction
since we must delete $j$ from at least one of these sets so we end up with a
$\phi$-set of size two. If one has size $4$ and two have size $3$ then we must
delete $j$ from the set of size $4$ (that is, the corresponding $\phi$-sets
all have size at most $3$. After checking all triples, the resulting sets are
still supersets of $\phi(ii^{\prime})$ for distinct $i,i^{\prime}=2,3,4,5$. In
every case, the sets are of the form
$\\{abc,def,xyuv,xyuv^{\prime},xy^{\prime}uv,xy^{\prime}uv^{\prime}\\}$ where
$\\{a,b,c,d,e,f\\}=[6],\\{x,y,y^{\prime}\\}=\\{a,b,c\\},\\{u,v,v^{\prime}\\}=\\{d,e,f\\}$.
So without loss of generality, the resulting sets are
$\\{123\\},\\{456\\},\\{1245\\},\\{1246\\},\\{1345\\},\\{1346\\}$. Sets
$1,3,4$ of sizes $3,4,4$ respectively all contain $1,2$, so without loss of
generality we can reduce to

$\\{123\\},\\{456\\},\\{145\\},\\{246\\},\\{1345\\},\\{1346\\}.$

But now sets 2,4,6 of sizes $3,3,4$ respectively all contain $4,6$ which is a
contradiction because deleting one copy of each gives a $\phi$-set of size at
most two. Thus we have eliminated all possible cases. We implemented the above
in python (6check.py). Thus when $r\geq 8$, for each $i\in[r]$ there is a set
$X_{i}\subseteq[r]\setminus\\{i\\}$ of size at most $3$ such that
$|\phi(ij)|=4$ if and only if $j\in X_{i}$. Therefore $2\cdot
6\lfloor\frac{r^{2}}{4}\rfloor\geq 2\sum_{c\in[6]}|\phi^{-1}(c)|\geq
r\cdot(12+3(r-4))=3r^{2}$. Thus $r$ is even, every $|X_{i}|=3$, and
$\phi^{-1}(c)\cong K_{\frac{r}{2},\frac{r}{2}}$ for all $c\in[6]$.

For $c\in[6]$, let $A_{c},B_{c}$ be the vertex classes of $\phi^{-1}(c)$. Let
$A=(a_{ij})$ be an $r\times 6$ matrix with $\pm 1$ entries, where the $c$-th
column represents $\phi^{-1}(c)$, with $a_{jc}=1$ if $j\in A_{c}$ and
$a_{jc}=-1$ if $j\in B_{c}$. By relabelling classes, without loss of
generality, the $r$-th row of $A$ is $(1,1,1,1,1,1)$. Notice that $|\phi(ij)|$
is the number of columns $c\in[6]$ where $a_{jc}$ and $a_{ic}$ differ. So
$|\phi(rj)|$ is the number of entries equal to $-1$ in the $j$-th row. But
$|\phi(rj)|=3$ for all but $3$ rows $j$.

If $r\geq 10$, then $|\phi(rj)|=3$ for at least $r-1-3\geq 6$ other rows $j$.
Each of these rows, without loss of generality $j=1,2,3,4,5,6$, therefore
contains exactly $3$ entries equal to $-1$. By parity, no pair of these rows
can differ in exactly three places. Thus $|\phi(ij)|\neq 3$ and hence
$|\phi(ij)|=4$ for all $ij\in\binom{[6]}{2}$, so e.g. $|X_{1}|\geq 5$, a
contradiction.

Recalling that $r\geq 8$ and $r$ is even, we must have $r=8$. For $\ell=3,4$,
let $G_{\ell}:=\\{ij\in\binom{[8]}{2}:|\phi(ij)|=\ell\\}$. Since also
$\|\bm{d}\|_{1}=\frac{7}{8}$, $\bm{\alpha}$ is uniform. One can check via
computer (6config.py) that whenever $\phi^{-1}(c)\cong K_{4,4}$ for all
$c\in[6]$ are such that every edge multiplicity is $3$ or $4$, then
$G_{3}\cong K_{4,4}$ and $G_{4}\cong K_{4}\cup K_{4}$. (To reduce
computations, first we assume all $\phi^{-1}(c)$ are distinct. Next, if they
are not, one needs at least $3=\log 8$ copies of $K_{4,4}$ to cover every edge
of $K_{8}$ at least once, so at least five such graphs are required to cover
every edge at least three times. So it remains to check the cases where
$\phi^{-1}(1),\phi^{-1}(2)$ are identical and the other colour graphs are
distinct.) Given this structure, $3G_{3}\cup 4G_{4}$ has a decomposition into
$6$ copies of $K_{4,4}$ if and only if $4K_{8}$ has a decomposition into $7$
copies of $K_{4,4}$. Thus the columns of $A$ are among the $7$ rightmost
columns of a normalised order-$8$ Hadamard matrix $H$ (up to permutation of
rows and/or negation of rows).

###  3.4 Hadamard matrices and the triangle problem

Figure 2: Extremal graphs for $(3;s)$ for $2\leq s\leq 7$.

Figure 2 shows how the known extremal graphs for the triangle problem relate
to Hadamard matrices. For $s\in[7]\setminus\\{5\\}$, these are all unique, and
for $s=5$ there is an infinite family of asymptotically extremal graphs, of
which two are drawn here. Index the columns of the above matrices by
$0,1,\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt$. For each $c\in[s]$,
$\phi^{-1}(c)$ is a complete balanced bipartite graph whose vertex classes are
given by the set of row indices of the white squares, and of the black
squares, in column $c$. Some columns are repeated, denoted by $\times\ell$,
and some are removed, denoted by $-$. Taking $r$ to be the order of the
matrix, and $\bm{u}\in\Delta^{r}$ to be uniform, we have the optimal solution
$(r,\phi,\bm{u})$.

##  4 Applications of Theorem 1.6

Here we discuss the perfect colouring problem (Problem 1.7), where we have
part sizes that maximise the number of perfect colourings. This was implicitly
done in previous works (and is trivial in some cases). Let $r\in\mathbb{N}$
and let $H\subseteq K_{r}$ be regular. Suppose that every
$(r^{*},\phi^{*},\bm{\alpha}^{*})\in\mathop{\textsc{opt}}^{*}(\bm{k})$ has
$r^{*}=r$, $\bm{\alpha}^{*}=\bm{u}_{r}$ uniform and furthermore, there is
$M_{\phi^{*}}\cong H$ such that $|\phi^{*}(ij)|=t_{1}$ for all $ij\in
M_{\phi^{*}}$ and $|\phi^{*}(ij)|=t_{2}$ for all $ij\in\binom{[r]}{2}\setminus
M_{\phi^{*}}$, where $0\leq t_{1}-t_{2}\leq 1$. Then we denote
$\mathrm{perf}(\bm{m}):=\mathrm{perf}_{r,\bm{u}_{r}}(\bm{m})$.

Note that by symmetry, there is some integer $C$ such that

$\mathrm{perf}(\bm{m})=C\cdot\sum_{J\cong H}f(\bm{m},J),\quad\text{where
}f(\bm{m},J):=\prod_{ij\in
J}t_{1}^{m_{i}m_{j}}\prod_{i^{\prime}j^{\prime}\notin
J}t_{2}^{m_{i^{\prime}}m_{j^{\prime}}},$

where the sum is over all copies $J$ of $H$ in $K_{r}$. Let
$\bm{m}^{\prime}:=(m_{1}-1,m_{2},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m_{r-1},m_{r}+1)$. Write $m_{J(i)}:=\sum_{j\in N_{J}(i)}m_{j}$. Then

$\displaystyle C^{-1}\mathrm{perf}(\bm{m}^{\prime})$
$\displaystyle=\sum_{\begin{subarray}{c}J:\\{1,r\\}\notin J\\\ J\cong
H\end{subarray}}g_{\rm
out}(\bm{m},J)f(\bm{m},J)+\sum_{\begin{subarray}{c}J:\\{1,r\\}\in J\\\ J\cong
H\end{subarray}}g_{\rm in}(\bm{m},J)f(\bm{m},J),$

where

$\displaystyle g_{\rm out}(\bm{m},J)$
$\displaystyle:=\left(\frac{t_{2}}{t_{1}}\right)^{m_{J(1)}-m_{J(r)}}t_{2}^{m_{1}-m_{r}-1}\quad\text{and}\quad
g_{\rm
in}(\bm{m},J):=\left(\frac{t_{2}}{t_{1}}\right)^{m_{J(1)}-m_{J(r)}}t_{2}^{m_{1}-m_{r}}t_{1}^{-1}.$
(50)

Indeed, if we let $n:=m_{1}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+m_{r}$ and $\bm{m}^{\prime\prime}:=(m_{1}-1,m_{2},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,m_{r})$, then
$\mathrm{perf}(\bm{m})/\mathrm{perf}(\bm{m}^{\prime\prime})=t_{1}^{m_{J(1)}}\cdot
t_{2}^{n-m_{J(1)}-m_{1}}$. Now combine this with the analogous formula for
$\mathrm{perf}(\bm{m}^{\prime})/\mathrm{perf}(\bm{m}^{\prime\prime})$, where
e.g. the power of $t_{1}$ is $\sum_{j\in N_{J}(r)}m_{j}^{\prime}$ which is
$m_{J(r)}$ if $\\{1,r\\}\notin J$ and $m_{J(r)}-1$ otherwise.

Proof of Corollary 1.10. Recall that we consider only non-increasing sequences
$\bm{m}$. In each case, letting $r$ be the (unique) number of vertices in
every solution in $\mathop{\textsc{opt}}^{*}(\bm{k})$, we will show that
whenever $m_{1}-m_{r}\geq 2$, we have $g_{\rm out}(\bm{m},J)\geq 1.01$, say,
for all copies $J$ of $H$ with $\\{1,r\\}\notin J$ and $g_{\rm
in}(\bm{m},J)\geq 1.01$ for all $J$ with $\\{1,r\\}\in J$. Thus we have
$\frac{1}{1.01}\cdot\mathrm{perf}(\bm{m}^{\prime})\geq C\cdot\sum_{J\cong
H}f(\bm{m},J)=\mathrm{perf}(\bm{m})$. This implies that the unique
supersolution to the perfect colouring problem for $n$ is
$\bm{m}^{*}=(m_{1}^{*},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m_{r}^{*})$ where $\|\bm{m}^{*}\|_{1}=n$ and $m_{1}^{*}-m_{r}^{*}\leq
1$, and the perfect colouring problem is soluble with constant $c:=0.01$. If
$\bm{k}$ has the strong extension property, Corollary 1.9 implies that for all
sufficiently large $n$, the unique $\bm{k}$-extremal graph on $n$ vertices is
$K_{m_{1}^{*},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m_{r}^{*}}\cong T_{r}(n)$.

All $\bm{k}$ from Theorem 1.1 apart from $(3;5)$ have the strong extension
property by Lemma 1.3. Indeed, we showed in [stability2, Theorem 1.7] that
each $\bm{k}$ among $(k;2),(k;3),(3;4),(4;4)$ has the strong extension
property for integers $k\geq 3$, and described the optimal solutions
[stability2, Table 2]. Write $g_{\rm in}$ and $g_{\rm out}$ when $\bm{m},J$
are fixed or clear from the context. Suppose $\bm{k}:=(k;s)$ is one of
$(k;2),(k;3),(4;4)$. Then every
$(r,\phi,\bm{\alpha})\in\mathop{\textsc{opt}}^{*}(\bm{k})$ has $\bm{\alpha}$
uniform and $\phi$ only takes one value $t$. Then for all $\bm{m}$ with
$m_{1}-m_{r}\geq 2$, $g_{\rm in}=g_{\rm out}=t^{m_{1}-m_{r}-1}\geq t\geq 2$,
as required.

Now suppose $\bm{k}:=(3;4)$. In the above discussion, $r=4$, $H\cong K_{2,2}$,
so $(t_{1},t_{2})=(3,2)$. Let $J$ be a copy of $H$. If $\\{1,4\\}\notin J$,
then $J(1)=J(4)=\\{2,3\\}$ while if $\\{1,4\\}\in J$, then $J(1)=\\{i,4\\}$
and $J(4)=\\{j,1\\}$, where $\\{i,j\\}=\\{2,3\\}$. Let $\bm{m}=(m_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,m_{4})$ be such that
$m_{1}-m_{4}\geq 2$. Here, $g_{\rm out}=2^{m_{1}-m_{4}-1}\geq 2$ and $g_{\rm
in}=3^{m_{1}-m_{4}-1}\left(\frac{2}{3}\right)^{m_{i}-m_{j}}$. If
$m_{i}-m_{j}\leq 1$ then this is at least $2$; otherwise $2\leq
m_{i}-m_{j}\leq m_{1}-m_{4}$ and it is at least $\frac{4}{3}$.

Suppose finally that $\bm{k}=(3;6)$. Here Theorem 3.2 implies that $r=8$ and
$H$ is the disjoint union of two copies of $K_{4}$. So $(t_{1},t_{2})=(4,3)$.
Let $J$ be a copy of $H$. If $\\{1,8\\}\in J$, then
$m_{J(1)}-m_{J(8)}=m_{8}-m_{1}$, so $g_{\rm in}=4^{m_{1}-m_{8}-1}\geq 4$. It
remains to check $g_{\rm out}$. So suppose that $\\{1,8\\}\notin J$. Then
$J(1),J(8)$ are disjoint sets of size three, and $3m_{8}\leq
m_{J(1)},m_{J(8)}\leq 3m_{1}$. Thus there is an integer $0\leq j\leq
6(m_{1}-m_{8})$ such that $m_{J(1)}-m_{J(8)}=3(m_{1}-m_{8})-j$. So

$g_{\rm
out}=\left(\frac{81}{64}\right)^{m_{1}-m_{8}}\cdot\left(\frac{4}{3}\right)^{j}\cdot\frac{1}{3}.$

If $m_{1}-m_{8}\geq 5$ then $g_{\rm out}\geq 1.08$, as required. If
$m_{1}-m_{8}=4$ and $j\geq 1$ then $g_{\rm out}\geq 1.14$. If $m_{1}-m_{8}=3$
and $j\geq 2$ then $g_{\rm out}\geq 1.2$, and if $m_{1}-m_{8}=2$ then $j\geq
3$ then $g_{\rm out}\geq 1.2$. There are only a few remaining possibilities,
namely, writing $\bm{m}=(m_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m_{1})+\bm{b}$,

$m_{1}-m_{8}$ | $j$ | $\bm{b}$ | $\bm{b}^{\prime}$
---|---|---|---
$4$ | $0$ | $(0,0,0,0,-4,-4,-4,-4)$ | $(-2,-2,-2,-2,-2,-2,-2,-2)$
$3$ | $0$ | $(0,0,0,0,-3,-3,-3,-3)$ | $(-1,-1,-1,-1,-2,-2,-2,-2)$
$3$ | $1$ | $(0,0,0,0,-2,-3,-3,-3)$ | $(-1,-1,-1,-1,-1,-2,-2,-2)$
|  | $(0,0,0,-1,-3,-3,-3,-3)$ |
$2$ | $0$ | $(0,0,0,0,-2,-2,-2,-2)$ | $(-1,-1,-1,-1,-1,-1,-1,-1)$
$2$ | $1$ | $(0,0,0,0,-1,-2,-2,-2)$ | $(0,-1,-1,-1,-1,-1,-1,-1)$
|  | $(0,0,0,-1,-2,-2,-2,-2)$ |
$2$ | $2$ | $(0,0,0,0,-1,-1,-2,-2)$ | $(0,0,-1,-1,-1,-1,-1,-1)$
|  | $(0,0,0,-1,-1,-2,-2,-2)$ |
|  | $(0,0,-1,-1,-2,-2,-2,-2)$ |

In all cases, we compare by direct calculation to
$\bm{\overline{m}}:=(m_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m_{1})+\bm{b}^{\prime}$, where $\bm{b}^{\prime}$ has its sum of entries
equal to that of $\bm{b}$, and all entries as equal as possible. Indeed,

$\frac{\mathrm{perf}(\bm{\overline{m}})}{\mathrm{perf}(\bm{m})}=\frac{\sum_{A^{\prime}\cup
B^{\prime}=[8]}\prod_{ij\in\binom{A^{\prime}}{2}}4^{b_{i}^{\prime}b_{j}^{\prime}}\prod_{ij\in\binom{B^{\prime}}{2}}4^{b_{i}^{\prime}b_{j}^{\prime}}\prod_{i\in
A^{\prime},j\in B^{\prime}}3^{b_{i}^{\prime}b_{j}^{\prime}}}{\sum_{A\cup
B=[8]}\prod_{ij\in\binom{A}{2}}4^{b_{i}b_{j}}\prod_{ij\in\binom{B}{2}}4^{b_{i}b_{j}}\prod_{i\in
A,j\in B}3^{b_{i}b_{j}}}$

depends only on $\bm{b},\bm{b}^{\prime}$. We did this calculation in python
(dcheck.py). In all cases, the ratio is at least $9$. As before this implies
that the unique supersolution has all entries as equal as possible.

Finally, we need to check that $(3;6)$ has the strong extension property. So
let $9$ be a new vertex and let $\phi^{\prime}$ be an extension of $\phi$ with
the property that

$\frac{1}{8}\sum_{i\in[8]}\log t_{i}=\frac{3}{4}+\frac{1}{2}\log
3\quad\text{i.e.}\quad t_{1}\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5ptt_{8}=2^{6}3^{4},$

where $t_{i}:=\max\\{|\phi^{\prime}(i9)|,1\\}$. Since each $\phi^{-1}(c)\cong
K_{4,4}$ and $\phi^{\prime-1}(c)$ is triangle-free, in this graph $9$ has at
most $4$ neighbours, and $\phi^{\prime-1}(c)\subseteq K_{5,4}$. Let $G_{c}$ be
the copy of $K_{5,4}$ containing $\phi^{\prime-1}(c)$, such that
$G_{c}-\\{9\\}\cong K_{4,4}$, so we obtain $G_{c}$ from $\phi^{-1}(c)$ by
adding $9$ to one of the two vertex classes of $\phi^{-1}(c)$. One can easily
check all such attachments using a computer, trying each of the $2^{6}$
choices (we implemented this using python (7ext.py)). This reveals that
$\\{G_{c}:c\in[6]\\}$ has $\prod_{i\in[8]}|\\{c\in[6]:i9\in
G_{c}\\}|=2^{6}3^{4}$ if and only if $\phi^{-1}(c)\equiv K_{5,4}$ and there is
some $i\in[8]$ such that $9$ lies in exactly the same vertex class as $i$ in
each $\phi^{-1}(c)$; that is, $9$ is a strong clone of $i$ (in other words,
$9$ corresponds to a copy of an existing row in the $\pm 1$-matrix
representing the optimal solution). Thus $\phi^{\prime-1}(c)=G_{c}$. We have
proved that $(3;6)$ has the strong extension property.

Therefore we can apply Theorem 1.6 with Theorem 3.2 to see that $T_{8}(n)$ is
the unique extremal graph for sufficiently large $n$. Moreover, letting $0\leq
j\leq 7$ be such that $n=8N+j$ for $N\in\mathbb{N}$, we see that the unique
supersolution $\bm{m}$ has $j$ terms equal to $N+1$ and $8-j$ equal to $N$,
and $\mathrm{perf}(\bm{m})$ equals $C_{j}^{\prime}\cdot 4^{12N}\cdot 3^{16N}$
where $C_{j}^{\prime}$ is a constant depending only on $j$, which can be
determined by calculating $|\mathop{\textsc{pat}}(8,\bm{u})|$, by counting
certain distinct Hadamard matrices (see the end of the proof of Theorem 1.11).
This gives the claimed value of $F(n;(3;6))$.

Proof of Theorem 1.11. Let $\bm{k}:=(3;7)$. By Theorem 3.1, every element of
$\mathop{\textsc{opt}}^{*}(\bm{k})$ is of the form $(8,\phi,\bm{u})$, where
$\bm{u}$ is uniform and $|\phi(ij)|=4$ for all $ij\in\binom{[8]}{2}$.

We need to show that $\bm{k}$ has the strong extension property. So let $9$ be
a new vertex and let $\phi^{\prime}$ be an extension of $\phi$ with the
property that

$\frac{1}{8}\sum_{i\in[8]}\log t_{i}=\frac{7}{4}\quad\text{i.e.}\quad
t_{1}\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5ptt_{8}=2^{14}$

where $t_{i}:=\max\\{|\phi^{\prime}(i9)|,1\\}$. So every $t_{i}$ equals $1$,
$2$, or $4$, and in fact the multiset of values is either
$\\{4,4,4,4,4,4,4,1\\}$ or $\\{4,4,4,4,4,4,2,2\\}$. Since each
$\phi^{-1}(c)\cong K_{4,4}$ and $\phi^{\prime-1}(c)$ is triangle-free, in this
graph $9$ has at most $4$ neighbours, and $\phi^{\prime-1}(c)\subseteq
K_{5,4}$. Let $G_{c}$ be the copy of $K_{5,4}$ containing
$\phi^{\prime-1}(c)$, such that $G_{c}-\\{9\\}\cong K_{4,4}$, so we obtain
$G_{c}$ from $\phi^{-1}(c)$ by adding $9$ to one of the two vertex classes of
$\phi^{-1}(c)$. One can easily check all such attachments using a computer,
trying each of the $2^{7}$ choices (we implemented this using python
(7ext.py)). This reveals that $\\{G_{c}:c\in[7]\\}$ has
$\prod_{i\in[8]}|\\{c\in[7]:i9\in G_{c}\\}|=2^{14}$ if and only if
$\phi^{-1}(c)\equiv K_{5,4}$ and there is some $i\in[8]$ such that $9$ lies in
exactly the same vertex class as $i$ in each $\phi^{-1}(c)$; that is, $9$ is a
strong clone of $i$ (in other words, $9$ corresponds to a copy of an existing
row in the Hadamard matrix representing the optimal solution). Thus $\bm{k}$
has the strong extension property.

Since $|\phi|$ only takes the value $4$, the same argument as at the beginning
of the proof of Corollary 1.10 implies that the perfect colouring problem is
soluble (with constant $c:=4$) and for all integers $n$, the unique
supersolution $\bm{m}_{n}=(m_{n,1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,m_{n,8})$ of the perfect colouring problem has
$|m_{n,i}-m_{n,j}|\leq 1$ for all $ij$. Corollary 1.9 implies that the unique
extremal graph is $K_{\bm{m}_{n}}(n)\cong T_{8}(n)$. Let $C$ be the number of
Hadamard matrices with first column and last row consisting of $1$-s. Then
$F(n;\bm{k})=(C+o(1))\cdot 4^{t_{8}(n)}$. Note that one can calculate $C$ if
desired. Indeed, two Hadamard matrices are _equivalent_ if one can be obtained
from the other by a sequence of permutations and/or negations of rows and/or
columns. It is known that, up to equivalence, there is one Hadamard matrix $H$
of order $8$. So $C$ is the number of distinct matrices that can be obtained
from $H$ by permuting the first $7$ rows and the last $7$ columns and making
the first column and the last row consist of all $1$-s.

##  5 The $(k+1,k)$-extremal graphs

In this section, we consider the simplest case when $\bm{k}$ has the weak
extension property, namely $\bm{k}=(k+1,k)$ for $k\geq 3$. For small $k$, we
determine the $(k+1,k)$-extremal graph, which turns out to have a part of size
$O(k)$, and the size of this part depends on the value of $n$ modulo $k-1$.
The proof relies heavily on Theorem 2.12, the full strength of which we have
not yet required.

###### Definition 5.1

For all integers $k\geq 3$ and $n\geq 4$,

  * •

for $q\geq 2$, let $\mathcal{J}_{q}(n)$ be the family of complete $k$-partite
graphs with parts of size $m_{1}\geq\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt\geq m_{k-1}\geq\ell$ where $m_{1}-m_{k-1}\leq q$,
$2\leq\ell\leq q$ and $m_{1}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+m_{k-1}+\ell=n$;

  * •

let $\mathcal{J}_{q}^{*}(n)$ be the set of graphs in $\mathcal{J}_{q}(n)$
which are $(k+1,k)$-extremal;

  * •

for $\ell\geq 1$, let $J^{\ell}(n)$ denote the complete $k$-partite graph with
parts of size $m_{1}\geq\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt\geq m_{k-1}\geq\ell$ where $m_{1}-m_{k-1}\leq 1$ and $m_{1}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+m_{k-1}+\ell=n$.

In this section we prove the following theorem, which includes Theorem 1.13.

###### Theorem 5.2

For all integers $k\geq 3$, there exists $n_{0}>0$ such that for all
$n>n_{0}$, every $n$-vertex $(k+1,k)$-extremal graph is in
$\mathcal{J}_{2(k-1)}(n)$. Moreover, $F(n;k+1,k)=O_{k}(1)\cdot
2^{t_{k-1}(n)}$, where the constant $O_{k}(1)$ is at least $2$.

Recall from (3) that $F(k+1,k)=Q(k+1,k)$. It is easy to solve Problem $Q^{*}$
for $s=2$ colours (see [stability2, Lemma 1.8]): the unique solution is
$(k-1,\phi,\bm{u})$ where $\bm{u}$ is uniform and $\phi(ij)=[2]$ for all $ij$.
Thus when $k$ is fixed and $n\to\infty$,

$Q(k+1,k)=\textstyle{\frac{k-2}{k-1}}\quad\text{and}\quad\log
F(n;k+1,k)=\left(\textstyle{\frac{k-2}{k-1}}+o(1)\right)\binom{n}{2}.$

So, while (3) determines $\log F(n;k+1,k)/\binom{n}{2}$ asymptotically,
Theorem 5.2 determines $F(n;k+1,k)$ up to a multiplicative constant.

The next proposition is numerical.

###### Proposition 5.3

Let $k\geq 3$ and $0\leq j\leq k-2$ be integers. Given $m_{1}\geq\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\geq m_{k-1}\geq\ell$, let
$\bm{m}:=(m_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,m_{k-1})$
and

$\displaystyle h(\bm{m};\ell)$
$\displaystyle:=\left(\prod_{ii^{\prime}\in\binom{[k-1]}{2}}2^{m_{i}m_{i^{\prime}}}\right)2^{\ell(m_{1}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+m_{k-1})}\left(2^{-m_{1}}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+2^{-m_{k-1}}\right)^{\ell},$
$\displaystyle h^{*}(\bm{m};\ell)$
$\displaystyle:=\left(\prod_{ii^{\prime}\in\binom{[k-1]}{2}}2^{m_{i}m_{i^{\prime}}}\right)2^{\ell(m_{1}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+m_{k-1})}\left(\sum_{i\in[k-1]}2^{-m_{i}}-\sum_{ii^{\prime}\in\binom{[k-1]}{2}}2^{-m_{i}-m_{i^{\prime}}}\right)^{\ell}.$

Let

$f(k,j,\ell):=\frac{h(\bm{m}^{*};\ell)}{2^{t_{k-1}(n)}}\quad\text{and}\quad
f(k,j):=\max_{0\leq\ell\leq k-1}f(k,j,\ell),$

where $m^{*}_{1}\geq\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\geq
m^{*}_{k-1}\geq\ell$, $m^{*}_{1}-m^{*}_{k-1}\leq 1$ and $m^{*}_{1}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+m^{*}_{k-1}+\ell=n$ (so
$m^{*}_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m^{*}_{k-1},\ell$ are the part sizes of $J^{\ell}(n)$). Let
$\bm{m}^{*}:=(m^{*}_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m^{*}_{k-1})$.

  1. (i)

Let $n\equiv j~{}(\\!\\!\\!\\!\mod k-1)$ with $0\leq j<k-1$ and $n\geq k^{3}$.
Consider the following way of colouring $J\in\mathcal{J}_{n}(n)$ with parts of
size $m_{1}\geq\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\geq
m_{k-1}\geq\ell$: for each $x$ in the $\ell$-part, pick $i_{x}\in[k-1]$ and
colour every edge between $x$ and the $m_{i}$-part with colour $1$. All other
edges are coloured arbitrarily. The number of colourings is between
$h^{*}(\bm{m};\ell)$ and $h(\bm{m};\ell)$.

  2. (ii)

If $0\leq\ell\leq k-1$, then

$f(k,j,\ell)=\begin{cases}2^{-\binom{\ell}{2}}\left(k-1-\frac{j-\ell}{2}\right)^{\ell}&\mbox{if
}0\leq\ell\leq j\\\
2^{j-\binom{\ell+1}{2}}\left(k-1+\ell-j\right)^{\ell}&\mbox{if }j<\ell\leq
k-1.\end{cases}$

  3. (iii)

Let $n\equiv j~{}(\\!\\!\\!\\!\mod k-1)$ with $n\geq k^{3}$. For $3\leq k\leq
10$, the maximum of $h(\bm{m};\ell)$ over all (part sizes of)
$J\in\mathcal{J}_{2(k-1)}(n)$ is attained by $J^{\ell(k,j)}(n)$, where
$\ell(k,j)$ is the $(k,j)$-th entry in the table below:

| $j=0$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  |  |
---|---|---|---|---|---|---|---|---|---|---|---|---
$k=3$ | 2 | 2 |  |  |  |  |  |  |  |  |  |
4 | 3 | 2 | 2 |  |  |  |  |  |  |  |  |
5 | 3 | 3 | 2 | 3 |  |  |  |  |  |  |  |
6 | 3 | 3 | 3 | 3 | 3 |  |  |  |  |  |  |
7 | 3 | 3 | 3 | 3 | 3 | 3 |  |  |  |  |  |
8 | 3 | 3 | 3 | 3 | 4 | 4 | 3 |  |  |  |  |
9 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 |  |  |  |
10 | 4 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 |  |  |

and the value is separated from the value for any other
$J\in\mathcal{J}_{2(k-1)}(n)$ by factor $1+\Omega(1)$.

  4. (iv)

For all $0\leq j\leq k-2$ we have $f(k,j)\geq\max\\{(k+1)^{2}/8,2\\}$.

Proof sketch. For (i), the assertion about $h$ is clear. Further, $h$
overcounts those colourings with all colour-$1$ edges to at least two other
parts. By a Bonferroni-type inequality, $h^{*}$ is a lower bound.

Let us turn to the remaining claims. Take any admissible $(\bm{m};\ell)$.
Define the integer $b$ by $n=b(k-1)+j$ and $0\leq j<k-1$. Define
$b_{i}:=m_{i}-b$. Then $b_{1}-b_{k-1}\leq 2(k-1)$. Moreover, $b_{1}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+b_{k-1}+\ell=\sum_{i}m_{i}-(k-1)b+\ell=n-(k-1)b=j$. Then

$h(\bm{m};\ell)=2^{\binom{k-1}{2}b^{2}+(k-2)bj}\cdot
2^{\ell\sum_{i}b_{i}}\left(2^{-b_{1}}+\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip
1.5pt+2^{-b_{k-1}}\right)^{\ell}\prod_{ii^{\prime}}2^{b_{i}b_{i^{\prime}}}.$
(51)

First we prove (iii). For this, one needs to compare the values of

$\tilde{h}(\bm{b};\ell):=2^{\ell\sum_{i}b_{i}}(2^{-b_{1}}+\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-b_{k-1}})^{\ell}\prod_{ii^{\prime}}2^{b_{i}b_{i^{\prime}}}$ (52)

among all tuples $\bm{b}:=(b_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,b_{k-1})$ and $\ell$ with sum $j$ and $|b_{i}-b_{i^{\prime}}|,\ell\leq
2(k-1)$. We implemented this in python (smallpart.py), and the optimal value
of $\ell$ (which is indeed unique) for $3\leq k\leq 10$ was recorded in the
table. In all cases, we also had $b_{1}-b_{k-1}\leq 1$, so the optimal
$m_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,m_{k-1}$ are as
equal as possible. Thus the maximum is attained by some $J^{\ell}(n)$. For
future reference, we note that we could have defined $b_{i}$ by subtracting
any $b^{\prime}\leq b$ from $m_{i}$, and then to compare values of
$h(\bm{b};\ell)$, one must compare values of $\tilde{h}(\bm{b};\ell)$ over
tuples $\bm{b}$ with sum $j+(k-1)(b-b^{\prime})$.

Note that

$t_{k-1}(n)=t_{k-1}((k-1)b+j)=\binom{k-1}{2}b^{2}+(k-2)bj+\binom{j}{2}.$

For $0\leq\ell\leq j$, (51) implies that the function $f(k,j,\ell)$ equals
$2^{-\binom{j}{2}}\cdot\tilde{h}((1,\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,1,0,\dots,0);\ell)$ where there are $j-\ell$ entries of
value $1$. For $j<\ell\leq k-1$, it equals
$2^{-\binom{j}{2}}\cdot\tilde{h}((0,\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,0,-1,\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,-1);\ell)$ where there are $\ell-j$ entries of value $-1$. This proves
(ii).

For (iv), we bound $f(k,j,2)$ from below. For $j\geq 2$, we have

$f(k,j,2)=\frac{1}{2}\cdot(k-j/2)^{2}\geq\frac{1}{2}\cdot(k-(k-2)/2)^{2}=\frac{(k+2)^{2}}{8}.$

We have $f(k,0,2)=(k+1)^{2}/8$ and $f(k,1,2)=k^{2}/4$. For $k\geq 11$ (i.e.
not in the table), the smallest of these is $(k+1)^{2}/8\geq 18$.

The next lemma states that whenever every vertex and pair of vertices in a
near-extremal complete partite graph $G$ has almost optimal contribution to
$F(G;\bm{k})$, then $G$ is only optimal if it lies in
$\mathcal{J}_{2(k-1)}(n)$.

###### Lemma 5.4

There exist ${\varepsilon}>0$ and $n_{0}\in\mathbb{N}$ such that the following
holds. Let $G$ be a graph on $n\geq n_{0}$ vertices which is complete
multipartite, and such that $\log
F(G;k+1,k)\geq\left(\frac{k-2}{k-1}-{\varepsilon}\right)\binom{n}{2}$ and

$\displaystyle\log F(G;k+1,k)-\log
F(G-x;k+1,k)\geq(\textstyle{\frac{k-2}{k-1}}-2{\varepsilon})n\quad\forall\
x\in V(G),$ (53) $\displaystyle\log F(G;k+1,k)-\log
F(G-y-z;k+1,k)\geq(\textstyle{\frac{k-2}{k-1}}-2{\varepsilon})(n+n-1)$
$\displaystyle\hskip 170.71652pt\forall\text{ distinct }y,z\in V(G).$

If $G\not\in\mathcal{J}_{2(k-1)}(n)$, then there is a graph $G^{\prime}$ of
order $n$ with $F(G^{\prime};k+1,k)>F(G;k+1,k)$.

Proof. As it is easy to show (or see [stability2, Lemma 1.8]), $(k+1,k)$ has
the extension property. Let $0<\delta^{\prime}\ll\delta$. Let
$n_{0},{\varepsilon}>0$ be the parameters returned by Theorem 2.12 applied
with parameter $\delta^{\prime}$. We may assume that
$0<1/n_{0}\ll{\varepsilon}\ll\delta^{\prime}$. Let $G$ be a graph on $n\geq
n_{0}$ vertices as in the lemma. Let $X_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,X_{t}$ be the partition of $V(G)$, where $|X_{1}|\geq\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\geq|X_{t}|$. By Theorem 2.12,
there is a set $\mathcal{P}$ of at least $(1-2^{-{\varepsilon}n})F(G;k+1,k)$
valid colourings of $G$ such that, for each $\chi\in\mathcal{P}$, the
following hold.

  * (i)

There is a coarsening $Z_{0},Z_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,Z_{k-1}$ of $X_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,X_{t}$ such that
$\sum_{i\in[k-1]}|\,|Z_{i}|-\frac{n}{k-1}\,|<\delta^{\prime}n$.

  * (ii)

Each of $Z_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,Z_{k-2}$ is
a part of $G$ and $Z_{k-1}$ contains at most two parts of $G$.

  * (iii)

For all $x\in V(G)$, there is $i(x)\in[k-1]$, so that we have $\chi(xy)=1$ for
all $y\in N_{G}(x)\cap Z_{i(x)}$, and for all $j\in[k-1]\setminus\\{i(x)\\}$,
it holds that

$|\chi^{-1}(c)[x,X]|=\textstyle{\frac{1}{2}}|X|\pm\delta^{\prime}|Z_{j}|\quad\text{for
all }c\in[2]\text{ and parts }X\subseteq Z_{j}.$ (54)

Moreover, for all $j\in[k-1]$ and distinct $y,z\in V(G)$ with $i(y)=i(z)\neq
j$, it holds that

$|N_{\chi^{-1}(c)}(y,X)\cap
N_{\chi^{-1}(c^{\prime})}(z,X)|=\textstyle{\frac{1}{4}}|X|\pm\delta^{\prime}|Z_{j}|\quad\text{for
all }c,c^{\prime}\in[2]\text{ and parts }X\subseteq Z_{j}.$ (55)

Also, if $x\in Z_{i}$ for $i\in[k-1]$ then $i(x)=i$.

Fix $\chi^{*}\in\mathcal{P}$ and choose $Z_{0},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,Z_{k-1},i:V(G)\mapsto[k-1]$ as above. (Recall
that these may be different for different colourings.) If there is a part in
$Z_{k-1}$ of size at most $\delta n$, move it into $Z_{0}$. Then (i) holds
with parameter $2\delta$, (iii) holds with parameter $\delta^{\prime}$, every
part in $Z_{k-1}$ has size at least $\delta n$, and all but one part in
$Z_{0}$ has size at most $\delta^{\prime}n$. Let $p^{*}$ be the number of
parts in $Z_{k-1}$ and $q^{*}$ the number of parts in $Z_{0}$ (which both
depend on $\chi^{*}$).

###### Claim 5.4.1

Suppose that $Z_{0}\neq\emptyset$. Then $Z_{k-1}$ contains exactly one part.
Moreover, if $x,x^{\prime}\in Z_{0}$ lie in different parts of $G$, then for
all $\chi\in\mathcal{P}$ we have $\chi(xx^{\prime})=2$ and $i(x)\neq
i(x^{\prime})$. In particular, $Z_{0}$ contains at most $k-1$ parts.

Proof of Claim. Let $\\{B_{p^{\prime}}:p^{\prime}\in[p^{*}]\\}$ be the part(s)
of $G$ contained in $Z_{k-1}$. Suppose first that $p^{*}=2$ and $q^{*}\geq 1$.
Let $x\in Z_{0}$ and $\chi\in\mathcal{P}$ be arbitrary. Then $\chi(xv)=1$ for
all $v\in Z_{i(x)}$, and for each $i\in[k-1]\setminus\\{i(x)\\}$, the vertex
and pair locally good conditions (54) and (55) hold. Without loss of
generality, assume $|B_{1}|\geq|B_{2}|$. Thus e.g. $|B_{1}|\geq n/(2k)$ and
$|B_{2}|\geq\delta n$. By (54) there is $y\in B_{2}$ such that $\chi(xy)=1$
(when $i(x)\neq k-1$, since if $i(x)=k-1$ this is obvious). Since $i(y)=k-1$
we also have $\chi(yz)=1$ for every $z\in B_{1}$. Let $J:=\chi^{-1}(1)$. For
$i\in[k-2]$, let $A_{i}:=N_{J}(x,Z_{i})\cap N_{J}(y,Z_{i})$ and let
$A_{k-1}:=N_{J}(x,B_{1})\cap N_{J}(y,B_{1})$. Then (55) implies that
$|A_{i}|\geq(\frac{1}{4}-\delta^{\prime})|Z_{i}|\geq|Z_{i}|/5\geq n/(5k)$ for
all $i\in[k-2]$. Also, by (54),
$|A_{k-1}|=|N_{J}(x,B_{1})|\geq(\frac{1}{2}-\delta^{\prime})|B_{1}|\geq|Z_{k-1}|/5\geq
n/(5k)$. Lemma 2.6 implies that $J[A_{i},A_{j}]$ is
$(\sqrt{\delta^{\prime}},\frac{1}{2})$-regular for all distinct $i,j\in[k-1]$.
By Lemma 2.4, $J$ contains a $K_{k-1}$ with one vertex in each of
$A_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,A_{k-1}$. Together
with $x,y$, this gives rise to a $1$-coloured copy of $K_{k+1}$ in $G$, a
contradiction. So if $p^{*}=2$, then $q^{*}=0$.

Suppose now that $p^{*}=1$ and let $x,x^{\prime}\in Z_{0}$ lie in different
parts of $G$. Similar arguments to those above show that $x,x^{\prime}$ form
the $2$-element set in a copy of the $k$-partite graph $K_{1,\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,1,2}$ in $\chi^{-1}(1)$.
Therefore (since the edge between them must have some colour)
$\chi(xx^{\prime})=2$, as required. Suppose now, for a contradiction, that
$i(x)=i(x^{\prime})$. Without loss of generality, suppose their common value
is $1$. Then $U_{i}:=N_{\chi^{-1}(2)}(x,Z_{i})\cap
N_{\chi^{-1}(2)}(x^{\prime},Z_{i})$ satisfies
$|U_{i}|=(\textstyle{\frac{1}{4}}\pm\sqrt{\delta^{\prime}})|Z_{i}|$ for all
$2\leq i\leq k-1$. By Proposition 2.7, $\chi^{-1}(2)[U_{i},U_{i^{\prime}}]$ is
$((\delta^{\prime})^{1/3},\frac{1}{2})$-regular for all distinct $2\leq
i,i^{\prime}\leq k-1$. By Lemma 2.4, there are $z_{i}\in U_{i}$ for $2\leq
i\leq k-1$ such that $x,x^{\prime},z_{2},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,z_{k-1}$ form a copy of $K_{k}$ in $\chi^{-1}(2)$, a
contradiction. Thus $i(x)\neq i(x^{\prime})$. This completes the proof of the
claim.

The total number of parts is $t=k-2+p^{*}+q^{*}$. Suppose that $t=k-1$. Then
$G$ is $K_{k}$-free. Thus every $2$-edge colouring is $(k,k+1)$-valid and so
$|\mathcal{P}|\leq 2^{t_{k-1}(n)}$ and hence
$F(G;\bm{k})\leq(1-2^{-{\varepsilon}n})^{-1}\cdot 2^{t_{k-1}(n)}$.

Suppose $t\geq k$ and every part of $G$ has size at least $\delta n$. Then
every $\chi\in\mathcal{P}$ has the same associated coarsening
$Z_{1}=X_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,Z_{k-2}=X_{k-2},Z_{k-1}=X_{k-1}\cup X_{k}$ in order to satisfy
$\sum_{i\in[k-1]}|\,|Z_{i}|-\frac{n}{k-1}\,|\leq\delta^{\prime}n$. The number
of perfect colourings is the same as if $X_{k-1},X_{k}$ were merged into a
single part since edges between these parts are coloured with $1$, so

$|\mathcal{P}|\leq 2^{t_{k-1}(n)},\quad\text{so again}\quad
F(G;\bm{k})\leq(1+o(1))\cdot 2^{t_{k-1}(n)}.$

We will see later, due to Proposition 5.3, that there is $G^{\prime}$ with
$|\mathcal{P}(G^{\prime})|\geq 1.9|\mathcal{P}(G)|$.

So from now on we will assume that $t\geq k$ and there are $q\geq 1$ parts of
size less than $\delta n$. Claim 5.4.1 implies that these parts lies in
$Z_{0}$ so $p^{*}=1$ and $q^{*}=q=t-(k-1)$. Thus we have $|X_{i}|<\delta n$
for all $i\geq k$, so also $|X_{1}|\geq\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt\geq|X_{k-1}|\geq\frac{n}{k-1}-(k-1)\delta n$. We will say
that $X_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,X_{k-1}$ are
the _large parts_ , of sizes $m_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,m_{k-1}$ respectively, and $L_{1},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,L_{q}$ are the _small parts_ , of sizes
$\ell_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,\ell_{q}$
respectively. Also, let $m:=m_{1}+\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt+m_{k-1}$ and $\ell:=\ell_{1}+\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt+\ell_{q}$, and $\bm{m}:=(m_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,m_{k-1})$ and
$\bm{\ell}:=(\ell_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,\ell_{q})$. For some colourings $\chi$, one of the $L_{i}$ may be a part
of $Z_{k-1}$, while in others all $L_{i}$ will be parts of $Z_{0}$. Suppose
there are $\chi$ and $i$ such that $Z_{k-1}=X_{k-1}\cup L_{i}$. Then Claim
5.4.1 implies that $q=0$, so then $t=k$. So for all $\chi$, either
$(Z_{k-1},Z_{0})=(X_{k-1}\cup L_{i},\emptyset)$, or
$(Z_{k-1},Z_{0})=(X_{k-1},L_{i})$. We may assume that we always have the
second partition, as the number of perfect colourings is a function of
$(Z_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,Z_{k-1},Z_{0})$
and there are more choices with the second. Thus we may assume that each
perfect colouring $\chi$ gives rise to the same partition $(Z_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,Z_{k-1},Z_{0})=(X_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,X_{k-1},L_{1}\cup\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\cup L_{q})$, where $q\leq k-1$.

Let $P_{q}(k-1)$ be the set of ordered partitions of $[k-1]$ into $q$ parts
(some of which may be empty) with the following property. Suppose that exactly
$a$ different values appear in $\bm{\ell}$, so $\ell_{1}=\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt=\ell_{i_{1}}>\ell_{i_{1}+1}=\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt=\ell_{i_{2}}>\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt>\ell_{i_{a-1}+1}=\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt=\ell_{q}$ for some $a\in[q]$. For each
unordered partition $\\{I_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,I_{q}\\}$, labelled so that $\min\\{I_{1}\\}<\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt<\min\\{I_{q}\\}$, and any permutation
$\sigma:[q]\to[q]$ that has $\sigma(i_{s-1}+1)<\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt<\sigma(i_{s})$ for all $1\leq s\leq a+1$
(where $i_{0}:=0$ and $i_{a+1}:=q$), we put $(I_{\sigma(1)},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,I_{\sigma(q)})$ into
$P_{q}(k-1)$. So if $\ell_{1}>\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt>\ell_{q}$, then $P_{q}(k-1)$ consists of all ordered partitions of
$[k-1]$ into $q$ parts, while if $\ell_{1}=\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt=\ell_{q}$, then for each unordered partition it contains
exactly one ordering.

Every colouring in $\mathcal{P}(G)$ is obtained as follows: First, colour
edges between pairs in $Z_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,Z_{k-1}$ arbitrarily and colour edges between the $L_{i}$ with colour
$2$. By Claim 5.4.1, $i(x)\neq i(x^{\prime})$ for $x,x^{\prime}$ in different
small parts, so choose $(I_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,I_{q})\in P_{q}(k-1)$ so that $i(x)\in I_{j}$ for all $x$ in $L_{j}$.
Now for each $j\in[q]$ and $x$ in $L_{j}$, colour all edges between $x$ and
$Z_{i(x)}$ with colour $1$ and all edges between $x$ and the remaining $Z_{i}$
arbitrarily. The number of choices in this colouring procedure is at most

$\displaystyle f(\bm{m};\bm{\ell}):=$
$\displaystyle\prod_{ij\in\binom{[k-1]}{2}}2^{m_{i}m_{j}}\cdot 2^{m\ell}\cdot
g(\bm{m};\bm{\ell}),\quad\text{where}\quad
g(\bm{m};\bm{\ell}):=\sum_{\begin{subarray}{c}(I_{1},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,I_{q})\\\ \in
P_{q}(k-1)\end{subarray}}\prod_{j\in[q]}\left(\sum_{i^{\prime}\in
I_{j}}2^{-m_{i^{\prime}}}\right)^{\ell_{j}}.$

We have $|\mathcal{P}(G)|\leq f(\bm{m};\bm{\ell})$ and would like an almost
matching lower bound. Every colouring from the procedure above is valid so we
need to check which colourings have been counted more than once. Suppose
$\chi$ is a perfect colouring arising from two different choices. Let
$(I_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,I_{q})$ and
$(I_{1}^{\prime},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,I_{q}^{\prime})$ be the respective choices of partitions, which are
necessarily different. So there are $i\in[q]$ and $s\in[k-1]\setminus I_{i}$
such that $s\in I_{i}^{\prime}\setminus I_{i}$. But then in $\chi$ every edge
between $L_{i}$ and $\bigcup_{i^{\prime}\in I_{i}\cup\\{s\\}}Z_{i^{\prime}}$
is coloured with colour $1$. In other words, the number of choices for colours
of edges between $L_{i}$ and $Z_{1}\cup\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt\cup Z_{k-1}$ has decreased by a multiplicative factor of
$2^{m_{s}\ell_{i}}$. The number of such colourings is therefore at most

$f(\bm{m};\bm{\ell})\cdot q\cdot(k-1)\cdot 2^{-m_{k-1}\ell_{q}}\leq
2^{-n/k}\cdot f(\bm{m};\bm{\ell}).$

Thus

$(1-2^{-n/k})f(\bm{m};\bm{\ell})\leq|\mathcal{P}(G)|\leq f(\bm{m};\bm{\ell}).$
(56)

Now we can state that we are done in the case $t=k-1$ and the case $t=k$ and
every part has size at least $\delta n$. Indeed, the previous inequality, the
fact that

$f(\bm{m};(\ell))=h(\bm{m};\ell)$

and Proposition 5.3 imply that

$F(n;k+1,k)\geq(2+o(1))\cdot 2^{t_{k-1}(n)}.$ (57)

Moreover, for $3\leq k\leq 10$, among graphs in $\mathcal{J}_{2(k-1)}(n)$, the
unique graph with the largest number of valid colourings is $J^{\ell(k,j)}(n)$
where $\ell(k,j)$ is in the table in Proposition 5.3(iii).

We return to the only remaining case when $t\geq k$ and there is at least one
part of size less than $\delta n$. Write $f(\bm{m};\ell)$ and $g(\bm{m};\ell)$
for $f(\bm{m};(\ell))$, $g(\bm{m};(\ell))$ respectively. In the next series of
claims we will compare $|\mathcal{P}(G)|=(1+o(1))f(\bm{m};\bm{\ell})$ with
$|\mathcal{P}(G^{\prime})|=(1+o(1))f(\bm{m}^{\prime};\bm{\ell}^{\prime})$
where $G^{\prime}$ is another complete partite graph with slightly different
part sizes $\bm{m}^{\prime},\bm{\ell}^{\prime}$, in order to gradually pin
down what $\bm{m}$ and $\bm{\ell}$ must be. The first of these claims states
that merging small parts does not decrease the number of perfect colourings.
(This is not yet sufficient for us to conclude that extremal graphs always
have a single small part, as for this the number of perfect colourings would
need to increase by factor $1+\Omega(1)$.)

###### Claim 5.4.2

If $q\geq 2$, then $g(\bm{m};\ell)\geq g(\bm{m};\ell_{1},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,\ell_{q})+2^{-m_{k-1}\ell}$, so
$f(\bm{m};\ell)\geq f(\bm{m};\ell_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,\ell_{q})$.

Proof of Claim. If we obtain $G^{\prime}$ from $G$ by merging $L_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,L_{q}$ to obtain a single part
$L$, then the number of perfect colourings increases. Indeed, let $x\in L_{1}$
and $y\in L_{2}$, say. In $G$, the number of valid choices of $(i(x),i(y))$ is
strictly less than the number in $G^{\prime}$, since $i(x)\neq i(y)$ in $G$,
while there is no such restriction in $G^{\prime}$. More precisely, the
$(I_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,I_{q})$ term in
$g$ corresponds to all the colourings that come from choosing $i(x)\in I_{i}$
for all $i\in[q]$ and $x\in L_{i}$. In $G^{\prime}$ we can choose $i(x)=k-1$
for all $x\in L$, giving the new term $2^{-m_{k-1}\ell}$.

In the next three claims, we assume that $G$ has one small part of size
$\ell$. Write $m_{1}\geq\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt\geq m_{k-1}$ for its other parts and let $a_{i}:=m_{i}-m_{k-1}$ for all
$i\in[k-1]$. By (56), as in the proof of Proposition 5.3, to compare the
number of perfect colourings of $G$ with another complete partite graph
$G^{\prime}$ with a single small part of size $\ell^{\prime}$ and large parts
of size $m_{1}^{\prime},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,m_{k-1}^{\prime}$, it suffices to compare their associated functions
$\tilde{h}(\bm{a};\ell),\tilde{h}(\bm{a}^{\prime},\ell^{\prime})$ defined in
(52), where $\bm{a}=(a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,a_{k-1})$, and $\bm{a}^{\prime}=(a_{1}^{\prime},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-1}^{\prime})$ is chosen so that
$\sum_{i}a_{i}+\ell=\sum_{i}a_{i}^{\prime}+\ell^{\prime}$. (Note that in
Proposition 5.3, we defined $b_{i}:=m_{i}-\lfloor\frac{n}{k-1}\rfloor$ whereas
here it is convenient to define $a_{i}=m_{i}-m_{k-1}$ so that $a_{1}\geq\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\geq a_{k-1}=0$.) The next claim
concludes the proof in the case when $\ell$ is large and not every
$a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-2}$ is
comparable with $\ell$.

###### Claim 5.4.3

Suppose $q=1$. If $a_{k-2}\leq(\ell-1)/2$ and $\ell\geq\min\\{13,2k-2\\}$ then
there exists an $n$-vertex graph $G^{\prime}$ with
$|\mathcal{P}(G^{\prime})|>1.01|\mathcal{P}(G)|$.

Proof of Claim. Remove $1$ from $\ell$ and add $1$ to $a_{k-2}$, letting
$\bm{a}^{(1)}:=(a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,a_{k-2}+1,a_{k-1})$. We let $G^{\prime}$ be the complete partite graph
with large parts of size $(m_{k-1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,m_{k-1})+\bm{a}^{(1)}$ and one small part of size $\ell-1$.
Then

$\displaystyle(1+o(1))\frac{|\mathcal{P}(G^{\prime})|}{|\mathcal{P}(G)|}=\frac{\tilde{h}(\bm{a}^{(1)};\ell-1)}{\tilde{h}(\bm{a};\ell)}=\frac{2^{\ell-
a_{k-2}-1}(2^{-a_{1}}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+\frac{1}{2}\cdot 2^{-a_{k-2}}+1)^{\ell-1}}{(2^{-a_{1}}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+2^{-a_{k-2}}+1)^{\ell}}.$ (58)

Now, for $y>0$ and $0<x\leq 1$, let

$f(x,y):=\frac{(y+\frac{x}{2}+1)^{\ell-1}}{(y+x+1)^{\ell}},\quad\text{then}\quad\frac{\partial
f}{\partial
x}=-\frac{2(y+\frac{x}{2}+1)^{\ell}((\ell+1)(y+1)+x)}{(y+x+1)^{\ell+1}(2(y+1)+x)^{2}},$

so $f$ is decreasing in $x$ and hence $f(x,y)\geq
f(1,y)=(y+\frac{3}{2})^{\ell-1}/(y+2)^{\ell}$. Also

$\frac{\partial f(1,y)}{\partial
y}=-\frac{(y-\frac{\ell}{2}+2)(y+\frac{3}{2})^{\ell-2}}{(y+2)^{\ell+1}}$

so $f(1,y)$ is increasing from $y=0$ to $y=\frac{\ell}{2}-2\geq k-3$. Thus for
$0\leq y\leq k-3$ we have $f(1,y)\geq
f(1,0)=(\frac{3}{2})^{\ell-1}/2^{\ell}=\frac{1}{2}\left(\frac{3}{4}\right)^{\ell-1}$.
Since $2^{-a_{1}}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-a_{k-3}}\leq k-3$, and $\ell\geq 13$, we see that (58) is at least

$2^{\ell-
a_{k-2}-1}\cdot\left(\frac{3}{4}\right)^{\ell-1}\cdot\frac{1}{2}\geq\frac{1}{2}\left(\frac{\sqrt{2}\cdot
3}{4}\right)^{\ell-1}>1.013,$

completing the proof of the claim.

###### Claim 5.4.4

Suppose $q=1$. If $a_{k-2}\geq\ell/2$ and $\ell\geq\max\\{14,2k-2\\}$ then
there exists an $n$-vertex graph $G^{\prime}$ with
$|\mathcal{P}(G^{\prime})|>1.05|\mathcal{P}(G)|$.

Proof of Claim. Let $A:=\\{a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,a_{k-2},\ell\\}$ and $b:=\sum_{u\in A}u$. Then, recalling $a_{k-1}=0$,

$\displaystyle\tilde{h}(\bm{a};\ell)\stackrel{{\scriptstyle(\ref{tildeh})}}{{=}}\prod_{uu^{\prime}\in\binom{A}{2}}2^{uu^{\prime}}(2^{-a_{1}}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+2^{-a_{k-2}}+1)^{\ell}\leq
2^{t_{k-1}(b)}(2^{-a_{1}}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-a_{k-2}}+1)^{\ell}.$

Note that

$t_{k-1}(n)=t_{k-1}((k-1)m_{k-1}+b)=\binom{k-1}{2}m_{k-1}^{2}+(k-2)m_{k-1}b+t_{k-1}(b).$

Thus $(1+o(1))|\mathcal{P}(G)|=h(\bm{m};\ell)\leq
2^{t_{k-1}(n)}\cdot(2^{-a_{1}}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-a_{k-2}}+1)^{\ell}$. But

$(2^{-a_{1}}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-a_{k-2}}+1)^{\ell}\leq((k-2)2^{-a_{k-2}}+1)^{\ell}\leq\left(\left(\frac{\ell}{2}-1\right)\cdot
2^{-\ell/2}+1\right)^{\ell}.$

This is less than $1.9$ for $\ell\geq 14$. Equation (57) implies the existence
of $G^{\prime}$ with $|\mathcal{P}(G^{\prime})|=(2+o(1))\cdot 2^{t_{k-1}(n)}$,
and further $2/1.9>1.052$.

The next claim implies that $a_{1}$ and hence all of $a_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-1}$ cannot be much bigger
than $\ell$.

###### Claim 5.4.5

Suppose $q=1$. If $a_{1}\geq\ell+2$, then there is an $n$-vertex graph
$G^{\prime}$ with $|\mathcal{P}(G^{\prime})|>1.9|\mathcal{P}(G)|$.

Proof of Claim. Suppose that $a_{1}\geq\ell+2$. Let
$\bm{a}^{(2)}:=(a_{1}-1,a_{2},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,a_{k-2},a_{k-1}+1)$. Then

$\frac{\tilde{h}(\bm{a}^{(2)};\ell)}{\tilde{h}(\bm{a};\ell)}=2^{a_{1}-1}\left(\frac{2\cdot
2^{-a_{1}}+2^{-a_{2}}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-a_{k-2}}+\frac{1}{2}\cdot 2^{-a_{k-1}}}{2^{-a_{1}}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+2^{-a_{k-1}}}\right)^{\ell}\geq
2^{a_{1}-1-\ell}\geq 2,$

since we can lower bound the numerator by
$\frac{1}{2}\sum_{i\in[k-1]}2^{-a_{i}}$.

###### Claim 5.4.6

There is a positive function $p$ of $k$ such that the following holds. If
$a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,a_{k-1},\ell=O_{k}(1)$ and $q\geq 2$, then the graph $G^{\prime}$
obtained by merging $L_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,L_{q}$ has $|\mathcal{P}(G^{\prime})|>(1+p(k))|\mathcal{P}(G)|$.

Proof of Claim. It suffices to show that there is $a=a(k)$ such that
$f(\bm{m};\ell)\geq(1+a)f(\bm{m};\ell_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,\ell_{q})$. We have
$g(\bm{m};\bm{\ell})=2^{-m_{k-1}\ell}g(\bm{a};\bm{\ell})$, where
$\bm{a}=(a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-1})$
satisfies $a_{i}=m_{i}-m_{k-1}$, so $0\leq a_{i}=O_{k}(1)$ for all $i$. Since
also $\ell=O_{k}(1)$, we have $g(\bm{a};\bm{\ell})=p_{0}(k)$ for some positive
function $p_{0}$ of $k$. We have $g(\bm{a};\ell)\geq g(\bm{a};\bm{\ell})+1$ by
Claim 5.4.2, so

$\frac{f(\bm{m};\ell)}{f(\bm{m};\ell_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,\ell_{q})}=\frac{g(\bm{m};\ell)}{g(\bm{m};\ell_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,\ell_{q})}\geq\frac{p_{0}(k)+1}{p_{0}(k)},$

as required.

###### Claim 5.4.7

If $q=1$ and $\ell=1$ and $k\geq 4$, then the graph $G^{\prime}$ obtained by
moving one vertex from $Z_{1}$ to $L=L_{1}$ has
$|\mathcal{P}(G^{\prime})|>1.9|\mathcal{P}(G)|$.

Proof of Claim. Let $\bm{a}^{(3)}:=(a_{1}-1,a_{2},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-1})$. Then

$\displaystyle\frac{\tilde{h}(\bm{a}^{(3)};2)}{\tilde{h}(\bm{a};1)}$
$\displaystyle\geq\frac{2^{a_{1}-2}\left(2\cdot 2^{-a_{1}}+2^{-a_{2}}+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{-a_{k-1}}\right)^{2}}{2^{-a_{1}}+2^{-a_{2}}+\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt+2^{-a_{k-1}}}\geq
2^{-1}+2^{a_{1}-a_{1}-2}+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+2^{a_{1}-a_{k-1}-2}$
$\displaystyle\geq\frac{1}{2}+\frac{k-1}{4}\geq\frac{5}{4},$

where the second inequality follows by expanding
$(2^{-a_{1}}+\sum_{i\in[k-1]}2^{-a_{i}})^{2}$.

To complete the proof of Lemma 5.4, assume that
$G\notin\mathcal{J}_{2(k-1)}(n)$. We will find an $n$-vertex graph
$G^{\prime}$ with $F(G^{\prime};k+1,k)>F(G;k+1,k)$. Let $m_{1},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,m_{k-1}$ be the large parts and
$\ell_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,\ell_{q}$ be the
small parts of $G$. Let $a_{i}:=m_{i}-m_{k-1}$ for all $i\in[k-1]$. Obtain
$G_{0}$ by merging $L_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,L_{q}$ and let $\ell:=\ell_{1}+\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt+\ell_{q}$.

By Claim 5.4.2, we have that
$|\mathcal{P}(G_{0})|\geq(1+o(1))|\mathcal{P}(G)|$. Suppose
$\ell\geq\max\\{14,2k-2\\}$. Then Claims 5.4.3 and 5.4.4 imply that there is
an $n$-vertex graph $G^{\prime}$ such that
$|\mathcal{P}(G)|<(1+o(1))|\mathcal{P}(G_{0})|<(1+o(1))\frac{1}{1.01}\cdot|\mathcal{P}(G^{\prime})|$,
as required. Thus we may suppose instead that $\ell<\max\\{14,2k-2\\}$.

Suppose further that $a_{1}\geq\ell+2$. Then Claim 5.4.5 implies that there is
an $n$-vertex graph $G^{\prime}$ such that
$|\mathcal{P}(G)|<(1+o(1))|\mathcal{P}(G_{0})|<\frac{1}{1.8}\cdot|\mathcal{P}(G^{\prime})|$.
So we may suppose that $\max\\{14,2k-2\\}\geq\ell+1\geq a_{1}\geq\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt\geq a_{k-2}\geq a_{k-1}=0$.

Suppose $q\geq 2$. Then Claim 5.4.6 implies that
$|\mathcal{P}(G_{0})|>(1+p(k))|\mathcal{P}(G)|$ for some positive function
$p$. So we may suppose that $q=1$. Suppose now $\ell=1$. Claim 5.4.7 furnishes
us with the required $G^{\prime}$ when $k\geq 4$.

If $k\geq 8$, then we have that $14\leq 2k-2$ and of course $k\geq 4$, so in
fact $q=1$, $\ell\geq 2$ and $2k-2\geq\ell,a_{1},\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-1}$, which is a contradiction since
$G\notin\mathcal{J}_{2(k-1)}(n)$. Thus we have $k\leq 7$ and
$14\geq\ell,a_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,a_{k-1}$. Here one can use the same program as in the proof of
Proposition 5.3(iii) with tweaked parameters to obtain that in every case
there is $G^{\prime}$ with large part differences $a_{1}^{\prime},\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt,a_{k-1}^{\prime}$ such that
$a_{1}^{\prime}\leq 1$ and $\ell^{\prime}$ is as in the table there, such that
$\tilde{h}(\bm{a}^{\prime};\ell^{\prime})>\tilde{h}(\bm{a};\ell)+\Omega(1)$,
since $G\neq G^{\prime}$.

We derive Theorem 5.2 from Lemma 5.4 using the same approach as [PY].

Proof of Theorem 5.2. We want to show that

$|\mathcal{P}(J)|=O_{k}(1)\cdot 2^{t_{k-1}(n)}\quad\text{for all
}J\in\mathcal{J}_{2(k-1)}(n),$ (59)

which implies the same equality holds for $F(J;k+1,k)$ by the arguments in the
proof of Lemma 5.4. For this, start with $T_{k-1}(n)$ with vertex partition
$Y_{1},\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt,Y_{k-1},Y_{k}=\emptyset$. Consider moves where each time we move one
vertex between parts. One can obtain $J$ in $O(k^{2})$ moves, between large
parts, or from a large part to the small part $Y_{k}$. Each move changes $F$
by a multiplicative factor of $O_{k}(1)$ (we already did the calculations in
Claims 5.4.5 and 5.4.7). This proves (59).

Apply Lemma 5.4 to obtain ${\varepsilon},n_{0}$. We may assume that
$1/n_{0}\ll{\varepsilon}\ll 1$. Let $N:=n_{0}^{2}$. Let $G$ be a
$(k+1,k)$-extremal graph on $n\geq N$ vertices. Suppose, for a contradiction,
that $G\not\in\mathcal{J}_{2(k-1)}(n)$. Let $G_{n}:=G$. If $G_{n}$ is not a
complete multipartite graph, apply Lemma 2.14 to obtain a graph $H_{n}$ on $n$
vertices which is $(k+1,k)$-extremal and complete multipartite, with a part of
size $1$ and let $G_{n}:=H_{n}$. Observe that in both cases
$G_{n}\not\in\mathcal{J}_{2(k-1)}(n)$. We iteratively apply the following
procedure. Let $G_{m}$ be the current graph on $m\geq n_{0}+2$ vertices with
$\log
F(G_{m};k+1,k)\geq\left(\frac{k-2}{k-1}-{\varepsilon}\right)\binom{m}{2}$,
apply Lemma 5.4. If (53) fails for some $x\in V(G_{m})$, we let
$G_{m-1}:=G_{m}-x$, decrease $m$ by $1$, and repeat. Similarly, if (53) fails
for some pair $y,z\in V(G_{m})$, we let $G_{m-2}:=G_{m}-y-z$, decrease $m$ by
$2$, and repeat. Note that

$\log F(G_{m-1};k+1,k)\geq\log
F(G_{m};k+1,k)-\left(\frac{k-2}{k-1}-2{\varepsilon}\right)m\geq\left(\frac{k-2}{k-1}-2{\varepsilon}\right)\left(\binom{m}{2}-m\right).$

If (53) holds for all $x\in V(G)$ and pairs $y,z\in V(G)$, but
$G_{m}\not\in\mathcal{J}_{2(k-1)}(m)$, then we replace $G_{m}$ by the graph
$G^{\prime}$ returned by Lemma 5.4 and repeat the step (without decreasing
$m$). Recall that $G^{\prime}$ has strictly more valid colourings than
$G_{m}$. Note that for every $m$ for which $G_{m}$ is defined we have

$\log F(G_{m};k+1,k)\geq\log
F(G;k+1,k)-\left(\frac{k-2}{k-1}-2{\varepsilon}\right)\left(n+(n-1)+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+(m+1)\right).$

It follows that we never reach $m\leq n_{0}$ for otherwise, when this happens
for the first time, we get that

$\displaystyle\log F(G_{m};k+1,k)$
$\displaystyle\geq\left(\frac{k-2}{k-1}-{\varepsilon}\right)\binom{n}{2}-\left(\frac{k-2}{k-1}-2{\varepsilon}\right)\left(\binom{n+1}{2}-\binom{m+1}{2}\right)$
$\displaystyle\geq{\varepsilon}\binom{n}{2}+\left(\frac{k-2}{k-1}-2{\varepsilon}\right)\binom{m}{2}>\binom{m}{2},$

i.e. $F(m;k+1,k)>2^{\binom{m}{2}}$, a contradiction. Thus we stop for some
$m\geq n_{0}+2$, with $G_{m}\in\mathcal{J}_{2(k-1)}(m)$. We cannot have $m=n$
for otherwise any $J_{n}\in\mathcal{J}_{2(k-1)}(n)$ has more colourings than
$G$ by Lemma 5.4. Almost every colouring of
$G_{m}:=J_{m}\in\mathcal{J}_{2(k-1)}(m)$ is perfect. Thus

$\displaystyle 1+\log|\mathcal{P}(J_{m})|$ $\displaystyle>\log F(J_{m};k+1,k)$
$\displaystyle\geq\log
F(G;k+1,k)-\left(\frac{k-2}{k-1}-2{\varepsilon}\right)\left(n+(n-1)+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt+(m+1)\right).$

Since $t_{k-1}(\ell)-t_{k-1}(\ell-1)=\lfloor\frac{k-2}{k-1}\ell\rfloor$, (59)
implies that there is some constant $C_{k}>0$ such that
$|\mathcal{P}(J_{\ell})|\geq C_{k}\cdot
2^{\frac{k-2}{k-1}\ell-1}|\mathcal{P}(J_{\ell-1})|$ for all $\ell\geq n_{0}$
and all $J_{\ell}\in\mathcal{J}_{2(k-1)}(\ell)$,
$J_{\ell-1}\in\mathcal{J}_{2(k-1)}(\ell-1)$. Thus

$\log F(G;k+1,k)\geq\log|\mathcal{P}(J_{n})|\geq\frac{k-2}{k-1}\left(n+\hskip
0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+(m+1)\right)+(C_{k}-1)(n-m)+\log|\mathcal{P}(J_{m})|.$

Together with the previous displayed equation, this is a contradiction to
$m\geq 1$. Thus $G\in\mathcal{J}_{2(k-1)}(n)$.

##  6 Concluding remarks

###  6.1 The uniform problem

Consider $\bm{k}=(k;s)$. In this paper we obtained an exact result for $(3;7)$
and a new proof for $(3;6)$. For general $(k;s)$, it seems reasonable to
expect every $(r,\phi,\bm{\alpha})$ to be such that $(k-1)|r$, $\bm{\alpha}$
is uniform and every $\phi^{-1}(c)\cong T_{k-1}(r)$. If this were so, then for
distinct $c,c^{\prime}\in[s]$, $\phi^{-1}(c)\cup\phi^{-1}(c^{\prime})$ would
have at most $(k-1)^{2}$ parts. This would give rise to a constraint in
Problem $L$ which is the analogue of (46), namely

$(s-1+s-2)d_{2}+(s-1+s-2+s-3)d_{3}+\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt+(s-1+s-2+\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip
1.5pt+s-s)d_{s}\leq\binom{s}{2}\frac{(k-1)^{2}-1}{(k-1)^{2}}.$

Perhaps this constraint is always valid. As in the case $(3;s)$, it alone does
not seem enough to give a realisable solution for $s\geq 8$, but for $(5;4)$
and $(5;5)$ it does give rise to a realisable solution, with
$\bm{d}=(0,\frac{3}{4},\frac{3}{16})$ and $(0,0,\frac{15}{16},0)$
respectively. The corresponding solution to Problem $Q^{*}$ has $r=16$, and
colourings come from $\mathbb{F}^{2}_{4}$. Thus we make the following
conjecture.

###### Conjecture 6.1

There exists $n_{0}>0$ such that for all $n\geq n_{0}$, $T_{16}(n)$ is the
unique $(5;4)$-extremal graph, and the unique $(5;5)$-extremal graph.

Its proof would probably follow from the following analogue of Lemma 3.3, for
$b$ not too small.

###### Problem 6.2

Find $b>0$ as large as possible such that the following holds for all
sufficiently large $n$. Let $R,B$ be two $K_{5}$-free graphs on the same
vertex set of size $n$ with $|R|+|B|\geq(\frac{3}{2}-b)n^{2}/2$. Then $|R\cup
B|\leq\frac{15}{16}n^{2}/2+o(n^{2})$.

Suppose $R,B$ are $K_{k}$-free graphs on the same vertex set of size $n$, with
$|R|,|B|\geq(\frac{k-2}{k-1}-d)n^{2}/2$ and $|R\cup
B|=(\frac{(k-1)^{2}-1}{(k-1)^{2}}+d^{\prime})n^{2}/2$. The strong stability
theorem of Füredi [furedi] implies that at most $dn^{2}/2$ edges need to be
removed from each of $R,B$ to make them $(k-1)$-partite. Thus removing at most
$dn^{2}$ edges from $R\cup B$ yields a $(k-1)^{2}$-partite graph, so
$d^{\prime}\leq 2d$. We need $d=\Omega(1)$ and $d^{\prime}=o(1)$, for example
we proved $(d,d^{\prime})=(\frac{1}{40},o(1))$ in Lemma 3.3.

To prove Lemma 3.3, of which Problem 6.2 is an analogue, we used the fact that
$R(3,3)-(3-1)^{2}=1$, whereas $R(4,4)-(4-1)^{2}=9$ and $27\leq
R(5,5)-(5-1)^{2}\leq 32$. Thus there could be many clique sizes larger than
$(k-1)^{2}$ present in $R\cup B$, and moreover they could have many different
red/blue colourings. Therefore the proof method of Lemma 3.3 seems unlikely to
generalise.

###  6.2 The two colour problem

Solving the two colour problem completely seems difficult. Recall that
$\bm{k}=(k,\ell)$ has the weak extension property but not the strong extension
property, so our stability theorem Theorem 1.4 applies – which shows there is
a large family of almost extremal graphs – but our exact theorem Theorem 1.6
does not. The method we used to prove Theorem 1.13 about $\bm{k}=(k+1,k)$
could be used to prove further two colour results, but the number of possible
coloured graph structures one needs to consider in an analogue of Lemma 5.4
increases with $k-\ell$.

It seems plausible that the $(5,3)$-extremal graph may be $T_{4}(n)$, with
$F(n;(5,3))=(3+o(1))\cdot 2^{t_{2}(n)}$, where almost all valid colourings
come from taking one of the $\binom{4}{2}/2$ part-respecting bipartitions and
allowing every cross-edge to be either colour, while edges within one part are
given colour $1$. Perhaps for $\bm{k}=(\ell(k-1)+1,k)$, the $\bm{k}$-extremal
graph is $T_{\ell(k-1)}(n)$, with
$F(n;\bm{k})=(\frac{1}{(k-1)!}\binom{\ell(k-1)}{\ell,\hskip 0.9pt.\hskip
0.3pt.\hskip 0.3pt.\hskip 1.5pt,\ell}+o(1))\cdot 2^{t_{\ell(k-1)}(n)}$, and
for $\bm{k}=(\ell(k-1)+j,k)$ for $j=2,\hskip 0.9pt.\hskip 0.3pt.\hskip
0.3pt.\hskip 1.5pt,k-1$, extremal graphs contain at least one small part.

## References

Oleg Pikhurko |  | Katherine Staden
---|---|---

Mathematics Institute and DIMAP |  | Mathematical Institute

University of Warwick |  | University of Oxford

Coventry |  | Oxford

CV4 2AL |  | OX2 6GG

UK |  | UK

|  |

E-mail addresses<EMAIL_ADDRESS><EMAIL_ADDRESS>