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

At least 3 years old · documented by

Let k,p,t≥2k,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 1≤a1≤⋯≤ap−1≤t1\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 n−kn-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+d−1)(n+d-1)-vertex Ka1,a2K_{a_1,a_2}-free graph in which at most k−1k-1 vertices have degree less than dd. Fox, He and Wigderson's conjecture. For every k,p,t≥2k,p,t\geq 2, there exists δ>0\delta>0 such that for all n≥1n\geq 1, whenever 1≤a1≤⋯≤ap−1≤t1\leq a_1\leq\cdots\leq a_{p-1}\leq t and ap≤δna_p\leq\delta n,

r(Kp(a1,…,ap),Bk,n)=(p−1)(n−1)+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 a1≥2a_1\geq2.

References

Primary source

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

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.