A new lower bound for the multicolor Ramsey number r_k(K_{2, t + 1})

2024/11/21 by Taranchuk, Vladislav
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2411.14364

Abstract

In this short note, we provide a new infinite family of K_{2, t+1}-free graphs for each prime power t. Using these graphs, we show that it is possible to partition the edges of K_n into parts, such that each part is isomorphic to our K_{2, t+1}-free graph. This yields an improved lower bound to the multicolor Ramsey number r_k(K_{2, t+1}) when k and t are powers of the same prime. For these values of k and t, our coloring implies that tk² + 1 ≤ r_k(K_{2, t+1}) ≤ tk² + k + 2. where the upper bound is due to Chung and Graham.

Related

• An improved lower bound for multicolor Ramsey numbers and the\n half-multiplicity Ramsey number problem
• Improved bounds on the multicolor Ramsey numbers of paths and even cycles
• New bounds for some small multicolor Ramsey numbers
• On the multicolor Ramsey number of a graph with m edges
• Upper bounds for multicolour Ramsey numbers