1 Distinguishing colour pallets by colour-blind
Consider a simple graph \(G=(V,E)\) and an edge colouring \(c:E\rightarrow \{1,2,\ldots ,k\}\), not necessarily proper. Such colouring is called neighbour distinguishing (or vertex colouring, see e.g., Addario-Berry et al. 2005) if for every edge \(uv\in E\), the multiset of colours incident with \(u\) is distinct from the multiset of colours incident with \(v\). In other words, if for every vertex \(v\) we set \(\overline{c}(v)=(a_1,\ldots ,a_k)\), where \( a_i =|\{w:wv\in E, c (wv)=i\}|\) for \(i=1,\ldots ,k\), then the colouring \(c\) is neighbour distinguishing if \(\overline{c}(u)\ne \overline{c}(v)\) for each edge \(uv\) of \(G\). Clearly, one can find such colouring if a graph contains no isolated edges, e.g., by painting each edge differently. Karoński et al. (2004) first proved that in fact a finite number of 183 colours are always sufficient, or even 30 if the minimum degree \(\delta \) of \(G\) is at least \(10^{99}\). This was then greatly improved by Addario-Berry et al. (2005), who showed that four colours are sufficient, and these can be decreased to three if \(\delta \ge 1,000\).
Suppose now that such coloured graph is examined by a colour-blind person, i.e., somebody who cannot name colours but distinguishes one from another. Can such individual ‘distinguish neighbours’ then? The answer is affirmative in many cases. It is due to the fact that given a set of coloured edges, they are able to divide it into monochromatic subsets and count their cardinalities. Given any sequence \(\overline{c}(v)=(a_1,\ldots ,a_k)\), let us re-order it non-decreasingly. The obtained sequence \(c^*(v)=(d_1,\ldots ,d_k)\) we shall call a pallet of \(v\). Note that there is a bijection between the set of all possible pallets one may obtain for a vertex \(v\) of degree \(d\) and the set of all \(k\)-partitions of the integer \(d\), i.e., the set \(P(d,k)=\{(d_1,d_2,\ldots ,d_k)\in \mathbb N ^k:d_1+\cdots +d_k=d\;\mathrm{and}\; 0\le d_i\le d_{i+1}\; \mathrm{for}\;i =1,\ldots , k-1 \}\). We say that a colour-blind person can distinguish neighbours in our colouring \(c:E\rightarrow \{1,\ldots ,k\}\) if \(c^*(u)\ne c^*(v)\) for every edge \(uv\in E\). The smallest integer \(k\) for which such colouring exists is called the colour-blind index of \(G\), and is denoted by \(\mathrm{dal}(G)\). This notion refers to the English chemist John Dalton, who in \(1798\) wrote the first paper on colour-blindness. In fact, because of Dalton’s work, the condition is often called daltonism.
Anzeige
It has to be noted that this parameter is undefined for some classes of graphs, in particular we must exclude graphs with isolated edges. However, thus far all known graphs with undefined colour-blind index have minimum degree at most three, see Kalinowski et al. for details. It has been proved there that given a fixed \(R> 1\), there always exists \(\delta _R\) such that \(\mathrm{dal}(G)\le 6\) for every graph with maximum degree \(\Delta \le R\delta \), provided that \(\delta \ge \delta _R\). Unfortunately \(\delta _R\) tends to infinity along with \(R\). It is thus not even known whether graphs with \(\delta \ge \delta _0\) have well defined colour-blind index for any constant \(\delta _0\), though Kalinowski et al. conjecture that it is so (maybe even with \(\delta _0=4\)). Situation with this mysterious parameter changes if we restrict ourselves to regular graphs exclusively. Using a Lovász Local Lemma, Kalinowski et al. proved that \(\mathrm{dal}(G)\le 6\) for every \(d\)-regular graph \(G\) if its degree is greater than a huge constant, namely, if \(d\ge 2\times 10^7\). An application of the probabilistic method in this context meets unusual obstacles. Unlike in many other similar problems, increasing the number of colours, ‘helps’ only until a certain point. Then the probability of a ‘bad event’ that vertices are indistinguishable for a colour-blind person (e.g., when the edge colouring is proper) grows. In this paper we optimize this probabilistic approach in order to significantly reduce the threshold for \(d\) at the cost of a few more colours. We shall thus prove the following theorem.
Theorem 1
For every \(d\)-regular graph \(G\) of degree \(d\ge 960\),
$$\begin{aligned} \mathrm{dal}(G)\le 15. \end{aligned}$$
The proof is based on the following variation of the Lovász Local Lemma, due to Erdős and Spencer (1991), sometimes referred to as the ‘Lopsided’ Local Lemma. We recall its symmetric versions from Alon and Spencer (2000) (see Corollary 5.1.2 and the comments below).
Theorem 2
(Lopsided Symmetric Local Lemma) Let \(\mathcal A \) be a family of (typically bad) events in any probability space and let \(D=(\mathcal A ,\mathcal E )\) be a directed graph with maximum out-degree \(\Delta ^+\). Suppose that for each \(A\in \mathcal A \) and every \(\mathcal C \subset \mathcal A \backslash N^+(A)\),whereThen \(\mathbf{Pr }(\bigcap _{A\in \mathcal A }\overline{A})>0\).
$$\begin{aligned} \mathbf{Pr }(A|\bigcap _{C\in \mathcal C }\overline{C}) \le p, \end{aligned}$$
(1)
$$\begin{aligned} ep(\Delta ^++1)\le 1. \end{aligned}$$
(2)
Anzeige
2 Proof of Theorem 1
2.1 Random process and dependency digraph
Suppose we are given a \(d\)-regular graph \(G=(V,E)\) with \(d\ge 960\). For each edge \(e\,{\in }\, E\) we independently and randomly choose a colour from the available set \(\{1,2,\ldots ,15\}\), each with equal probability, and denote it by \(c(e)\). In other words, the edges of \(G\) are associated with a set of independent random variables \((X_e)_{e\in E}\), each taking one of the values \(1,2,\ldots ,15\) with probability \(1/15\). Outcomes for these determine an edge colouring of \(G\), each occurring with probability \(1/15^{|E|}\) within the associated product probability space. By a bad event
\(A_{e}\) in our random process of generating \(c\) we shall mean obtaining \(c^*(u)= c^*(v)\) for some edge \(e=uv\in E\). If no bad event occurs, the corresponding colouring shall meet our requirements. We thus need to show that the probability of the event \(\bigcap _{e\in E}\overline{A_e}\) is positive in our probability space.
We define a digraph \(D=(\mathcal A ,\mathcal E )\), so called dependency digraph, in the following manner. Let \(\mathcal A =\{A_{e}: e\in E\}\). Now for every edge \(e=uv\) (i.e. \(e=\{u,v\}\)) of \(G\), we arbitrarily choose one of its end vertices, say \(v\). Equivalently, we choose an orientation \(\overrightarrow{e}=(u,v)\) of every edge \(e\in E\), and the obtained orientation of \(G\) we denote by \(\overrightarrow{G}=(V,\overrightarrow{E})\). Then for every edge \(e\in E\) with orientation \(\overrightarrow{e}=(u,v)\), we draw an arc between \(A_e\) and every event \(A_{e^{\prime }}\) such that \(e^{\prime }\) is at distance at most \(2\) from \(v\) in a graph \(G-e\) (where an edge incident with a vertex is at distance \(1\) from it), i.e., \(e^{\prime }\) is incident with some neighbour of \(v\) different from \(u\). The set of all such arcs we denote by \(\mathcal E \). Note that thenwhere \(\Delta ^+\) is the maximum out-degree of \(D\).
$$\begin{aligned} \Delta ^+\le (d-1)d\le d^2-1, \end{aligned}$$
(3)
2.2 Conditional probability of a bad event
Consider any event \(A_e\) with \(\overrightarrow{e}=(u,v)\) and some family of events \(\mathcal C \subset \mathcal A \backslash (N^+(A_{e})\cup \{A_{e}\})\), where \(N^+(A_{e})\) is the set of out-neighbours of \(A_e\) in \(D\). We assumed that \(A_{e}\notin \mathcal C \), since inequality (1) is obvious otherwise (for every \(p\ge 0\)). Note that every event \(C=A_f\in \mathcal C \) (hence also \(\overline{C}\)) is determined by the values of the random variables \(X_{e^{\prime }}\) with \(e^{\prime }\) at distance at most \(1\) from \(f\) (i.e., sharing a vertex with \(f\)). By our construction of \(D\), neither of such \(e^{\prime }\) is incident with \(v\), except possibly when \(f=e\). Let \(e_1,e_2,\ldots ,e_{d}\) denote the edges incident with \(v\), where \(e_d=e\), and let \(e_{d+1},\ldots ,e_m\) denote the remaining edges of \(G\). Then the event \(\bigcap _{C\in \mathcal C }\overline{C}\) is determined by the outcomes for (part of) the random variables \(X_{e_i}\) with \(i\ge d\). Denote \([15]=\{1,2,\ldots ,15\}\) and let \(Z\) be a set of all (partial) colourings of the edges \(e_d,\ldots ,e_m\) for which \(\bigcap _{C\in \mathcal C }\overline{C}\) holds, i.e., the set of vectors \(\widetilde{c}=(c_d,\ldots ,c_m)\in [15]^{m-d+1}\) such that \((X_{e_d},\ldots ,X_{e_m})=\widetilde{c}\) guarantees \(\bigcap _{C\in \mathcal C }\overline{C}\). Then (if \(\bigcap _{C\in \mathcal C }\overline{C}\ne \emptyset \), hence \(\mathbf{Pr }(\bigcap _{C\in \mathcal C }\overline{C})>0\)):Since \(A_{e}\) is determined by the outcomes for random variables associated with edges at distance at most \(1\) from \(e\), and the pallet of \(v\) by the outcomes for \(X_{e_1},\ldots ,X_{e_d}\), we thus obtain:where the maximum is taken over all partitions \(c^*=(d_1,\ldots ,d_{15})\) of \(d\) and all \(c_d\in [15]\). Note however that since a colour blind person cannot name a single colour, in particular the colour \(c_d\), then the bound from (4) is equivalent to the following one:(Note that the same upper bound as in (5) holds also for \(\mathbf{Pr }(A_{e})\).)
$$\begin{aligned} \mathbf{Pr }(A_{e}|\bigcap _{C\in \mathcal C }\overline{C})&= \frac{ \mathbf{Pr }(A_{e}\cap \bigcap _{C\in \mathcal C }\overline{C})}{ \mathbf{Pr }(\bigcap _{C\in \mathcal C }\overline{C})}\\&= \frac{\sum _{\widetilde{c}\in Z} \mathbf{Pr }(A_{e}|(X_{e_d},\ldots ,X_{e_m}) =\widetilde{c}) \mathbf{Pr }((X_{e_d},\ldots ,X_{e_m})=\widetilde{c})}{ \mathbf{Pr }(\bigcap _{C\in \mathcal C }\overline{C})}\\&\le \max _{\widetilde{c}\in Z} \mathbf{Pr }(A_{e}|(X_{e_d},\ldots ,X_{e_m}) = \widetilde{c}) \sum _{\widetilde{c}\in Z} \frac{ \mathbf{Pr }((X_{e_d},\ldots ,X_{e_m})=\widetilde{c})}{ \mathbf{Pr }(\bigcap _{C\in \mathcal C }\overline{C})}\\&= \max _{\widetilde{c}\in Z} \mathbf{Pr }(A_{e}|(X_{e_d},\ldots ,X_{e_m})=\widetilde{c})\\&\le \max _{\widetilde{c}\in [15]^{m-d+1}} \mathbf{Pr }(A_{e}|(X_{e_d},\ldots ,X_{e_m})=\widetilde{c}). \end{aligned}$$
$$\begin{aligned} \mathbf{Pr }(A_{e}|\bigcap _{C\in \mathcal C }\overline{C}) \le \max \mathbf{Pr }(c^*(v)=c^*|X_{e_d}=c_d), \end{aligned}$$
(4)
$$\begin{aligned} \mathbf{Pr }(A_{e}|\bigcap _{C\in \mathcal C }\overline{C}) \le \max _{c^*\in P(d,15)}\mathbf{Pr }(c^*(v)=c^*). \end{aligned}$$
(5)
Consider any fixed \(c^*=(d_1,\ldots ,d_{15})\in P(d,15)\), and denote the lengths of its consecutive maximal subsequences of identical integers by \(l_1,l_2,\ldots ,l_q\), where \(l_i\ge 1\) for \(i=1,\ldots , q\) and \(l_1+\cdots +l_q=15\). In other words, \(c^*\) is of the form \((\underbrace{d_1,\ldots ,d_1}_{l_1},\, \underbrace{d_{l_1+1},\ldots ,d_{l_1+1}}_{l_2},\, \ldots ,\, \underbrace{d_{15-l_q+1},\ldots ,d_{15-l_q+1}}_{l_q})\). Thenwhere \(\bigg (\begin{array}{c} d\\ {d_1\ldots d_{15}}\end{array}\bigg )\) is just the number of distinct partitions of \(d\) elements (edges) into 15 (enumerated) subsets \(S_1,\ldots ,S_{15}\) of cardinalities \(d_1,\ldots ,d_{15}\), resp., hence \(\bigg (\begin{array}{c} d\\ {d_1\ldots d_{15}}\end{array}\bigg )=\frac{d!}{d_1!d_2!\cdots d_{15}!}\), the factor \(15!\) appears due to the colour-blindness of a person trying to distinguish neighbours, for which every (bijective) assignment of colours \(1,\ldots ,15\) to the sets \(S_1,\ldots ,S_{15}\) yields the same pallet, while \(l_1!\ldots l_q!\) counts how many times a given colouring has been taken into account in our calculations. Let us denote by \(r(d_1,\ldots ,d_{15})\) (or \(r(c^*)\)) the number of repetitions in \(c^*\), where we call \(d_i\) a repetition if \(d_i=d_j\) for some \(j < i\) (hence \(r(d_1,\ldots ,d_{15})=15-q\)), and note that by (6),In fact such estimation has (almost) no influence on the result we are able to prove, but significantly simplifies calculations.
$$\begin{aligned} \mathbf{Pr }(c^*(v)=c^*) = {d\atopwithdelims (){d_1\ldots d_{15}}}\frac{15!}{l_1!\ldots l_q!}\frac{1}{15^d}, \end{aligned}$$
(6)
$$\begin{aligned} \mathbf{Pr }(c^*(v)=c^*) \le {d\atopwithdelims (){d_1\ldots d_{15}}}\frac{15!}{2^{r(c^*)}}\frac{1}{15^d}. \end{aligned}$$
(7)
By (1), (2), (3), (5) and (7), in order to prove Theorem 1, it is sufficient to show thatfor every \(c^*=(d_1,\ldots ,d_{15})\in P(d,15)\). We shall prove this inequality consecutively for the elements of an ascending family \(P_0(d,15)\subset P_1(d,15) \subset \ldots P_{14}(d,15)=P(d,15)\) of subsets of \(P(d,15)\), where \(P_r(d,15)=\{c^*\in P(d,15):r(c^*)\le r\}\) is just the set of all \(15\)-partitions of \(d\) with at most
\(r\) repetitions, \(r=0,\ldots ,14\).
$$\begin{aligned} e d^2 {d\atopwithdelims (){d_1\ldots d_{15}}}\frac{15!}{2^{r(c^*)}}\,\frac{1}{15^d}\le 1 \end{aligned}$$
(8)
2.3 Partitions without repetitions
We first consider \(c^*\in P_0(d,15)\), for which all \(d_i\) are distinct. We shall prove thatfor every \(d\ge 960\).
$$\begin{aligned} a_d:=e d^2 \max _{(d_1,\ldots ,d_{15})\in P_0(d,15)}{d\atopwithdelims (){d_1\ldots d_{15}}}15!\frac{1}{15^d}\le 0.8328\le 1 \end{aligned}$$
(9)
Given a not necessarily monotone sequence of non-negative integers \(k_1,\ldots ,k_{15}\) summing up to \(d\), by tightening its two elements \(k_i,k_j\) satisfying \(k_j\ge k_i+2\) we shall mean substituting these with the elements \(k_i+1\) and \(k_j-1\). Note that such operation always ‘increase the value’ of \(\bigg (\begin{array}{c}d\\ k_1\ldots k_{15}\end{array}\bigg )\), since if without lost of generality, \(i=1\) and \(j=15\), i.e, \(k_{15}\ge k_1+2>k_1+1\), then \(\bigg (\begin{array}{c}d\\ k_1+1 k_2\ldots k_{14} k_{15}-1\end{array}\bigg ) = \frac{k_{15}}{k_1+1} \bigg (\begin{array}{c}d\\ {k_1\ldots k_{15}}\end{array}\bigg )>{d\atopwithdelims (){k_1\ldots k_{15}}}\). Moreover, the minimum and maximum of this sequence shall be called its left and right borders, resp., and every integer which does not appear in the sequence, but is between its borders shall be called a gap.
Let \(c^*_{d,0}=(d_1,\ldots ,d_{15})\) be an element of \(P_0(d,15)\) for which the value of \(\bigg (\begin{array}{c} d\\ {d_1\ldots d_{15}}\end{array}\bigg )\) is maximal. Then this sequence has at most one gap, since otherwise we could tighten the element preceding the smallest gap and the element succeeding the largest gap creating no repetitions in the obtained one. For every \(d\) (sufficiently large) there is only one such sequence, due to the fact that its elements must sum up to \(d\). Namely, for \(d\equiv s \pmod {15},\, s\in \{0,\ldots ,14\}\), we have:We shall first show that the sequence \((a_d)_{d\ge 960}\) consists of \(15\) decreasing subsequences \((a_{15n+j})_{n\ge 64},\, j= 0,1,\ldots ,14\). For this purpose consider the following proportion (for \(d\equiv s \pmod {15}\)):The last inequality is obvious for \(s=0\), while for the remaining \(s\), the fact thator, equivalently,is a simple consequence of the following Theorem 3 on so called majorization inequality, applied for the function \(f(x)=\log _{0.5}x\).
$$\begin{aligned} a_d=e d^2 \frac{d!\left(\frac{d-s}{15}+8-s\right)!}{\left(\frac{d-s}{15}-7\right)!\left(\frac{d-s}{15}-6\right)! \ldots \left(\frac{d-s}{15}+8\right)!} 15!\frac{1}{15^d}. \end{aligned}$$
$$\begin{aligned} \frac{a_{d}}{a_{d-15}}&= \frac{d^2}{(d-15)^2}\frac{\left[\prod _{i=0}^{14}(d-i)\right]\,\left(\frac{d-s}{15}+8-s\right)}{\left(\frac{d-s}{15}-7\right)\left(\frac{d-s}{15}-6\right) \ldots \left(\frac{d-s}{15}+8\right)} \frac{1}{15^{15}}\nonumber \\&\le \frac{d^2}{(d-15)^2}\frac{\prod _{i=0}^{14}(d-i)}{\left(\frac{d}{15}-7\right)\left(\frac{d}{15}-6\right) \ldots \left(\frac{d}{15}+7\right)} \frac{1}{15^{15}}. \end{aligned}$$
$$\begin{aligned}&\left(\frac{d-s}{15}-7\right)\ldots \left(\frac{d-s}{15}+7-s\right) \left(\frac{d-s}{15}+9-s\right) \ldots \left(\frac{d-s}{15}+8\right)\\ \nonumber&\quad \ge \left(\frac{d}{15}-7\right) \left(\frac{d}{15}-6\right) \ldots \left(\frac{d}{15}+7\right) \end{aligned}$$
$$\begin{aligned}&\log _{0.5}\left(\frac{d}{15}-7\right) +\log _{0.5}\left(\frac{d}{15}-6\right)+ \cdots +\log _{0.5}\left(\frac{d}{15}+7\right)\\ \nonumber&\quad \ge \log _{0.5}\left(\frac{d-s}{15}-7\right)+\cdots +\log _{0.5}\left(\frac{d-s}{15}+7-s\right)\\ \nonumber&\qquad + \log _{0.5}\left(\frac{d-s}{15}+{9-s}\right)+ \cdots +\log _{0.5}\left(\frac{d-s}{15}+8\right) \end{aligned}$$
(10)
Theorem 3
(Karamata’s inequality, Kadelburg et al. 2005) Let \(I\) be an interval of the real line and let \(f\) denote a real-valued convex function defined on \(I\). If \(x_1\le x_2\le \cdots \le x_n\) and \(y_1\le y_2\le \cdots \le y_n\) are numbers in \(I\) such that \((x_1,\ldots ,x_n)\) majorizes \((y_1,\ldots ,y_n)\), i.e., \(x_1+\cdots +x_n=y_1+\cdots +y_n\) and \(x_1+\cdots +x_i\ge y_1+\cdots +y_i\) for \(i=1,\ldots ,n-1\), then
$$\begin{aligned} f(x_1)+\cdots +f(x_n)\ge f(y_1)+\cdots +f(y_n). \end{aligned}$$
By (10) we thus have:because \(d(d-11)(d-12)-(d-15)(d-15)(d+15) = -8d^2+357d-3375 < 0\) for \(d\ge 32,\, d(d-13)(d-14)-(d-15)(d-30)(d+30) = -12d^2+1082d-13500 < 0\) for \(d\ge 76\), and (since \(d\ge 960>4\cdot 15^2\)), \(\frac{(d-2i+1)(d-2i)}{(d-(i+2)15)(d+(i+2)15)} = \frac{d^2-(4i-1)d+2i(2i-1)}{d^2-(i+2)^2 15^2} < \frac{d^2-(4i-1)4\cdot 15^2+15^2}{d^2-(i+2)^2 15^2} = \frac{d^2-(16i-5)\cdot 15^2}{d^2-(i+2)^2 15^2}<1\) for \(i=1,\ldots ,5\). Computing \(a_{960}=0.83275<0.8328,\, a_{961}=0.74,\, a_{962}=0.67,\, a_{963}=0.62,\, a_{964}=0.58,\, a_{965}=0.55,\, a_{966}=0.53,\, a_{967}=0.52,\, a_{968}=0.51,\, a_{969}=0.52,\, a_{970}=0.53,\, a_{971}=0.56,\, a_{972}=0.59,\, a_{973}=0.64,\, a_{974}=0.71\), by inequality (11) we thus obtain \(a_d<0.8328\) for \(d\ge 960\), i.e., (9) holds.
$$\begin{aligned} \frac{a_{d}}{a_{d-15}}&\le \frac{d^2}{(d-15)^2}\frac{\prod _{i=0}^{14}(d-i)}{\left(d-7\cdot 15\right)\left(d-6\cdot 15\right) \ldots \left(d+7\cdot 15\right)}\nonumber \\&= \left[\prod _{i=1}^5\left(\frac{(d-2i+1)(d-2i)}{(d-(i+2)15)(d+(i+2)15)}\right)\right]\nonumber \\&\times \left(\frac{d(d-11)(d-12)}{(d-15)(d-15)(d+15)}\right) \left(\frac{d(d-13)(d-14)}{(d-15)(d-30)(d+30)}\right)\nonumber \\&< 1, \end{aligned}$$
(11)
Now we shall extend this result, and show thatfor every \(d\ge 960\) and \(i=0,1,\ldots ,14\) (where \(P_{-1}(d,15):=\emptyset \)). This will imply (8) and finalize the proof. It is then the more sufficient to show thatfor \(d\ge 960\) and \(i=0,1,\ldots ,14\). The proof of this fact shall be inductive with respect to \(i\). The case of \(i=0\) being already considered, let us fix \(i\ge 1,\, i\le 14\), and assume that (13) holds for \(a_{d,i^{\prime }}\) with \(i^{\prime }<i\). Let \(c^*_{d,i}=(d_1,\ldots ,d_{15})\) be an element of \(P_i(d,15)\) for which the value of \(\bigg (\begin{array}{c}d\\ {d_1\ldots d_{15}}\end{array}\bigg )\) is maximal. If \(c^*_{d,i}\in P_{i-1}(d,15)\), then (13) holds by induction hypothesis. Assume then that our \(c^*_{d,i}\) contains exactly \(i\) repetitions (\(i\ge 1\)). Observe then that \(c^*_{d,i}\) cannot contain any gaps, since otherwise we could tighten two of its element creating no additional repetitions (contradicting maximality of \(c^*_{d,i}\)). Indeed, if any repetition of \(c^*_{d,i}\) was larger than some gap, then we could tighten this repetition and the element of \(c^*_{d,i}\) preceding its smallest (left-most) gap, and analogously in the opposite case (i.e., when a repetition was smaller than some gap). Finally note that to prove (13) for our fixed \(i\), by induction hypothesis, it is sufficient to prove for every \(d\ge 960\) that at least one of the following two conditions holds:
(the later for \(i\ge 2\)). In fact this is exactly what we shall do for almost every \(i\). We will have to by slightly more careful with the case of \(i=1\) though.
$$\begin{aligned} e d^2 \max _{(d_1,\ldots ,d_{15})\in P_i(d,15)\backslash P_{i-1}(d,15)}{d\atopwithdelims (){d_1\ldots d_{15}}}\frac{15!}{2^{i}}\,\frac{1}{15^d}\le 1 \end{aligned}$$
(12)
$$\begin{aligned} a_{d,i}:= e d^2 \max _{(d_1,\ldots ,d_{15})\in P_i(d,15)}{d\atopwithdelims (){d_1\ldots d_{15}}}\frac{15!}{2^{i}}\,\frac{1}{15^d}\le 1 \end{aligned}$$
(13)
$$\begin{aligned} \max _{(d^{\prime \prime }_1,\ldots ,d^{\prime \prime }_{15})\in P_i(d,15)}{d\atopwithdelims (){d^{\prime \prime }_1\ldots d^{\prime \prime }_{15}}}&\le 2\max _{(d^{\prime \prime }_1,\ldots ,d^{\prime \prime }_{15})\in P_{i-1}(d,15)}{d\atopwithdelims (){d^{\prime \prime }_1\ldots d^{\prime \prime }_{15}}}\end{aligned}$$
(14)
$$\begin{aligned} \max _{(d^{\prime \prime }_1,\ldots ,d^{\prime \prime }_{15})\in P_i(d,15)}{d\atopwithdelims (){d^{\prime \prime }_1\ldots d^{\prime \prime }_{15}}}&\le 4\max _{(d^{\prime \prime }_1,\ldots ,d^{\prime \prime }_{15})\in P_{i-2}(d,15)}{d\atopwithdelims (){d^{\prime \prime }_1\ldots d^{\prime \prime }_{15}}} \end{aligned}$$
(15)
2.4 Partitions with one repetition
Assume that \(i=1\), hence \(c^*_{d,i} = c^*_{d,1}= (d_1,d_1+1,\ldots ,d_1+t,d_1+t,d_1+t+1,\ldots ,d_1+13)\) for some \(t\in \{0,\dots ,13\}\). Consequently, \(d=15d_1+91+t\le 15d_1+104\), and hence \(d_1\ge \frac{d-104}{15}\). Note that our repetition must be ‘closer’ to one of the borders of \(c^*_{d,1}\), and let us denote the smaller of these two ‘distances’ by \(b\), i.e., \(b\in \{0,\ldots ,6\}\) is an integer such that \(\{t,13-t\}=\{b,13-b\}\). Then we may ‘make’ of \(c^*_{d,1}\) a partition of \(d\) without repetitions by substituting its elements \(d_1+b\) and \(d_1+13-b\) with \(d_1-1\) and \(d_1+14\), respectively (and ordering non-decreasingly). For the obtained partition \(\left(d^{\prime }_1,\ldots ,d^{\prime }_{15}\right)\) we then have:Since \(\prod _{j=0}^6\frac{d_1+8+j}{d_1+j}\) is a decreasing function of \(d_1\) (for \(d_1\ge 1\)) and \(d_1\ge \frac{d-104}{15}\ge \frac{856}{15}\) (for \(d\ge 960\)), we thus obtain:but since \((d^{\prime }_1,\ldots ,d^{\prime }_{15})\in P_0(d,15)\), by (9) we have:Consequently,thus (13) holds for \(i=1\).
$$\begin{aligned} {d\atopwithdelims (){d_1\ldots d_{15}}} = {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^b\frac{d_1+14-b+j}{d_1+j} \le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^6\frac{d_1+8+j}{d_1+j}. \end{aligned}$$
$$\begin{aligned} {d\atopwithdelims (){d_1\ldots d_{15}}} \le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^6\frac{\frac{856}{15}+8+j}{\frac{856}{15}+j} \le 2.4015 {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}, \end{aligned}$$
$$\begin{aligned} {d\atopwithdelims (){d_1\ldots d_{15}}} \le 2.4015 \frac{0.8328}{e d^2 15!\frac{1}{15^d}}. \end{aligned}$$
$$\begin{aligned} a_{d,1}\le e d^2 \frac{2.4015 \cdot 0.8328}{e d^2 15!\frac{1}{15^d}}\frac{15!}{2^{1}}\frac{1}{15^d} = 0.9999846 \le 1, \end{aligned}$$
2.5 Partitions with at least two repetitions
Assume now that \(i\ge 2\). Since \(d_1\) and \(d_1+14-i\) are the borders of \(c^*_{d,i}\), then analogously as above, \(d\le d_1+(d_1+1)+\cdots +(d_1+14-i)+i(d_1+14-i) = 15d_1+\frac{(15-i)(14-i)}{2}+i(14-i) = 15d_1+\frac{(15+i)(14-i)}{2} \le 15d_1+102\) (for \(i\ge 2\)), hence \(d_1 \ge \frac{d-102}{15}\ge \frac{858}{15}\).
Consider first the case when at least one of the repetitions of \(c^*_{d,i}\), say \(d_1+t\), is ‘at distance’ at most \(3\) from one of the borders, i.e., there exists an integer \(b\in \{0,\ldots ,3\}\) such that \(\{t,14-i-t\}=\{b,14-i-b\}\). Then we may ‘make’ of \(c^*_{d,i}\) a partition of \(d\) with at most \(i-1\) repetitions by substituting its elements \(d_1+b\) and \(d_1+14-i-b\) with \(d_1-1\) and \(d_1+15-i\), respectively. For the obtained partition \((d^{\prime }_1,\ldots ,d^{\prime }_{15})\in P_{i-1}(d,15)\) we then have:hence (13) holds by (14).
$$\begin{aligned} {d\atopwithdelims (){d_1\ldots d_{15}}}&= {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^b\frac{d_1+15-i-b+j}{d_1+j}\\&\le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^b\frac{d_1+13-b+j}{d_1+j}\\&\le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^3\frac{d_1+10+j}{d_1+j}\\&\le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^3\frac{\frac{858}{15}+10+j}{\frac{858}{15}+j}\\&= 1.88 {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\\&\le 2 \max _{(d_1^{\prime \prime },\ldots ,d_{15}^{\prime \prime })\in P_{i-1}(d,15)}{d\atopwithdelims (){d_1^{\prime \prime }\ldots d_{15}^{\prime \prime }}}, \end{aligned}$$
Assume then that every repetition of \(c^*_{d,i}\) is between \(d_1+4\) and \(d_1+10-i\) (hence \(2\le i\le 6\)). Choose any two repetitions \(d_1+t\) and \(d_1+t^{\prime }\) of \(c^*_{d,i}\) with \(4\le t\le t^{\prime }\le 10-i\) (possibly \(t=t^{\prime }\)), and let \(a=\max \{t,14-i-t^{\prime }\}\), hence \(t^{\prime }-t+a\le 8\), and thus \(a\le 8\). Then we may ‘make’ of \(c^*_{d,i}\) a partition of \(d\) with at most \(i-2\) repetitions by substituting its elements \(d_1+t\) and \(d_1+t^{\prime }\) with \(d_1+t-a-1<d_1\) and \(d_1+t^{\prime }+a+1>d_1+14-i\), respectively. For the obtained partition \((d^{\prime }_1,\ldots ,d^{\prime }_{15})\in P_{i-2}(d,15)\) we then have: hence (13) holds by (15). The proof of Theorem 1 is thus completed.
$$\begin{aligned} {d\atopwithdelims (){d_1\ldots d_{15}}}&= {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^a\frac{d_1+t^{\prime }+1+j}{d_1+t-a+j}\\&\le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^a\frac{d_1+(8+t-a)+1+j}{d_1+t-a+j}\\&\le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^8\frac{d_1+t+1+j}{d_1+t-8+j}\\&\le {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\prod _{j=0}^8\frac{\frac{858}{15}+5+j}{\frac{858}{15}-4+j}\\&= 3.734 {d\atopwithdelims (){d^{\prime }_1\ldots d^{\prime }_{15}}}\\&\le 4 \max _{(d_1^{\prime \prime },\ldots ,d_{15}^{\prime \prime })\in P_{i-2}(d,15)}{d\atopwithdelims (){d_1^{\prime \prime }\ldots d_{15}^{\prime \prime }}}, \end{aligned}$$
Acknowledgments
This research was partly supported by the National Science Centre Grant No. DEC-2011/01/D/ST1/04154 and by the Polish Ministry of Science and Higher Education. I enclose special thanks to Andrzej Żak for fruitful discussions in 306A.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.