The complete bipartite graph size Ramsey number conjecture

Let Ks,tK_{s,t} denote the complete bipartite graph with parts of sizes ss and tt, and let hatr(H)hat r(H) denote the size Ramsey number of a graph HH. For functions of the parameters, write f=Θ(g)f=\Theta(g) when they are bounded above and below by positive constant multiples of gg. Complete bipartite size Ramsey conjecture. For all sts\leq t,

hatr(Ks,t)=Θ(s2t2s).hat r(K_{s,t})=\Theta(s^2t2^s).

In particular,

hatr(Kt,t)=Θ(t32t).hat r(K_{t,t})=\Theta(t^3 2^t).

The paper proves this order of magnitude when t=Ω(slogs)t=\Omega(s\log s) and conjectures that it extends to the full range sts\leq t.

Sources & referencesView supporting material

Primary source

David Conlon, Jacob Fox and Yuval Wigderson, “Three early problems on size Ramsey numbers”, arXiv:2111.05420 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.