Size bipartite Ramsey numbers (Q1011777)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Size bipartite Ramsey numbers
scientific article

    Statements

    Size bipartite Ramsey numbers (English)
    0 references
    0 references
    0 references
    9 April 2009
    0 references
    For bipartite graphs \(B_1\) and \(B_2\), the \textit{size bipartite Ramsey number} \(\widehat{br}(B_1, B_2)\) is the size of the smallest bipartite graph \(B\) such that in any \(2\)-coloring of the edges of \(B\) there will be copy of \(B_1\) in the first color or a copy of \(B_2\) in the second color. It is shown that if \(m\) is fixed and \(n\) is sufficiently large, then \[ \frac{1}{e}m2^mn \leq \widehat{br}(K_{m,n}, K_{m,n}) \leq {4m^2}{2^m}n. \] Also, it is shown for \(n\) sufficiently large that \[ \frac{1}{15}n{2^n} \leq \widehat{br}(K_{n,n}, K_{n,n}) \leq 3{n^3}{2^n}. \] This extends some earlier results of \textit{P. Erdős} and \textit{C. C. Rousseau} on bipartite size Ramsey numbers in [Discrete Math. 113, No.\,1--3, 259--262 (1993; Zbl 0778.05059)].
    0 references
    size Ramsey number
    0 references
    bipartite graph
    0 references

    Identifiers