Fox, He and Wigderson's Ramsey goodness conjecture for complete multipartite graphs and books

From papers

Let k,p,t2k,p,t\geq 2 be integers. For a complete pp-partite graph H=Kp(a1,,ap)H=K_p(a_1,\dots,a_p) with 1a1ap1t1\leq a_1\leq\cdots\leq a_{p-1}\leq t and apδna_p\leq\delta n, let Bk,nB_{k,n} be the book graph on nn vertices consisting of nkn-k copies of Kk+1K_{k+1} sharing a common KkK_k. Define dk(n,Ka1,a2)d_k(n,K_{a_1,a_2}) as the maximum dd for which there is an (n+d1)(n+d-1)-vertex Ka1,a2K_{a_1,a_2}-free graph in which at most k1k-1 vertices have degree less than dd. Fox, He and Wigderson's conjecture. For every k,p,t2k,p,t\geq 2, there exists δ>0\delta>0 such that for all n1n\geq 1, whenever 1a1ap1t1\leq a_1\leq\cdots\leq a_{p-1}\leq t and apδna_p\leq\delta n,

r(Kp(a1,,ap),Bk,n)=(p1)(n1)+dk(n,Ka1,a2)+1.r(K_p(a_1,\dots,a_p),B_{k,n})=(p-1)(n-1)+d_k(n,K_{a_1,a_2})+1.

This extends known Ramsey-goodness results for books without using the regularity lemma; the conjecture is stated as open in the source, although the paper notes that it fails in many cases and remains open for a12a_1\geq2.

Progress summary

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

Sources & referencesView supporting material

Primary source

Chunchao Fan and Qizhong Lin, “Ramsey non-goodness involving books”, arXiv:2204.03462 (2022).

Solutions 0

No solutions have been posted yet.