Fox–Grinshpun–Pach conjecture for Gallai–Ramsey numbers of triangles and cliques

Let k3k\geq 3 and p3p\geq 3 be integers. Write r(Kp,Kp)r(K_p,K_p) for the two-color Ramsey number of the complete graph KpK_p, and let grk(K3:Kp)\operatorname{gr}_k(K_3:K_p) denote the Gallai–Ramsey number for a rainbow triangle and a monochromatic KpK_p. (The displayed formula in the source uses nn for the parity condition, although the quantified parameter is kk.)

Fox–Grinshpun–Pach conjecture.

grk(K3:Kp)={(r(Kp,Kp)1)k/2+1,if k is even,(p1)(r(Kp,Kp)1)(k1)/2+1,if k is odd.\operatorname{gr}_k(K_3:K_p)=\left\{\begin{array}{ll}(r(K_p,K_p)-1)^{k/2}+1, & \text{if }k\text{ is even},\\(p-1)(r(K_p,K_p)-1)^{(k-1)/2}+1, & \text{if }k\text{ is odd}.\end{array}\right.

This conjecture gives an exact formula for the Gallai–Ramsey number of a rainbow triangle versus a monochromatic complete graph, refining the preceding asymptotic result. The supplied material gives no evidence of a resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Ping Li, Yaping Mao, Ingo Schiermeyer and Yifan Yao, “Ramsey and Gallai-Ramsey numbers for linear forests and kipas”, arXiv:2401.08942 (2024).

Additional references

11 papers in this index state this conjecture (2017–2024). The statement above is taken from the most recent of them; the others are arXiv:2011.01592, arXiv:1906.05263, arXiv:1905.13564, arXiv:1901.03622, arXiv:1809.00227, arXiv:1808.09963, arXiv:1808.10282, arXiv:1802.04930, arXiv:1802.06503, arXiv:1709.06130.

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.