# Upper bound on induced Ramsey numbers

The induced Ramsey number $$r^*(G)$$ is the least integer $$m$$ for which there exists a graph $$H$$ with $$m$$ vertices so that in any $$2$$-coloring of the edges of $$H$$, there is always an induced monochromatic copy of $$G$$ in $$H$$. The existence of $$r^*(G)$$ was proved independently by Deuber [1], Erdös, Hajnal and Pósa [7], and Rödl [6]. It was proved by Harary, Nešetril and Rödl that [3] that $$r^*(P_4)=8$$. Erdös and Rödl [2] asked the following question:

# Problem (proposed by Erdös and Rödl [2])

If $$G$$ has $$n$$ vertices, is it true that $r^*(G) < c^n$ for some absolute constant $$c$$?

The above inequality holds for the case that $$G$$ is a bipartite graph[6]. Łuczak and Rödl [5] showed that a graph on $$n$$ vertices with bounded degree has its induced Ramsey number bounded by a polynomial in $$n$$, confirming a conjecture of Trotter.

Suppose $$G$$ has $$k$$ vertices and $$H$$ has $$t\geq k$$ vertices. Kohayakawa, Prömel, and Rödl [4] proved that the induced Ramsey number $$r^*(G,H)$$ satisfies the following bound:

$$\displaystyle r^*(G,H)\leq t^{ck\log q}$$

where $$q$$ denotes the chromatic number of $$H$$ and $$c$$ is some absolute constant. This implies

$$\displaystyle r^*(G) < k^{ck \log k}.$$

Bibliography
1 W. Deuber, Generalizations of Ramsey's theorem, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 323-332, North-Holland, Amsterdam, 1975.

2 P. Erdös, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 183-192 (loose errata), Academia, Prague, 1975.

3 F. Harary, J. Nešetril and V. Rödl. Generalized Ramsey theory for graphs, XIV, Induced Ramsey numbers, Graphs and other Combinatorial Topics (Prague, 1982), 90-100.

4 Y. Kohayakawa, H.-J. Prömel and V. Rödl, Induced Ramsey numbers, preprint.

5 T. Łuczak and V. Rödl, On induced Ramsey numbers for graphs with bounded maximum degree, J. Comb. Theory Ser. B 66 (1996), 324-333.

6 V. Rödl, The dimension of a graph and generalized Ramsey theorems, thesis, Charles Univ. Praha, 1973.

7 P. Erdös, A. Hajnal and L. Pósa, Strong embeddings of graphs into colored graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 585-595, North-Holland, Amsterdam, 1975.