Linear Ramsey Numbers for Bounded-Degree Hypergrahps
Affiliation:
1. National Research Nuclear University MEPHI Moscow Engineering Physics Institute, 115409, Kashirskoe shosse, 31, Moscow, Russian Federation;2. Federal Research Center ” Computer Science and Control” of the Russian Academy of Sciences, Vavilova 44-2, 119333, Moscow, Russian Federation
Abstract:
We show that the Ramsey number is linear for every uniform hypergraph with bounded degree. This is a hypergraph extension of the famous theorem for ordinary graphs which Chvátal et al. [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), pp. 239–243] showed in 1983. Our proof demonstrates the potential of a new regularity lemma by [Y. Ishigami, A simple regularization of hypergraphs, preprint, arXiv:math/0612838 (2006)].
