An exact Ramsey number of large bipartite graphs versus odd wheel

Sayan Gupta, Kaushik Majumder · 2025

Read An exact Ramsey number of large bipartite graphs versus odd wheel by Sayan Gupta, Kaushik Majumder (2025) 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-2511-14867.txt.

Introduction

Sayan Gupta and Kaushik Majumder pin down an exact Ramsey number for a pair of large graphs. Ramsey numbers mark the point where any red-blue coloring of connections must contain a chosen pattern in one color. They study a bipartite graph with two hubs joined to many leaves, set against an odd wheel, a ring with a center point.

For all large enough sizes in the stated range, the Ramsey number comes out to a clean formula, three times the leaf count plus four. The proof mixes chance-based methods with a structural analysis of tightly linked neighborhoods. The result also shows the bipartite graph is well behaved, in the technical sense, against every odd wheel.

Catalog record

CREATORSayan Gupta, Kaushik Majumder
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14867

Browse the full library · About the Tower of Babel

Full text

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

An exact Ramsey number of large bipartite graphs versus odd wheel Sayan Gupta, Kaushik Majumder Abstract . The Ramsey number for the pair of graphs 𝕂 1 , n \mathbb{K}_{1,n} (star) versus W m W_{m} (wheel) has been extensively studied. In contrast, the Ramsey number of 𝕂 2 , n \mathbb{K}_{2,n} versus wheel is not yet explored due to the structural complexity of 𝕂 2 , n \mathbb{K}_{2,n} . In this article, we have established an exact value of 𝕂 2 , n \mathbb{K}_{2,n} versus W m W_{m} for large n n and m m . In particular, we have proved R ⁡ ( 𝕂 2 , n , W m ) = 3 ​ n + 4 R(\mathbb{K}_{2,n},W_{m})=3n+4 if n n and m m are sufficiently large integers where n ≥ 4 ​ m n\geq 4m and m m is an odd integer. This also proves the W m W_{m} -goodness of 𝕂 2 , n \mathbb{K}_{2,n} . We have used a probabilistic method composed of structural analysis in our proof. 2020 Mathematics Subject Classification Primary: 05C55, 05D10, 05D40. Secondary: 05C35. 1. Introduction Let G and H be two graphs. The Ramsey number R(G,H) is the minimum positive integer N such that for each graph \Gamma on N vertices either \Gamma contains a copy of G or its complement \overline{\Gamma} contains a copy of H (i.e. \textup{copy}(H) is a subgraph of \overline{\Gamma} ). For a vertex v in G , we denote the set of neighbours of v in G as N_{G}(v) and its size |N_{G}(v)| is called degree with textbook notation \deg_{G}(v) . In the case of a bipartite graph G with bipartition A\sqcup B , if v\in A , then we simply denote the neighbours of it by N_{B}(v) as it does not contain any neighbour in A . A graph is k -connected if the deletion of any set of vertices with size less than k does not make the graph disconnected. The minimum number of vertices needed to delete to make G disconnected is called the connectivity of the graph. We denote it by \mathop{k}(G) . The maximum and minimum degrees of a graph G are denoted by \Delta(G) and \delta(G) , respectively. For a graph G , suppose its vertex set V decomposed into two sets P\sqcup Q , such that \frac{|P|}{|V|} is sufficiently small enough, in the sense that if |V|\rightarrow\infty , then \frac{|P|}{|V|}\rightarrow 0 . In this setting, we may regard Q forms a dense or good set in V , while P behaves like a null or bad set. The presence of a bad set P complicates the analysis of the dependency tree. However, the dominant contribution comes from the dense set Q , which plays a central role in analysis. In this article, we have observed such decomposition in our proof. All the graphs we consider throughout this article are simple and undirected. Burr proved a general lower bound on the Ramsey number for the pair of graphs (G,H) . His statement is the following:- Theorem 1.1 . [ 5 , Theorem 1] Let G be a connected graph and H be a graph satisfying |V(G)|\geq\sigma(H) where \sigma(H) is the size of the smallest colour class in a \chi(H) -colouring of H . Then R(G,H)\geq(|V(G)|-1)(\chi(H)-1)+\sigma(H). We say that a graph G is H -good if equality holds in Burr’s lower bound for the pair (G,H) . This notion of goodness, introduced by Burr and Erdős in [ 6 ] , plays a central role in the study of Ramsey goodness. Roughly speaking, it identifies those pairs of graphs (G,H) for which Burr’s standard lower bound is in fact tight. The study of Ramsey goodness has attracted significant attention, particularly in cases where H has a bounded chromatic number. Indeed, when H is a cycle or a tree graph, its chromatic number satisfies \chi(H)\in\{2,3\} , values that do not depend on |V(H)| . In such situations, R(G,H) grows linearly with |V(G)| . More generally, whenever H has a chromatic number \chi(H) that is independent of |V(H)| , the lower bound of Ramsey number R(G,H) remains linear in |V(G)| . Although it may still depend on the parameter \sigma(H) . If both \chi(H) and \sigma(H) are independent of |V(H)| , then the growth of R(G,H) is at least linear in |V(G)| . On the other hand, if \chi(H) is independent of |V(H)| but \sigma(H) depends on |V(H)| , then R(G,H) still grows at least linearly with |V(G)| , and the equality case becomes particularly rich and tractable. Concluding that R(G,H) is linear in |V(G)| requires establishing an upper bound of the same order. Our statement (Theorem 1.5 ) shows that R(\mathbb{K}_{2,n},W_{m}) , grows linearly with |V(\mathbb{K}_{2,n})|=n+2 with explicit parametric dependence on n and m . In fact, Theorem 1.5 further establishes that \mathbb{K}_{2,n} is W_{m}- good, again with explicit dependence on n and m . Determining which graphs are H- good for various families of graphs H , and understanding the structural reasons behind goodness, remains one of the central and challenging problems in graph Ramsey theory. Over the past several decades, substantial progress has been made for trees, cycles, and various sparse or nearly bipartite graphs; see, for example, [ 1 , 8 , 13 , 14 , 12 ] . A well-studied example in the literature on Ramsey goodness is the pair (\mathbb{K}_{1,n},W_{m}) , where \mathbb{K}_{1,n} denotes the star graph and W_{m} is the wheel graph on m+1 vertices. The formal definition of the wheel graph W_{m} on m+1 vertices is the graph \mathbb{K}_{1}\circledast C_{m} . Here, the notation \circledast indicates the join of two graphs, that is \mathbb{K}_{1} is adjacent to all vertices of the cycle graph C_{m} . Recall that for each integer m , \chi(W_{m})\in\{3,4\} and \sigma(W_{m})=1 . The general Ramsey number for the pair (\mathbb{K}_{1,n},W_{m}) in the case of odd wheels was first determined in [ 7 ] for n\geq m-1 , establishing that \mathbb{K}_{1,n} is W_{m} -good in this range. This bound was later improved to n\geq\frac{m+1}{2} in [ 3 ] . For further results on star–wheel Ramsey numbers, see [ 11 ] . Theorem 1.2 . [ 7 , Theorem 2] If n\geq m-1 and m\geq 3 is an odd integer, then R(\mathbb{K}_{1,n},W_{m})=3n+1. A book graph \mathbb{K}_{2}\circledast\overline{\mathbb{K}_{n}} contains n+2 vertices and 2n+1 many edges, i.e., n triangles sharing a common edge. It is denoted by B_{n} . The exact value of the book-wheel Ramsey number is the following. Theorem 1.3 . [ 16 , Theorem 1] If m\geq 5n+3 and n\geq 1 , then R(W_{m},B_{n})=2m+1. This result proves that W_{m} is B_{n} -good. The motivating observation is that the graph \mathbb{K}_{2,n} is sandwiched between the star and book graphs. In particular, \mathbb{K}_{1,n}\subset\mathbb{K}_{2,n}\subset B_{n}. Here, H\subset G means a copy of the graph H is contained in G as a subgraph. A graph G is \mathbb{K}_{1,n} -free if and only if the maximum degree \Delta(G)\leq n-1 . As a consequence, we get a lower bound on the minimum degree of \overline{G} . This helps to identify the embedding of particular structures inside \overline{G} . Whereas in the case of \mathbb{K}_{2,n} , we do not have that particular advantage due to its structural complexity and dependency.

Read the complete text