| Abstract: |
We say that a graph F strongly arrows (G, H) and write F >->
(G, H) if for every edge-coloring of F with colors red and blue a red G or a blue H occurs as an induced subgraph of F.
Induced Ramsey numbers are defined by r*(G, H) = min{ |V(G)| : F >-> (G,
H)}. The value of r*(G, H) is finite for all graphs, and good upper bounds on
induced Ramsey numbers in general, and for particular families of graphs are known. Most of these results, however, use the probabilistic
method, and therefore do no yield explicit constructions. This paper provides
several constructions for upper bounds on r*(G, H) including r*(Cn)
< c{(log n)^2}, r*(T, Kn) < |T|
n{|T| log |T|}, r*(B, Cn) < |B|{2[log
n]+2}, where T is a tree, B is bipartite, Kn is the complete graph on n vertices and
Cn a cycle on n vertices. We also have some new upper bounds for small graphs:
r*(K3+e) <= 21, and r*(K4-e)
<= 46.
|