Upper bound on induced Ramsey numbers
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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:
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, 323332, NorthHolland,
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), 183192 (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), 90100.

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), 324333.

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, 585595, NorthHolland,
Amsterdam, 1975.
