A short proof of the induced Ramsey Theorem for hypergraphs

详细信息    查看全文

• 作者：Vindya Bhat ; ^{vbhat@cims.nyu.edu" class="auth_mail" title="E-mail the corresponding author} ; Vojtěch Rö ; dl
• 关键词：Induced Ramsey Theorem ; Hypergraph ; Partite lemma
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 March 2016
• 年：2016
• 卷：339
• 期：3
• 页码：1147-1149
• 全文大小：384 K

文摘

For fixed r≥2$r\ge 2$, an r$r$-graph   G=(V,E)$G=(V,E)$ is an r$r$-uniform hypergraph with vertex set V$V$ and edge set $E\subseteq \left(\genfrac{}{}{00}{}{V}{r}\right)$. For k≥r≥2$k\ge r\ge 2$, let K_k$K_k$ denote the complete r$r$-graph on k$k$ vertices and let $\overline{K_k}$ denote its complement, an independent set on k$k$ vertices.

The Induced Ramsey Theorem states that for c,r≥2$c,r\ge 2$ and every r$r$-graph G$G$, there exists an r$r$-graph H$H$ such that every c$c$-coloring of the edges of H$H$ contains a monochromatic induced copy of G$G$. A natural question to ask is what other subgraphs F$F$ can be partitioned and have a similar Ramsey property. One can show that if F≠K_k$F\ne K_k$ or $F\ne \overline{K_k}$, then this fails to be true. On the other hand, a result of Abramson and Harrington (1978) and Nešetřil and Rödl (1977) implies that F=K_k$F=K_k$, as well as $F=\overline{K_k}$, has the Ramsey property.

The proof of the Induced Ramsey Theorem was based on a partite lemma and partite construction as shown in Nešetřil and Rödl (1977) and Nešetřil and Rödl (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.