A short proof of the induced Ramsey Theorem for hypergraphs

作者：Bhat Vindya^*; Roedl Vojtech

来源：Discrete Mathematics, 2016, 339(3): 1147-1149.

DOI：10.1016/j.disc.2015.09.019

• Induced Ramsey Theorem
• Hypergraph
• Partite lemma

For fixed r >= 2, an r-graph G = (V, E) is an r-uniform hypergraph with vertex set V and edge set E subset of ((v)(r)). For k >= r >= 2, let K-k denote the complete r-graph on k vertices and let (K-k) over bar denote its complement, an independent set on k vertices.
The Induced Ramsey Theorem states that for c, r >= 2 and every r-graph G, there exists an r-graph H such that every c-coloring of the edges of H contains a monochromatic induced copy of G. A natural question to ask is what other subgraphs F can be partitioned and have a similar Ramsey property. One can show that if F not equal K-k or F not equal (K-k) over bar, then this fails to be true. On the other hand, a result of Abramson and Harrington (1978) and Nesetril and Rodl (1977) implies that F not equal K-k, as well as F not equal (K-k) over bar, has the Ramsey property.
The proof of the Induced Ramsey Theorem was based on a partite lemma and partite construction as shown in Nesetril and Rodl (1977) and Nesetril and Rodl (1987). In this note, we present a short proof of this result by eliminating the partite construction to show that the theorem is a direct consequence of the Hales Jewett Theorem. In other words, we have reduced the proof of this result to one step, rather than two steps.

• 出版日期2016-3-6