The bipartite Ramsey number $b(s,t)$ is the smallest integer $n$ such that every blue-red edge coloring of $K_{n,n}$ contains either a blue $K_{s,s}$ or a red $K_{t,t}$. In the bipartite $K_{2,2}$-free process, we begin with an empty graph on vertex set $X\cup Y$, $|X|=|Y|=n$. At each step, a random edge from $X\times Y$ is added under the restriction that no $K_{2,2}$ is formed. This step is repeated until no more edges can be added. In this note, we analyze this process and prove that the resulting graph shows that $b(2,t) =\Omega(t^{3/2}/\log t)$, thereby improving the best known lower bound.
@article{10_37236_9101,
author = {Deepak Bal and Patrick Bennett},
title = {The bipartite {\(K_{2,2}\)-free} process and bipartite {Ramsey} number \(b(2, t)\)},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9101},
zbl = {1451.05151},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9101/}
}
TY - JOUR
AU - Deepak Bal
AU - Patrick Bennett
TI - The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9101/
DO - 10.37236/9101
ID - 10_37236_9101
ER -
%0 Journal Article
%A Deepak Bal
%A Patrick Bennett
%T The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9101/
%R 10.37236/9101
%F 10_37236_9101
Deepak Bal; Patrick Bennett. The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\). The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9101
