TY - JOUR
T1 - The bipartite k2,2-free process and bipartite ramsey number b(2, t)
AU - Bal, Deepak
AU - Bennett, Patrick
N1 - Publisher Copyright:
© The authors.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020
Y1 - 2020
N2 - The bipartite Ramsey number b(s, t) is the smallest integer n such that every blue-red edge coloring of Kn,n contains either a blue Ks,s or a red Kt,t . In the bipartite K2,2-free process, we begin with an empty graph on vertex set X ∪ Y, |X| = |Y | = n. At each step, a random edge from X × Y is added under the restriction that no K2,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) = Ω(t3/2/ log t), thereby improving the best known lower bound.
AB - The bipartite Ramsey number b(s, t) is the smallest integer n such that every blue-red edge coloring of Kn,n contains either a blue Ks,s or a red Kt,t . In the bipartite K2,2-free process, we begin with an empty graph on vertex set X ∪ Y, |X| = |Y | = n. At each step, a random edge from X × Y is added under the restriction that no K2,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) = Ω(t3/2/ log t), thereby improving the best known lower bound.
UR - http://www.scopus.com/inward/record.url?scp=85095422640&partnerID=8YFLogxK
U2 - 10.37236/9101
DO - 10.37236/9101
M3 - Article
AN - SCOPUS:85095422640
SN - 1077-8926
VL - 27
SP - 1
EP - 13
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 4
M1 - P4.23
ER -