Ramsey number of a cycle versus a graph of a given size

Stijn Cambie, Andrea Freschi, Patryk Morawski, Kalina Petrova, Alexey Pokrovskiy · 2026

Read Ramsey number of a cycle versus a graph of a given size by Stijn Cambie, Andrea Freschi, Patryk Morawski, Kalina Petrova, Alexey Pokrovskiy (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-2601-10238.txt.

Introduction

Stijn Cambie, Andrea Freschi, Patryk Morawski, Kalina Petrova, and Alexey Pokrovskiy bound a Ramsey count. Ramsey counts ask how large a graph must be to force a set shape. Here the shapes are a cycle and a graph of set size. Size is read as the count of edges.

The team prove a clean bound. For each cycle length and each graph with no lone nodes, the count is at most twice the edge count plus half the cycle length. The bound needs the graph to be large next to the cycle. Such bounds pin down how fast forced shapes must show.

Catalog record

CREATORStijn Cambie, Andrea Freschi, Patryk Morawski, Kalina Petrova, Alexey Pokrovskiy
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10238

Browse the full library · About the Tower of Babel

Full text

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

Ramsey number of a cycle versus a graph of a given size Stijn Cambie, Andrea Freschi, Patryk Morawski, Kalina Petrova, Alexey Pokrovskiy Abstract In this paper, we prove that for every k k and every graph H H with m m edges and no isolated vertices, the Ramsey number R ⁡ ( C k , H ) R(C_{k},H) is at most 2 ​ m + ⌊ k − 1 2 ⌋ 2m+\mathopen{}\left\lfloor\frac{k-1}{2}\right\rfloor\mathclose{} , provided m m is sufficiently large with respect to k k . This settles a problem of Erdős, Faudree, Rousseau and Schelp. 1 Introduction For two graphs G and H , the Ramsey number R(G,H) is defined as the smallest N such that in every red-blue colouring of the edges of K_{N} (i.e., the complete graph on N vertices), there is a red copy of G or a blue copy of H . The existence of these numbers was proven by Ramsey [ 17 ] . The first good quantitative bound R(K_{n},K_{n})\leq 4^{n} was later obtained by Erdős and Szekeres [ 8 ] . Obtaining better estimates for R(K_{n},K_{n}) is a central problem in combinatorics, and an upper bound of the form 4^{(1-c)n} for some c>0 has only been obtained recently [ 5 ] . Understanding Ramsey numbers of non-complete graphs is also important. In particular, a substantial part of Ramsey theory research has focused on obtaining upper bounds on R(G,G) in terms of various parameters of G . Note that the number of vertices of G , denoted as |G| , is not a very interesting parameter on its own: since R(G,G)\leq R(K_{|G|},K_{|G|}) for any graph G , proving bounds on R(G,G) which only take |G| into account is equivalent to proving bounds on Ramsey numbers of complete graphs. On the other hand, proving bounds on R(G,G) in terms of the number of edges of G , denoted as e(G) , is a different and very interesting problem. The best known bound here is by Sudakov [ 21 ] who proved that R(G,G)\leq 2^{250\sqrt{e\smash{(G)}}} for any graph G with no isolated vertices, solving a well-known conjecture of Erdős [ 12 ] . Turning to the asymmetric case, researchers have been interested in obtaining bounds on R(G,H) where G is a fixed graph and H varies. In analogy to the previous paragraph, we again want to determine the best general upper bound in terms of e(H) and no other parameters of H . The simplest non-trivial case is when G=K_{3} . This problem was posed by Harary, who conjectured that R(K_{3},H)\leq 2e(H)+1 for any graph H with no isolated vertices; this is tight when H is a tree or a matching. Following weaker upper bounds by Erdős, Faudree, Rosseau, and Schelp [ 9 ] and by Sidorenko [ 19 ] , Harary’s Conjecture was fully proved via two independent proofs by Goddard and Kleitman and by Sidorenko. Theorem 1 (Goddard and Kleitman [ 14 ] ; Sidorenko [ 18 ] ) . For any graph H with no isolated vertices, we have R(K_{3},H)\leq 2e(H)+1 . What about when we replace K_{3} by some other graph G ? In [ 11 ] , Erdős, Faudree, Rosseau, and Schelp initiated a systematic study of this question, proving many bounds and posing many open problems. They specifically introduced the notion of “Ramsey size-linear” graphs, that is, graphs G such that for some constant C_{G}=C_{G}(G) we have R(G,H)\leq C_{G}\cdot e(H) for every graph H with no isolated vertex. They discovered that the average degree of G is largely responsible for it being Ramsey size-linear or not. In particular, they proved that graphs with e(G)\geq 2|G|-2 are not Ramsey size-linear, whereas graphs with e(G)\leq|G|+1 always are. In the intermediate range, both behaviours are possible and determining which graphs are Ramsey size-linear is a difficult problem. The behaviour can be quite complicated — for example Wigderson [ 22 ] showed that there are infinitely many graphs which are not Ramsey size-linear, but each of whose subgraphs is Ramsey size-linear, answering a question of Erdős, Faudree, Rosseau, and Schelp. Even for specific simple G , like subdivisions of K_{4} , we still do not have a full answer [ 1 , 3 ] . For a given Ramsey size-linear graph G , one can go further and ask what the optimal constant C_{G} should be. Generalizing Harary’s original conjecture, Erdős, Faudree, Rosseau, and Schelp posed the following question for the case where G is a cycle C_{k} on k vertices: Question 2 (Erdős, Faudree, Rosseau, and Schelp [ 11 ] ) . For each k , is it true that all graphs H with no isolated vertices and e(H) sufficiently large with respect to k satisfy R(C_{k},H)\leq 2e(H)+\mathopen{}\left\lfloor\frac{k-1}{2}\right\rfloor\mathclose{} ? The upper bound in Question 2 is tight, as seen by taking H to be a matching (i.e., a collection of vertex-disjoint edges) and considering a red-blue colouring of the complete graph on (2e(H)-1)+\mathopen{}\left\lfloor\frac{k-1}{2}\right\rfloor\mathclose{} vertices consisting of a blue clique of order 2e(H)-1 and all other edges red. Question 2 appears as Problem 570 in the database of Erdős problems [ 2 ] , and was also previously listed by Chung and Graham in their book [ 6 ] and as problem 35 in the database of hard graph theory Erdős problems [ 7 ] from 2010. Erdős, Faudree, Rosseau, and Schelp [ 11 ] verified Question 2 when k is even. When k=3 , Question 2 is just Harary’s original conjecture which is true by Theorem 1 . The case k=5 was resolved by Jayawardene [ 16 ] . In this paper, we settle all remaining cases. Theorem 3 . For each odd k\geq 7 , all graphs H with no isolated vertices satisfy R(C_{k},H)\leq 2e(H)+\left\lfloor\frac{k-1}{2}\right\rfloor , provided that e(H) is sufficiently large with respect to k . Like the earlier proofs in this area by Sidorenko, Goddard and Kleitman, Erdős, Faudree, Rosseau and Schelp, and Jayawardene, our proof is an induction. We prove a more general upper bound (Theorem 10 ) that holds for all values of e(H) and equals 2e(H)+\mathopen{}\left\lfloor\frac{k-1}{2}\right\rfloor\mathclose{} for e(H) sufficiently large. The main proof is presented in Section 3 , and depends on multiple preliminary results. The latter are presented in Section 2 . Our core ideas depend on an estimate for R(P_{k},H) (Corollary 7 ), where P_{k} denotes the path on k vertices, and on proving that if either the first or second neighbourhood of a vertex contains a copy of P_{2k} then one can find a copy of C_{k} (Lemma 8 ). Notation and terminology. For a graph G , we write V(G) for the vertex set of G , |G| for the number of vertices in G , and e(G) for the number of edges in G . For a vertex v\in V(G) , we let N_{G}(v) denote the neighbourhood of v in G . For a set S\subseteq V(G) we define the neighbourhood of S to be the set \{u\in V(G)\setminus S:\exists v\in S\text{ with }uv\in E(G)\} . The second neighbourhood of a vertex v\in V(G) is the neighbourhood of N(v) minus v itself. If G is red-blue coloured, we define the (second) red neighbourhood of v\in V(G) to be the (second) neighbourhood in the

Read the complete text