Multipartite Ramsey Numbers of Double Stars
摘要
Let s be a positive integer with \(s\ge 2\) and \(G_1,G_2\) be simple graphs. The set multipartite Ramsey number \(M_s(G_1,G_2)\) is the smallest positive integer c such that any 2-coloring of the edges of \(K_{c\times s}\) contains a monochromatic copy of \(G_i\) in color i for some \(i\in \{1,2\}\) . Let c be a positive integer with \(c\ge 2\) . The size multipartite Ramsey number \(m_c(G_1,G_2)\) is the smallest positive integer s such that any 2-coloring of the edges of \(K_{c\times s}\) contains a monochromatic copy of \(G_i\) in color i for some \(i\in \{1,2\}\) . For \(a\ge b\ge 0\) , the double star S(a, b) is the graph on the vertex-set \(\{v_0,v_1,\dots ,v_a,w_0,w_1,\ldots ,w_b\}\) with edge-set \(\{v_0w_0,v_0v_i,w_0w_j|1\le i\le a,1\le j\le b\}.\) In this paper, we utilize \((-1,1)\) -matrices and strongly regular graphs to establish some lower and upper bounds, and some exact values of the set or size multipartite Ramsey numbers of double stars.