Induced Ramsey numbers (Q1288912): Difference between revisions

The induced Ramsey number \(r_{\text{ind}}(G,H)\), is the smallest possible order of a graph \(F\) with the property that if the edges of \(F\) are \(2\)-colored, there is an induced subgraph of \(G\) in the first color or \(H\) in the second color. It is shown for any graphs \(G\) and \(H\) with \(k = | G| \leq | H| = t\) and \(q = \chi(H)\), the chromatic number of \(H\), that \(r_{\text{ind}}(G,H) \leq t^{Ck \log q}\) for some constant \(C\). Related results and conjectures are presented; in particular, it is conjectured that there is a constant \(f = f(G)\) such that if \(t = | H| \), then \(r_{\text{ind}}(G,H) \leq t^{f}\). When \(G\) is a tree a polynomial bound, in terms of both \(t\) and \(k\), on \(r_{\text{ind}}(G,H)\) is proved. The proofs use probabilistic techniques and random graphs that are based on projective planes.