Improvement of the lower bound in the Erdös-Hajnal combinatorial problem
type: Item
instance of: scholarly article
title: Improvement of the lower bound in the Erdös-Hajnal combinatorial problem
zbMATH Open document ID: 1281.05099
DOI: 10.1134/S1064562409030132
published in: Doklady Mathematics
publication date: 2009-10-26T00:00:00Z
review text: 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}. \]
reviewed by: Olaf Ninnemann
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5621455
author: D. A. Shabanov
MaRDI profile type: Publication
cites work: On a property of families of sets
cites work: On a combinatorial problem. II
cites work: Ein kombinatorisches Problem von P. Erdős und A. Hajnal
cites work: On a combinatorial problem of P. Erdős and L. Lovasz
cites work: On 3-chromatic hypergraphs
cites work: Improved bounds and algorithms for hypergraph 2-coloring
cites work: Hypergraphs with high chromatic number
cites work: Coloring uniform hypergraphs with few colors
full work available at URL: s1064562409030132
OpenAlex ID: W2018064035
description: scientific article; zbMATH DE number 5621455