Recurrent upper bounds in the Erdos-Hajnal problem on hypergraph coloring and its generalizations

In 1961, P. Erdos and A. Hajnal posed a problem of finding the quantity m(n) equal to the minimum number of edges in an n-uniform hypergraph with chromatic number greater than 2. Different asymptotic bounds are now known for m(n). However, exact values are found only for n ≤ 3. For other small values of n, only recurrent estimates are obtained. We consider an important generalization of the problem. Namely, we are interested in a quantity mk(n) equal to the minimum number of edges in an n-uniform hypergraph that does not admit a bichromatic coloring of the set of its vertices such that any edge contains in it at least k vertices of the first color and at least k vertices of the second color. We can find a series of recurrent bounds on mk(n). These bounds considerably strengthen all the previously known estimates for most values of n and k.