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.