Mono-multi bipartite Ramsey numbers, designs, and matrices (Q817616)

The mono-multi bipartite Ramsey number BRR\((G_1,G_2)\) is the smallest \(N\) such that any edge coloring of the complete bipartite graph \(K_{N,N}\) contains either a monochromatic \(G_1\) or a multicolored \(G_2\). The problem of finding the values of BRR\((G_1,G_2)\) is reformulated in terms of matrices for the case that \(G_1\) is a star and \(G_2\) is a star forest: Given positive integers \(\lambda, r\) and \(s\), \(n=n_\lambda(r,s)\) is the smallest number such that in any \(n\times n\) matrix \(A\) either some entry is repeated at least \(\lambda\) times in some row or column, or there is an \(r\times s\) submatrix \(B\) in \(A\) whose elements are all distinct. In addition, an asymmetric version of this problem is formulated for asymmetric \(m\times n\) matrices \(A\); the corresponding Ramsey type numbers are denoted by \(n_\lambda(r,s;m)\). It is shown that \(n_\lambda(2,2)=3\lambda-2\), implying that the lower bound of \textit{L. Eroh} and \textit{R. Oellermann} [Discrete Math. 277, 57--72 (2004; Zbl 1036.05032)] is tight for BRR\((K_{1,\lambda},K_{2,2})\). Moreover, it is shown that \(n_\lambda(2,2;\lambda)=\lambda^2\), i.e., for any \(\lambda\) and \(n\geq\lambda^2\) every edge coloring of \(K_{\lambda,n}\) contains either a monochromatic \(K_{1,\lambda}\) or a multicolored \(K_{2,2}\). In addition, an upper bound for \(n_\lambda(r,s;m)\) is derived which is shown to be sharp for \(n_\lambda(3,s;m)\) and infinitely many appropriate values of \(m,\lambda\) and \(s\). In particular, \(n_3(3,3;5)=n_3(3,3;6)=71\).