The bipartite k2,2-free process and bipartite ramsey number b(2, t)

Deepak Bal, Patrick Bennett

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article numberP4.23
Pages (from-to)1-13
Number of pages13
JournalElectronic Journal of Combinatorics
Issue number4
StatePublished - 2020


Dive into the research topics of 'The bipartite k<sub>2,2</sub>-free process and bipartite ramsey number b(2, t)'. Together they form a unique fingerprint.

Cite this