Improvement of the lower bound in the Erdös-Hajnal combinatorial problem (Q736013)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improvement of the lower bound in the Erdös-Hajnal combinatorial problem |
scientific article |
Statements
Improvement of the lower bound in the Erdös-Hajnal combinatorial problem (English)
0 references
26 October 2009
0 references
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}. \]
0 references