×

On induced Ramsey numbers. (English) Zbl 1004.05042

The induced Ramsey number \(\text{IR}(G,H)\) is the smallest integer \(n\) for which there exists a graph \(F\) on \(n\) vertices such that any 2-colouring of its edges in red and blue produces either or both of a copy of a graph \(G\) induced in \(F\) with all of its edges red, or a copy of a graph \(H\) induced in \(F\) with all of its edges blue. A 2-colouring of the edges of a graph \(F\) partitions \(F\) into monochromatic subgraphs \(F_r\) and \(F_b\), containing respectively (all vertices and) all red edges and all blue edges. The weak induced Ramsey number \(\text{IR}_{\text{w}}(G,H)\) is the smallest integer \(n\) for which there exists a graph \(F\) on \(n\) vertices such that any 2-colouring of its edges in red and blue produces either or both of a copy of \(G\) induced in \(F_r\), or a copy of \(G\) induced in \(F_b\). The induced planar Ramsey number \(\text{IPR}(G,H)\) and the weak induced planar Ramsey number \(\text{IPR}_{\text{w}}(G,H)\) are defined analogously to \(\text{IR}(G,H)\) and \(\text{IR}_{\text{w}}(G,H)\), with the additional restriction that, in the 2-colouring of the edges of \(F\), \(F_r\) is planar. For any positive integer \(k\), \(kK_2\) denotes a matching consisting of \(k\) vertex-disjoint copies of \(K_2\).
From the authors’ introduction: “The existence of \(\text{IR}(G,H)\) for each pair of graphs \(G\) and \(H\) was proved independently by Deuber, P. Erdős et al.[Colloq. Math. Soc. János Bolyai 10, 585-595 (1975; Zbl 0312.05123)] and Rödl, but not much is known about the behavior of the induced Ramsey numbers, and most of the results are of asymptotic type [e.g., see I. Gorgol, Discrete Math. 235, 159-163 (2001; Zbl 0978.05053), P. E. Haxell, Y. Kohayakawa and T. Łuczak, Comb. Probab. Comput. 4, 217-239 (1995; Zbl 0839.05073), Y. Kohayakawa, H. J. Prömel and V. Rödl, Combinatorica 18, 373-404 (1998; Zbl 0913.05074), T. Łuczak and V. Rödl, J. Comb. Theory, Ser. B 66, No. 2, 324-333 (1996; Zbl 0855.05084)]. Following K. Walker [Bull. Lond. Math. Soc. 1, 187-190 (1969; Zbl 0184.27705)] and R. Steinberg and C. A. Tovey [J. Comb. Theory, Ser. B 59, 288-296 (1993; Zbl 0794.05091)] we consider a planar version of the induced Ramsey number, and determine its value for some pairs of graphs. In particular, we show that, in the planar case, the induced Ramsey number and its ‘weak’ counterpart may substantially differ from each other.”
Theorem 1. For arbitrary \(k\geq 1\) and \(n\geq 2\) \(\text{IR}(kK_2,K_n)=kn\). Theorem 2. Let \(n\geq 3\). Then \(\lfloor\frac{3n}2\rfloor\leq \text{IR}(P_3,P_n)\leq 2n-1\) and \(\lfloor\frac{4n}3\rfloor\leq \text{IR}(P_3,P_n)\leq \lceil\frac{5n}3\rceil\). Theorem 3. Any planar graph \(G\) on \(n+5\) vertices, where \(n\geq 1\), contains either an induced matching \(2K_2\) or an independent set of \(n\) vertices. Theorem 4. For \(n\geq 2\) we have \(\text{IPR}_{\text{w}}(2K_2,K_n)= 2n\) for \(n\in\{2,3,4\}\) and \(n+5\) for \(n\geq 5\). Theorem 5. For \(n\geq 2\), \(\text{IPR}(2K_2,K_n)=2n\).
The question is raised as to whether there exists an infinite family of graphs \(\{H_n\}_n\) such that \[ \limsup_{n\to\infty}\frac{\text{IR}(G,H_n)} {\text{IR}_{\text{w}}(G,H_n) }>1 \] for some graph \(G\).

MSC:

05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI