On the Ramsey problem for multicolor bipartite graphs (Q1277209)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Ramsey problem for multicolor bipartite graphs |
scientific article |
Statements
On the Ramsey problem for multicolor bipartite graphs (English)
0 references
2 February 1999
0 references
Given positive integers \(i,j\), let \(K_{i,j}\) denote a bipartite complete graph and let \(R_r(m,n)\) be the smallest integer \(a\) such that for any \(r\)-colouring of the edges of \(K_{a,a}\) one can always find a monochromatic subgraph isomorphic to \(K_{m,n}\). It is shown that \(R_2(m,n)\leq 2^m (n-1)+ 2^{m-1}-1\), which generalizes the results for \(m=2, 3\) due to Beineke and Schwenk. Moreover, a class of lower bounds based on properties of orthogonal Latin squares is found which establishes that \(\lim_{r\to \infty}R_r(2,2) r^{-2}=1\).
0 references
Ramsey problem
0 references