Diagonal Ramsey numbers for wheels Supported by the National Science Foundation of China (No.12061059)

Maoxuan Li, Masaki Kashima, Yaping Mao · 2026

Read Diagonal Ramsey numbers for wheels Supported by the National Science Foundation of China (No.12061059) by Maoxuan Li, Masaki Kashima, Yaping Mao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22116.txt.

Introduction

Li and co-authors improve bounds on diagonal Ramsey numbers for wheels. R(G1,G2) is the smallest N such that every red-blue coloring of the complete graph on N vertices yields a red G1 or a blue G2. For wheels W_n on n vertices, prior 2022 bounds improve to 3n minus 2 through 6n minus 6 for even n at least 8. For odd n at least 7, bounds become 2n through (9n minus 7) over 2. They also give recursive k-colored Ramsey bounds for wheels.

Catalog record

CREATORMaoxuan Li, Masaki Kashima, Yaping Mao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25191
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.22116

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Diagonal Ramsey numbers for wheels Supported by the National Science Foundation of China (No.12061059) Maoxuan Li, Masaki Kashima, Yaping Mao Abstract The Ramsey number R ⁡ ( G 1 , G 2 ) \mathrm{R}(G_{1},G_{2}) is the smallest integer N N such that any red-blue coloring of the edges of the complete graph K N K_{N} contains either a red copy of G 1 G_{1} or a blue copy of G 2 G_{2} . In 2022, the third author and others gave lower and upper bounds of the Ramsey number R ⁡ ( W n , W n ) \mathrm{R}(W_{n},W_{n}) , where W n W_{n} is the wheel graph with n n vertices. In this paper, we improve their bounds by showing that 3 ​ n − 2 ≤ R ⁡ ( W n , W n ) ≤ 6 ​ n − 6 3n-2\leq\mathrm{R}(W_{n},W_{n})\leq 6n-6 for even n ≥ 8 n\geq 8 and 2 ​ n ≤ R ⁡ ( W n , W n ) ≤ 9 ​ n − 7 2 2n\leq\mathrm{R}(W_{n},W_{n})\leq\frac{9n-7}{2} for odd n ≥ 7 n\geq 7 . Furthermore, we give recursive bounds for the k k -colored Ramsey number for W n W_{n} . Keywords: Ramsey number; Wheel graph; Extremal Combinatorics; AMS subject classification 2020: 05C55; 05C38; 05C15; 05C80 1 Introduction All graphs considered in this paper are finite simple graphs without loops. For a positive integer n , K_{n} denotes the complete graph with n vertices, and C_{n} denotes the cycle of length n . Other basic notation not defined in this paper is based on Bondy and Murty [ 1 ] . Classical Ramsey theory was first introduced by Frank Plumpton Ramsey, a British mathematician. In his posthumous 1930 paper ‘On a Problem of Formal Logic’, he proposed Ramsey’s Theorem as an auxiliary tool to solve a problem in formal logic. Though it was not originally designed for combinatorial research, this theorem later became the cornerstone of classical Ramsey theory. Formally, Ramsey’s Theorem states that for any given positive integer, there exists a minimum positive integer, called the Ramsey number, such that if the subsets of a set with size not less than this minimal integer are partitioned into several classes, at least one class will contain all subsets of a smaller specified substructure. In the setting of graph theory, the Ramsey number for graphs are defined as follows. Definition 1.1 . For two graphs G_{1} and G_{2} , we write F\to(G_{1},G_{2}) if for any two coloring of edges of F in red and blue, either a red copy of G_{1} or a blue copy of G_{2} exists. The Ramsey number for G_{1} and G_{2} , denoted by \mathrm{R}(G_{1},G_{2}) , is defined as \mathrm{R}(G_{1},G_{2})=\min\{N\mid K_{N}\to(G_{1},G_{2})\}. It is well known that \mathrm{R}(K_{3},K_{3})=6 , and the Ramsey number \mathrm{R}(K_{n},K_{n}) for general n has been a main topic in graph Ramsey theory for a long time. In this paper, we focus on the Ramsey number for a wheel graph. For a positive integer n\geq 4 , the wheel graph W_{n} is a graph obtained from the cycle C_{n-1} of length n-1 by adding a new vertex adjacent to every vertex of C_{n-1} . The study of the Ramsey numbers involving wheel graphs has a rich developmental history spanning several decades. Early contributions include Burr and Erdős [ 3 ] , who in 1983 established the exact value \mathrm{R}(K_{3},W_{n})=2n-1 for all n\geq 6 as part of their generalizations of Chvátal’s Ramsey-theoretic results. Prior to that, Harborth and Mengersen [ 12 ] had already proven in 1988/89 that \mathrm{R}(W_{5},W_{5})=15 , a value which Hendry later listed without proof in his 1989 table of the Ramsey numbers for five-vertex graphs [ 13 ] . In 1993, Faudree and McKay [ 8 ] made progress on specific wheel-wheel Ramsey numbers by characterizing all critical colorings (of types 2, 1, and 2) for \mathrm{R}(W_{n},W_{6}) when n=4,5,6 , advancing the understanding of structural properties of critical graphs in this context. Building on Burr and Erdős’ work, Radziszowski and Xia [ 16 ] extended the analysis in 1994 by determining all critical colorings for \mathrm{R}(K_{3},W_{n}) for every n\geq 3 in their study of paths, cycles, and wheels in graphs without antitriangles. A notable milestone in this area is the refutation of an Erdős conjecture (labeled Erdős in Graham, Rothschild, and Spencer’s 1990 monograph [ 10 ] ), which posited that \mathrm{R}(G,G)\geq\mathrm{R}(K_{\chi(G)},K_{\chi(G)}) for any graph G ; this conjecture was disproven by the observation that \mathrm{R}(W_{6},W_{6})=17 , while \mathrm{R}(K_{4},K_{4})=18 and \chi(W_{6})=4 , making W_{6} a counterexample. Other results on the Ramsey number involving wheel graphs are on [ 4 , 18 , 19 , 20 ] . Recently, Mao, Wang, Magnant, and Schiermeyer [ 15 ] provided general lower and upper bounds for diagonal wheel Ramsey numbers in 2022. Theorem 1.1 ( [ 15 ] ) . For any integer n\geq 7 , \begin{cases}3n-3\leq\mathrm{R}(W_{n},W_{n})\leq 8n-10\quad&\text{if }n\text{ is even; and}\\ 2n-2\leq\mathrm{R}(W_{n},W_{n})\leq 6n-8\quad&\text{if }n\text{ is odd.}\\ \end{cases} In this paper, we improve both lower and upper bounds in Theorem 1.1 as follows. Theorem 1.2 . For any integers n\geq 7 , \begin{cases}3n-2\leq\mathrm{R}(W_{n},W_{n})\leq 6n-6\quad&\text{if }n\text{ is even; and}\\ 2n\leq\mathrm{R}(W_{n},W_{n})\leq\frac{9n-7}{2}\quad&\text{if }n\text{ is odd.}\\ \end{cases} As a natural generalization of the Ramsey number for two colors, the k -colored Ramsey number for is defined as follows. Definition 1.2 . For given graphs G_{1},\ldots,G_{k} and a graph F , we write F\to\left(G_{1},\ldots,G_{k}\right) if, no matter how one colors the edges of F with k colors 1,\ldots,k , there exists a monochromatic copy of G_{i} of color i in F , for some 1\leq i\leq k . The k -colored Ramsey number \mathrm{R}\left(G_{1},\ldots,G_{k}\right) is defined as \mathrm{R}\left(G_{1},\ldots,G_{k}\right)=\min\left\{N\mid K_{N}\to\left(G_{1},\ldots,G_{k}\right)\right\}. In particular, when every graph in G_{1},\ldots,G_{k} is isomorphic to a graph G , then we write \mathrm{R}_{k}(G) instead of \mathrm{R}(G_{1},\ldots,G_{k}) . Note that \mathrm{R}_{1}(G)=|V(G)| for any graph G . When G_{1}=\cdots=G_{k}=P_{3} , where P_{3} is a path with three vertices, F\to\left(G_{1},\ldots,G_{k}\right) if and only if F has a proper edge coloring with k colors. Thus, we have the exact value \mathrm{R}_{k}(P_{3})=k in this case. On the other hand, when it comes to other graph G , it is difficult to determine the value of \mathrm{R}_{k}(G) . Indeed, even for the case of G=K_{3} , the asymptotic behavior of \mathrm{R}_{k}(K_{3}) is unknown, while it was shown by Greenwood and Gleason [ 11 ] that \mathrm{R}_{3}(K_{3})=17 and 42\leq\mathrm{R}_{4}(K_{3})\leq 66 . In this paper, we show recursive relations on the k -colored Ramsey number \mathrm{R}_{k}(W_{n}) for wheels that give lower and upper bounds of \mathrm{R}_{k}(W_{n}) . Let K_{4}^{-} denote the graph obtained from K_{4} by deleting one edge. Theorem 1.3 . Let k\geq 2 and n\geq 2 be integers. Then \mathrm{R}_{k}(W_{n})-1\geq\max\{(\mathrm{R}_{k-\ell}(K_{4}^{-})-1)\cdot(\mathrm{R}_{\ell}(W_{n})-1)\mid 1\leq\ell\leq k-1\} for even n , and \mathrm{R}_{k}(W_{n})-1\geq\max\{(\mathrm{R}_{k-\ell}(K_{3})-1)\cdot(\mathrm{R}_{\ell}(W_{n})-1)\mid 1\leq\ell\leq k-1\} for odd n . By Theorems 1.2 and 1.3 , we have the following lower bound of \mathrm{R}_{k}(W_{n}) . Corollary 1.4 . For positive integers k\geq 2 and n\geq 4 , \begin{cases}\mathrm{R}_{k}(W_{n})\geq 3^{k-1}(n-1)+1\quad&\text{if }n\text{ is even; and}\\ \mathrm{R}_{k}(W_{n})\geq 2^{k-2}(2n-1)+1\quad&\text{if }n\text{ is odd.}\end{cases} Proof. The proof goes by induction on k . When k=2 , we have \mathrm{R}_{2}(W_{n})\geq 3n-2 for even n and \mathrm{R}_{2}(W_{n})\geq 2n for odd n by Theorem 1.2 . Suppose that the statement holds for k-1 . Since \mathrm{R}_{1}(K_{4}^{-})=4 and \mathrm{R}_{1}(K_{3})=3 ,

Read the complete text