2 Preliminaries

2.1 Graphs and colourings

Definition 2

✓

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

Definition 3

✓

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

Definition 4

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

\[ p_i(X,Y) = \min \bigg\{ \frac{|N_i(x) \cap Y|}{|Y|} : x \in X \bigg\} , \]

2.2 Multinomial coefficients

Lemma 5 Lemma A.1 in Balister et al.

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

\[ \binom {rk-t}{k,\dots ,k,k-t} \le e^{-(r-1)t^2/3rk} r^{rk-t}. \]

Proof ▶

To prove this, observe that

\[ \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}. \]

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

2.3 Trigonometry

Definition 6

✓

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

\[ \cosh \sqrt{x} = \sum _{n = 0}^\infty \frac{x^n}{(2n)!}. \]

Lemma 7

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.

Lemma 8

\(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 9

\(-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}\).

Definition 10

✓

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 11

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.