The threshold for the asymmetric vertex-Ramsey property in randomly perturbed graphs

Asier Calbet, Victor Falgas-Ravry, Joseph Hyde · 2026

Read The threshold for the asymmetric vertex-Ramsey property in randomly perturbed graphs by Asier Calbet, Victor Falgas-Ravry, Joseph Hyde (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-2606-30548.txt.

Introduction

Asier Calbet, Victor Falgas-Ravry and Joseph Hyde settle a threshold question in graph theory, the mathematics of networks, in a 2026 paper. A graph has the vertex-Ramsey property when any colouring of its vertices with a fixed set of colours forces a copy of a target graph in its assigned colour. Earlier work found the threshold for random graphs, and a later team studied dense graphs topped up with random edges for two target graphs.

Calbet and his co-authors resolve the perturbed setting in full generality. For any number of colours, at least two, and any matching list of target graphs, they determine how many random edges a dense graph needs. Past that number, the combined graph has the vertex-Ramsey property with probability approaching certainty. Their result extends the earlier two-graph problem posed by Das, Morris and Treglown to every tuple of targets at once.

Catalog record

CREATORAsier Calbet, Victor Falgas-Ravry, Joseph Hyde
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

The threshold for the asymmetric vertex-Ramsey property in randomly perturbed graphs Asier Calbet, Victor Falgas-Ravry, Joseph Hyde Abstract For r ≥ 2 r\geq 2 and graphs H 1 , … , H r , G H_{1},\ldots,H_{r},G , we say that G G is ( H 1 , … , H r ) (H_{1},\ldots,H_{r}) vertex-Ramsey, or ( H 1 , … , H r ) v (H_{1},\ldots,H_{r})_{v} -Ramsey, if whenever we colour the vertices of G G with colours from the set [ r ] = { 1 , 2 , … , r } [r]=\{1,2,\ldots,r\} there exists j ∈ [ r ] j\in[r] such that some copy of H j H_{j} in G G is monochromatic in colour j j . Given any fixed collection of graphs H 1 , … , H r H_{1},\ldots,H_{r} , Łuczak, Ruciński and Voigt [ 22 ] and Kreuter [ 13 ] determined in the 1990s the threshold edge probability p p at which the binomial random graph G ⁡ ( n , p ) G(n,p) becomes ( H 1 , … , H r ) v (H_{1},\ldots,H_{r})_{v} -Ramsey. More recently, Das, Morris and Treglown [ 6 ] investigated the vertex-Ramsey property in the randomly perturbed setting. When r = 2 r=2 they determined the number of random edges one must add to a dense graph to ensure that with probability 1 − o ⁡ ( 1 ) 1-o(1) the resulting graph is ( H 1 , H 2 ) v (H_{1},H_{2})_{v} -Ramsey whenever one of H 1 H_{1} or H 2 H_{2} is a clique. They posed the problem of extending their results to all pairs of graphs ( H 1 , H 2 ) (H_{1},H_{2}) . In this paper we resolve a more general form of their problem and determine for any r ≥ 2 r\geq 2 and r r -tuple of graphs ( H 1 , … , H r ) (H_{1},\ldots,H_{r}) the number of random edges one must add to a dense graph to ensure that with probability 1 − o ⁡ ( 1 ) 1-o(1) the resulting graph is ( H 1 , … , H r ) v (H_{1},\ldots,H_{r})_{v} -Ramsey. 1 Introduction Given r\geq 2 and graphs H_{1},\ldots,H_{r},G , we say that G is (H_{1},\ldots,H_{r}) vertex-Ramsey , or that G is (H_{1},\ldots,H_{r})_{v} -Ramsey , if whenever we colour the vertices of G with colours from the set [r]:=\{1,2,\ldots,r\} there exists some j\in[r] such that some copy of H_{j} in G is monochromatic in colour j . We denote this property by G\rightarrow(H_{1},\ldots,H_{r})_{v} . In the special case when H_{1}=\cdots=H_{r}=H we write this more compactly as G\rightarrow(H,r)_{v} and say ‘ G is (H,r)_{v} -Ramsey’. In the classical setting, the vertex-Ramsey problem is fairly uninteresting compared with its edge counterpart. Indeed, denoting by v(G) the order of a graph G and by K_{n} the complete graph of order n , it is easy to see for any r\geq 2 and graphs H_{1},\ldots,H_{r} that K_{n}\rightarrow(H_{1},\ldots,H_{r})_{v} if and only if n\geq v(H_{1})+\cdots+v(H_{r})-(r-1) . More generally for dense but non-complete graphs, writing e(G) for the number of edges in a graph G , we have the following. We say a graph is non-empty is it contains at least one edge. Observation 1.1 . Let r\geq 2 and H_{1},\ldots,H_{r} be non-empty graphs. There exists a graph G^{\star} with e(G^{\star})\leq\left(1-\frac{1}{\sum_{j=1}^{r}(\chi(H_{j})-1)}\right)\left(\binom{v(G^{\star})}{2}+\frac{v(G^{\star})}{2}\right) such that G^{\star}\not\rightarrow(H_{1},\ldots,H_{r})_{v} . On the other hand, for any fixed \varepsilon>0 there exists n_{0}\in\mathbb{N} such that any graph G with v(G)\geq n_{0} and e(G)\geq\left(1-\frac{1}{\sum_{j=1}^{r}(\chi(H_{j})-1)}+\varepsilon\right)\binom{v(G)}{2} satisfies G\rightarrow(H_{1},\ldots,H_{r})_{v} . Proof. For the first part, consider a complete balanced \sum_{j=1}^{r}(\chi(H_{j})-1) -partite graph G^{\star} . This graph has e(G^{\star})\leq\left(1-\frac{1}{\sum_{j=1}^{r}(\chi(H_{j})-1)}\right)\frac{v(G^{\star})^{2}}{2} edges. For each colour j\in[r] , select a set of \chi(H_{j})-1 parts of G and colour every vertex within them in colour j . This clearly yields an r -colouring of the vertices of G^{\star} containing no monochromatic copy of H_{j} in colour j for any j\in[r] . The second part of the observation follows from the famous Erdős–Stone–Simonovits [ 8 , 9 ] theorem. Indeed, let H^{*} be the complete \left(1+\sum_{j=1}^{r}(\chi(H_{j})-1)\right) -partite graph with all part sizes equal to \left(1+\sum_{j=1}^{r}(v(H_{j})-1)\right) . Observe that H^{*}\to(H_{1},\ldots,H_{r})_{v} : by the pigeon-hole principle, for every part in H^{\star} , there is at least one colour i such that at least v(H_{i}) vertices in that part are in colour i . By the pigeonhole principle again, there is some colour j for which i=j for at least (\chi(H_{i})=)\ \chi(H_{j}) different parts, yielding a monochromatic copy of H_{j} in colour j . Now for any \varepsilon>0 , the Erdős–Stone–Simonovits theorem [ 8 , 9 ] implies that there exists n_{0}\in\mathbb{N} such that for any graph G with v(G)\geq n_{0} with e(G)\geq\left(1-\frac{1}{\sum_{j=1}^{r}(\chi(H_{j})-1)}+\varepsilon\right)\binom{v(G)}{2} , we have H^{*}\subseteq G . Any such graph G is thus (H_{1},\ldots,H_{r})_{v} -Ramsey. ∎ The graph G^{\star} constructed in Observation 1.1 is both dense and highly structured. It is thus natural to ask about the vertex-Ramsey properties of host graphs G with more uniform edge distribution. In this vein, Łuczak, Ruciński and Voigt [ 22 ] initiated the study of vertex-Ramsey properties of random graphs. The model of random graphs considered here is the Erdős-Rényi binomial random graph model G(n,p) with n vertices and each edge included independently with probability p=p(n) . To state Łuczak, Ruciński and Voigt’s main result, we must first introduce a key graph parameter. Definition 1.2 . Given a graph H , we define the 1-density of H to be m_{1}(H):=\max\left\{\frac{e(J)}{v(J)-1}:J\subseteq H,v(J)\geq 2\right\}, setting m_{1}(H)=0 when v(H)\leq 1 . Note that throughout this paper, we follow the convention of setting n^{-1/0}:=0 . Theorem 1.3 (Łuczak, Ruciński and Voigt [ 22 ] ) . For r\geq 2 and any graph H with e(H)\geq 1 , excluding the case when r=2 and H is a matching, the following holds: there exist constants c,C>0 such that \lim_{n\to\infty}\mathbb{P}[G(n,p)\to(H,r)_{v}]=\begin{cases}1&\mbox{if}\ p>Cn^{-\frac{1}{m_{1}(H)}}\\ 0&\mbox{if}\ p<cn^{-\frac{1}{m_{1}(H)}}.\end{cases} We refer to the statements in the cases \lim_{n\to\infty}\mathbb{P}[G(n,p)\to(H,r)_{v}]=1 and \lim_{n\to\infty}\mathbb{P}[G(n,p)\to(H,r)_{v}]=0 in such results as the 1-statement and the 0-statement , respectively. When H is a matching, for any constant c>0 we have that many vertex disjoint copies of K_{3} appear in G(n,p) with probability at least some constant c^{\prime}=c^{\prime}(c)>0 whenever p\geq cn^{-1}=cn^{-1/m_{1}(H)} . Observe that K_{3}\rightarrow(K_{2},K_{2})_{v} . Hence, we require p=o(n^{-1/m_{1}(H)}) rather than p\leq cn^{-1/m_{1}(H)} for the 0 -statement when H is a matching. Kreuter [ 13 , Theorem 2] proved an asymmetric generalization of Theorem 1.3 . To state Kreuter’s result, we must introduce another graph parameter, refining the notion of 1-density. Definition 1.4 (Kreuter threshold) . Given any two graphs H_{1} and H_{2} with m_{1}(H_{1})\geq m_{1}(H_{2}) , we define the mixed 1-density of H_{2} and H_{1} (or Kreuter threshold of H_{2} and H_{1} ) to be m_{1}(H_{2},H_{1}):=\max\left\{\frac{m_{1}(H_{2})+e(J)}{v(J)}:J\subseteq H_{1}\right\}, setting m_{1}(H_{2},H_{1})=0 if v(H_{1})=0 . The following facts, which can be proved by elementary algebra, illustrate the relationship between 1-density and mixed 1-density. Fact 1.5 . For all pairs of graphs H_{1} and H_{2} with m_{1}(H_{1})\geq m_{1}(H_{2}) , the mixed 1 -density of H_{2} and H_{1} lies between the 1-densities of the corresponding graphs: m_{1}(H_{1})\geq m_{1}(H_{2},H_{1})\geq m_{1}(H_{2}) . Furthermore, m_{1}(H_{1})>m_{1}(H_{2},H_{1})>m_{1}(H_{2}) if and only if m_{1}(H_{1})>m_{1}(H_{2}) , and if for some graph H_{3} we have m_{1}(H_{2})=m_{1}(H_{3})\leq m_{1}(H_{1}) then m_{1}(H_{2},H_{1})=m_{1}(H_{3},H_{1}) . Theorem 1.6 (Kreuter [ 13 ] ) . For r\geq 2

Read the complete text