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

Deepak Bal, Patrick Bennett

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume27
Issue number4
DOIs
StatePublished - 2020

Fingerprint

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

Cite this