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

    Identifiers