Pak's conjecture on the size-Ramsey number of long subdivisions

Given a graph HH and a function c3:E(H)Nc3:E(H)\to\mathbb{N}, the subdivision HσH^{\sigma} is obtained by replacing each edge eE(H)e\in E(H) with a path of length σ(e)\sigma(e). For a graph GG and positive integer kk, let R^(G,k)\widehat{R}(G,k) denote its multicolor size-Ramsey number, and let Δ(H)\Delta(H) denote the maximum degree of HH. Pak's conjecture. For every k,DNk,D\in\mathbb{N} there exist C,L>0C,L>0 such that if HH is a graph with Δ(H)D\Delta(H)\leq D and

σ(e)Llog(V(Hσ))\sigma(e)\geq L\log(|V(H^{\sigma})|)

for all eE(H)e\in E(H), then

R^(Hσ,k)CV(Hσ).\widehat{R}(H^{\sigma},k)\leq C|V(H^{\sigma})|.

Pak posed this conjecture for long subdivisions of bounded-degree graphs, where every subdividing path has logarithmic length in the number of vertices. It predicts a linear multicolor size-Ramsey bound; the supplied text gives no information about whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Ramin Javadi, Yoshiharu Kohayakawa and Meysam Miralaei, “The multicolor induced size-Ramsey number of long subdivisions”, arXiv:2602.05960 (2026).

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.