On the lower bound for the van der Waerden function (Q369596)

The author's main result is a new asymptotic lower bound for the van der Waerden function \(W(n,r)\) [\textit{L. van der Waerden}, Nieuw Arch. 15, 212--216 (1927; JFM 53.0073.12)]. For this he uses an improved version of the Erdős-Lovász theorem [Colloq. Math. Soc. János Bolyai 10, 609--627 (1975; Zbl 0315.05117)] as follows. Theorem. If the degree of each vertex of an \(n\)-uniform hypergraph \(H\) does not exceed \[ d = \left(\frac{\sqrt 6-2}{4}\right)\frac {r^{n-1}}{\sqrt {n\ln n}} \] then \(\chi(H)\leq r\). The proof of this theorem is based on the application of the local lemma as well as on the random coloring method for the vertices of the hypergraph in \(r\) colors; this proof was proposed by the author in [Math. Notes 85, No. 6, 902--905 (2009); translation from Mat. Zametki 85, No. 6, 951--954 (2009; Zbl 1191.05044)]. This theorem implies the following lower bound for the van der Waerden function \(W(n, r)\). Theorem. For all \(n\geq 3\), \(r\geq 2\), the following inequality holds: \[ W(n, r)\geq \left(\frac{\sqrt 6-2}{4}\right)\frac {r^{n-1}}{\sqrt {n\ln n}}\left(1-\frac 1n\right). \] This estimate improves the Erdős-Lovász estimate for \(n\geq 15\). But, at the same time, this inequality is inferior asymptotically to \textit{Z. Szabó}'s estimate [Random Struct. Algorithms 1, No. 3, 343--360 (1990; Zbl 0723.05115)] if \(r=2\). When \(r\) is exponentially large compared to \(n\) \((n = o(\ln r))\), \textit{L. Moser}'s estimate [Can. Math. Bull. 3, 23--25 (1960; Zbl 0100.27103)] remains the best.