Randomized algorithms for colorings of uniform hypergraphs with large girth and their applications in Ramsey Theory
Dmitry Shabanov
Moscow
Abstract.
The classical theorems that laid the foundation of Ramsey Theory (e.g. the Ramsey Theorem, the Van der Waerden Theorem) can be reformulated in terms of hypergraph coloring theory. Thus, one may expect that extremal results concerning colorings of uniform hypergraphs could be applied for obtaining the quantitative estimates in such theorems. By using randomized algorithms we prove a new lower bound for the maximum vertex degree in an uniform hypergraph with large girth in terms of its chromatic number and, as an application, establish a new lower for the classical Van der Waerden number.