Asymmetric Ramsey numbers of trees
Jun Yan · 2025
Read Asymmetric Ramsey numbers of trees by Jun Yan (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-15673.txt.
Introduction
Jun Yan finds exact Ramsey numbers for many pairs of trees. A Ramsey number is the smallest size at which any two-coloring of a complete graph must contain a copy of one tree in the first color. It can also contain the other tree in the second color instead. Trees differ in size, in how their vertices split between the two sides of their split, and in their largest vertex degree.
Yan first builds four natural constructions that give a lower bound formula. The main result shows that bound is exact for all large trees. That holds when degrees stay modest and two size conditions between the splits hold. Examples show each of the three conditions is needed, since dropping any one lets the true number exceed the formula.
Catalog record
| CREATOR | Jun Yan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 171 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-15673
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymmetric Ramsey numbers of trees Jun Yan Abstract Let n ≥ ν n\geq\nu , let T T be an n n -vertex tree with bipartition class sizes t 1 ≥ t 2 t_{1}\geq t_{2} , and let S S be a ν \nu -vertex tree with bipartition class sizes s 1 ≥ s 2 s_{1}\geq s_{2} . Using four natural constructions, we show that the Ramsey number R ( T , S ) R(T,S) is lower bounded by R ¯ ( T , S ) = max { n + s 2 , ν + min { t 2 , ν } , min { 2 t 1 , 2 ν } , 2 s 1 } − 1 \underline{R}(T,S)=\max\{n+s_{2},\nu+\min\{t_{2},\nu\},\min\{2t_{1},2\nu\},2s_{1}\}-1 . Our main result shows that there exists a constant c > 0 c>0 , such that for all sufficiently large integers n ≥ ν n\geq\nu , if (i) Δ ( T ) ≤ c n / log n \Delta(T)\leq cn/\log n and Δ ( S ) ≤ c ν / log ν \Delta(S)\leq c\nu/\log\nu , (ii) s 2 ≥ t 2 s_{2}\geq t_{2} , and (iii) ν ≥ t 1 \nu\geq t_{1} , then R ( T , S ) = R ¯ ( T , S ) R(T,S)=\underline{R}(T,S) . In particular, this determines the exact Ramsey numbers for a large family of pairs of trees. We also provide examples showing that R ( T , S ) R(T,S) can exceed R ¯ ( T , S ) \underline{R}(T,S) if any one of the three assumptions (i), (ii), and (iii) is removed. 1 Introduction The Ramsey number of two graphs G_{1} and G_{2} , denoted by R(G_{1},G_{2}) , is the smallest positive integer N such that every red/blue edge colouring of the N -vertex complete graph K_{N} contains either a red copy of G_{1} or a blue copy of G_{2} . For brevity, R(G) is used to denote R(G,G) . The existence of R(G_{1},G_{2}) follows from the foundational result of Ramsey [ 15 ] in 1930, but determining the exact value of R(G_{1},G_{2}) , or even just providing good bounds, has since proved extremely challenging. To muster any hope of determining R(G_{1},G_{2}) exactly, usually at least one of G_{1} and G_{2} needs to be sparse, with some natural candidates being trees and cycles. Denote the n -vertex path by P_{n-1} . Gerencsér and Gyárfás [ 5 ] proved in 1967 that for all n\geq m\geq 2 , R(P_{n-1},P_{m-1})=n+\left\lfloor m/2\right\rfloor-1 . For stars, it was determined by Burr and Roberts [ 2 ] in 1973 that R(K_{1,n-1},K_{1,m-1})=m+n-3 if m and n are both even, and R(K_{1,n-1},K_{1,m-1})=m+n-2 otherwise. For cycles, Faudree and Schelp [ 4 ] and Rosta [ 16 ] independently proved in the early 1970s that, aside from a few small exceptions, for all n\geq m , R(C_{n},C_{m})=2n-1 if m is odd, R(C_{n},C_{m})=n+m/2-1 if both n and m are even, and R(C_{n},C_{m})=\max\{n+m/2-1,2m-1\} if n is odd and m is even. In this paper, we consider the Ramsey number R(T,S) of two general trees T and S . Even in the symmetric case when T=S , the exact value of R(T) is only known for a few very specific families of trees until very recently. There is, however, a general lower bound given by Burr [ 3 ] in 1974. Let the bipartition class sizes of T be t_{1}\geq t_{2}\geq 2 , and consider the following red/blue colourings of the complete graph G on N vertices. A1 N=t_{1}+2t_{2}-2 , G consists of two disjoint red cliques A and B of sizes t_{1}+t_{2}-1 and t_{2}-1 , respectively, with all edges between them blue. A2 N=2t_{1}-2 , G consists of two disjoint red cliques A and B both of size t_{1}-1 , with all edges between them blue. The constructions in both A1 and A2 contain no red copy of T , as the red connected components all have sizes smaller than |T| . The graph in A1 contains no blue copy of T as B is not large enough to accommodate the smaller bipartition class of T , while the graph in A2 contains no blue copy of T as neither A nor B is large enough to accommodate the larger bipartition class of T . Together, these two examples give the general lower bound R(T)\geq\max\{t_{1}+2t_{2},2t_{1}\}-1. ( \dagger ) Burr conjectured [ 3 ] that this bound is tight for every tree T with t_{1}\geq t_{2}\geq 2 . However, this was disproved in 1979 by Grossman, Harary, and Klawe [ 6 ] for certain trees called double stars . For any t_{1}\geq t_{2}\geq 2 , let D_{t_{1},t_{2}} be the tree formed by joining the central vertices of the stars K_{1,t_{1}-1} and K_{1,t_{2}-1} with an edge, noting that D_{t_{1},t_{2}} has bipartition class sizes t_{1} and t_{2} . Grossman, Harary, and Klawe [ 6 ] showed that if t_{1}\geq 3t_{2}-2\geq 10 , then R(D_{t_{1},t_{2}})=2t_{1} , and thus the bound ( † ‣ 1 ) can be off by 1. Burr’s conjecture was much more strongly disproved in 2016 by Norin, Sun, and Zhao [ 14 ] , who showed in particular that R(D_{2t,t})\geq(4.2-o(1))t , and therefore the bound ( † ‣ 1 ) can be off by a multiplicative factor. However, all known counterexamples to Burr’s conjecture have large maximum degrees, so perhaps it could be salvaged by imposing a suitable maximum degree condition on T . Towards this, Haxell, Łuczak, and Tingley [ 8 ] showed in 2002 that the bound ( † ‣ 1 ) is approximately tight for trees with up to small linear maximum degrees. More precisely, they showed that for every \mu>0 , there exists some c>0 , such that any n -vertex tree T with maximum degree \Delta(T)\leq cn and bipartition class sizes t_{1}\geq t_{2} satisfies R(T)\leq(1+\mu)\max\{t_{1}+2t_{2},2t_{1}\} . In a recent breakthrough, Montgomery, Pavez-Signé, and Yan [ 13 ] showed that Burr’s conjecture is true, given a suitable linear maximum degree condition. In particular, this result determines the exact Ramsey numbers of a large family of trees. Theorem 1.1 ( [ 13 , Theorem 1.1] ) . There exists a constant c>0 such that the following holds. Any n -vertex tree T with \Delta(T)\leq cn and bipartition classes of sizes t_{1}\geq t_{2} satisfies R(T)=\max\{2t_{1},t_{1}+2t_{2}\}-1. In this paper, building on ideas in [ 8 ] and [ 13 ] , we prove an asymmetric version of Theorem 1.1 , which determines the exact Ramsey numbers R(T,S) for a large family of pairs of trees (T,S) . Let T be an n -vertex tree with bipartition class sizes t_{1}\geq t_{2} . Let S be a \nu -vertex tree with bipartition class sizes s_{1}\geq s_{2} . Without loss of generality, assume that n\geq\nu . Motivated by Burr’s constructions A1 and A2 in [ 3 ] that lead to the general lower bound ( † ‣ 1 ), we now provide a general lower bound for R(T,S) by considering the following red/blue coloured complete graphs G on N vertices that contain neither a red copy of T nor a blue copy of S (see Figure 1 ). B1 N=n+s_{2}-2 , G consists of