Improvement of the lower bound in the Erdös-Hajnal combinatorial problem
In 1961 Erdős and Hajnal posed the problem of finding the minimum possible number \(m(n,r)\) of edges in an \(n\)-uniform hypergraph with a chromatic number large than \(r\). Later, Erdős proved the first nontrivial bounds for \(m(n, 2)\), which are easy to extend to arbitrary \(r\). Several asymptotic bounds for \(m(n,r)\) have been obtained over the last year. For arbitrary \(n\geq 2\) and \(r\geq 2\), the author has shown that \[ m(n,r)\geq (\sqrt 3-1)\left({n}{\ln n}\right)^{1/2} r^{n-1}. \] A. Pluhár has improved that result by showing for many values of \(r\) \[ m(n,r)\geq \frac 1{\sqrt{4\pi e}}n^{\frac 12-\frac 1{2r}}r^{n-1}. \] In this paper the following more accurate argument improving this result is stated. Theorem 1. For all positive integers \(n\geq 2\) and \(r\geq 2\), \[ m(n,r)\geq \left(\pi^{\frac 1r}e^{\frac 1{12(n-1)}}\right) \frac 1{e\sqrt{2\pi}}(n-1)^{\frac 12-\frac 1{2r}}r^{n+\frac2r}. \]
scientific article; zbMATH DE number 5621455