Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Size bipartite Ramsey numbers - MaRDI portal

Size bipartite Ramsey numbers (Q1011777)

From MaRDI portal





scientific article; zbMATH DE number 5542425
Language Label Description Also known as
English
Size bipartite Ramsey numbers
scientific article; zbMATH DE number 5542425

    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
    0 references

    Identifiers