2 Preliminaries

2.1 Elementary combinatorics

Lemma 2 Multinomial coefficient bound

Lemma A.1

For each \(k,t,r \in \mathbb {N}\) with \(3 \le t \le k\), we have

\begin{equation*} \binom {rk-t}{k,\dots ,k,k-t} \le e^{-(r-1)t^2/3rk} r^{rk-t}. \end{equation*}

Proof ▶

To prove this, observe that

\begin{equation*} \binom {rk-t}{k,\dots ,k,k-t} \binom {rk}{k,\dots ,k}^{-1} = \, \prod _{i = 0}^{t - 1} \frac{k - i}{rk - i} = r^{-t} \, \prod _{i = 0}^{t-1} \bigg( 1 - \frac{(r-1)i}{rk - i} \bigg) \le r^{-t} \cdot e^{-(r-1)t^2/3rk}. \end{equation*}

Since \(\binom {rk}{k,\dots ,k} \le r^{rk}\), the claimed bound follows.

2.2 Graphs and colourings

Definition 3 Complete graph

Definition 4 Edge colouring

✓

An edge colouring of a graph \(G\) with colours \(C\) is a map from the edge set \(E(G)\) to \(C\).

Definition 5 Colour neighbourhood

✓

Given an edge colouring, we write \(N_i(u)\) to denote the neighbourhood of vertex \(u\) in colour \(i\).

Definition 6 Function \(p_i(X,Y)\)

Let \(r, n\in \mathbb {N}\). Given sets \(X,Y \subset V(K_n)\) and a colour \(i \in [r]\), define

\begin{equation*} p_i(X,Y) = \min \bigg\{ \frac{|N_i(x) \cap Y|}{|Y|} : x \in X \bigg\} , \end{equation*}

Definition 7 Monochromatic cliques

Definition 8 Multicolor Ramsey numbers

Definition 9 Off-diagonal Ramsey numbers

Definition 10 Books

2.3 Trigonometry

Definition 11 cosh√x function

✓

Define \(\cosh \sqrt{x}\) via its Taylor expansion

\begin{equation*} \cosh \sqrt{x} = \sum _{n = 0}^\infty \frac{x^n}{(2n)!}. \end{equation*}

Lemma 12 Bounds on \(\cosh \sqrt{x}\) for positive arguments

\(x \le 2 + \cosh \sqrt{x} \le 3 e^{\sqrt{x}}\) for every \(x {\gt} 0\).

Proof ▶

For the lower-bound, using the fact that \(x{\gt}0\) and all coefficients of \(\cosh \sqrt{x}\) are positive,

\begin{equation*} 2+\cosh \sqrt{x} - x \ge 2 - \frac{x}{2} + \frac{x^2}{24} = \frac{1}{2}+\frac{1}{24}(x-6)^2 \ge 0. \end{equation*}

For the upper bound, we observe that because by comparing coefficients,

\begin{equation*} e^{\sqrt{x}} = \sum 3\frac{x^{n/2}}{n!} \ge \cosh \sqrt{x} \end{equation*}

Finally, \(2e^{\sqrt{x}}\ge 2\) when \(x{\gt}0\).

Lemma 13 Bounds on \(\cosh \sqrt{x}\) for negative arguments

\(-1 \le \cosh \sqrt{x} \le 1\) for every \(x {\lt} 0\).

Proof ▶

From the Taylor expansion, we get \(\cosh \sqrt{x} = \cos \sqrt{-x}\).

Lemma 14 Lower bound for cosh√x

For all \(x \in \mathbb {R}\), it is \(1 \le 2 + \cosh \sqrt{x}\).

Proof ▶

When \(x\) is negative, we use \(\cosh \sqrt{x} = \cos \sqrt{-x}\ge -1\). When \(x\) is positive this is implied by the fact that all coefficients in the power series of \(\cosh \sqrt{x}\) are positive.

Definition 15

✓

Let \(r \in \mathbb {N}\).

\begin{equation} \label{eq:f} f(x_1,\dots ,x_r) = \sum _{j = 1}^r x_j \prod _{i \ne j} \big( 2 + \cosh \sqrt{x_i} \big). \end{equation}

Lemma 16

All of the coefficients of the Taylor expansion of \(f\) are non-negative.

Proof ▶

By definition \(2+\cosh \sqrt{x}\) has positive coefficients. It suffices to observe that the product and sum of two Taylor series with only positive coefficients has again positive coefficients. Since \(f\) is such a combination of sums and products of Taylor series with only positive coefficients, we get the claim.

2.4 Integration theory

Lemma 17 Fubini for finite measures

Lemma 18 Exponential estimates

Lemma 19 Integration by parts for special functions

Lemma 20 Substitution formulas