On the lower bound for the van der Waerden function
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.
- Lower bounds on some certain van der Waerden functions.
- A pseudo upper bound for the van der Waerden function
- A new lower bound for van der Waerden numbers
- New lower bounds for van der Waerden numbers
- Bounds on some van der Waerden numbers
- A new method to construct lower bounds for van der Waerden numbers
- A lower bound for off-diagonal van der Waerden numbers
- On the existence of a reasonable upper bound for the van der Waerden numbers
- Lower bounds on van der Waerden numbers: randomized- and deterministic-constructive
- On a generalization of the van der Waerden theorem
- A Construction for Partitions Which Avoid Long Arithmetic Progressions
- A new proof of Szemerédi's theorem
- An application of Lovász' local lemma-A new lower bound for the van der Waerden number
- Combinatorial Theorems on Classifications of Subsets of a Given Set
- Notes on Number Theory II : On a theorem of van der Waerden
- Two combinatorial theorems on arithmetic progressions
This page was built for publication: On the lower bound for the van der Waerden function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q369596)
