3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Chvátal, Rödl, Szemerédi and Trotter proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. We prove that the same holds for 3-uniform hypergraphs. The main new tool which we prove and use is an embedding lemma for 3-uniform hypergraphs of bounded maximum degree into suitable 3-uniform `pseudo-random' hypergraphs.
19 pages, 1 figure, submitted to J. Comb. Theory Ser. B

Keywords

Combinatorics, 05D10

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/115462

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0608442
 http://arxiv.org/abs/math/0608442

Collections

arXiv