Ramsey properties for tilings in random graphs
Lucas Aragão and Xinbu Cheng and Rafael Filipe and Rafael Miyazaki and Danni Peng and Zhifei Yan · 2026
Read Ramsey properties for tilings in random graphs by Lucas Aragão and Xinbu Cheng and Rafael Filipe and Rafael Miyazaki and Danni Peng and Zhifei Yan (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-21471.txt.
Introduction
Lucas Aragão and co-authors prove Ramsey properties for tilings in random graphs, generalizing Burr et al. In 1975, Burr et al. showed that a graph on k vertices with independence number alpha yields many disjoint monochromatic copies under two-coloring. In the 1990s, Rödl and Ruciński proved that for most graphs, the random-graph threshold is n to the minus one over m-two. The authors prove the tiling threshold is n to the minus one over the max of m-two and one.
Catalog record
| CREATOR | Lucas Aragão and Xinbu Cheng and Rafael Filipe and Rafael Miyazaki and Danni Peng and Zhifei Yan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65501 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21471
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ramsey properties for tilings in random graphs Thanks: During this work, Xinbu Cheng was supported by CAPES, Rafael Filipe and Danni Peng were supported by CNPq, and Zhifei Yan was supported by the Institute for Basic Science (IBS-R029-C4) Lucas Aragão and Xinbu Cheng and Rafael Filipe and Rafael Miyazaki and Danni Peng and Zhifei Yan Abstract . Let m H mH be the graph formed by m m vertex-disjoint copies of a graph H H . Let G → ( H ) r G\rightarrow(H)_{r} denote that, in any r r -colouring of the edges of G G , there exists a monochromatic copy of H H . In 1975, Burr, Erdős, and Spencer showed that if H H is a graph on k k vertices whose independence number is α \alpha , then K n → ( m H ) 2 K_{n}\rightarrow(mH)_{2} , where m ∼ n / ( 2 k − α ) m\sim n/(2k-\alpha) , and that the 1 / ( 2 k − α ) 1/(2k-\alpha) factor is best possible. In the 1990s, Rödl and Ruciński proved that, for all but a few graphs H H , the threshold for the property 𝔾 ( n , p ) → ( H ) r \mathbb{G}(n,p)\rightarrow(H)_{r} is n − 1 / m 2 ( H ) n^{-1/m_{2}(H)} . In this paper, generalizing the result of Burr, Erdős, and Spencer, we prove that n − 1 / max { m 2 ( H ) , 1 } n^{-1/\max\{m_{2}(H),1\}} is the threshold for the property 𝔾 ( n , p ) → ( m H ) 2 \mathbb{G}(n,p)\rightarrow(mH)_{2} , where m ∼ n / ( 2 k − α ) m\sim n/(2k-\alpha) . This threshold matches the one found by Rödl and Ruciński for most graphs H H , extending their result in the case r = 2 r=2 . 1. Introduction Ramsey theory is one of the central topics in combinatorics. A fundamental problem in this field is to determine the Ramsey number of a given graph H , denoted by R(H) . This is the smallest integer n such that every 2 -colouring of the edges of the complete graph K_{n} contains a monochromatic copy of H . A classical theorem of Ramsey [ 26 ] asserts that R(H) is finite for every graph H , and in 1935 Erdős and Szekeres [ 16 ] established the first explicit upper bound for Ramsey numbers. Later, in 1947, Erdős [ 15 ] gave an exponential lower bound for the case H=K_{k} , marking the first application of the probabilistic method. This lower bound has since only been improved by a constant factor [ 34 ] . On the other hand, the upper bound in the case H=K_{k} has seen several substantial improvements over the years [ 35 , 12 , 31 ] , although an exponential improvement was achieved only recently by Campos, Griffiths, Morris, and Sahasrabudhe [ 10 ] . Together with Balister, Bollobás, Hurley, and Tiba [ 4 ] , they also obtained new upper bounds for multicolour Ramsey numbers. For further background on Ramsey theory, we refer the reader to the surveys [ 13 , 23 ] . An interesting variant of the classical Ramsey problem concerns the study of Ramsey numbers for graph tilings . Given a graph H , an H - tiling is a collection of vertex-disjoint copies of H , and we write mH to denote an H -tiling of size m . One of the earliest questions in this direction, posed by Erdős [ 14 ] , asked for estimates of R(mK_{t}) for all t\geqslant 3 . In 1975, Burr, Erdős, and Spencer [ 9 ] answered this question in a strong form by establishing the following theorem. Theorem 1.1 (Burr, Erdős, and Spencer [ 9 ] ) . Let H be a graph on k vertices that contains no isolated vertices and whose independence number is \alpha . There exist constants c=c(H) and m_{0}\in\mathbb{N} such that R(mH)=(2k-\alpha)m+c for all m\geqslant m_{0} . In their paper, Burr, Erdős, and Spencer [ 9 ] stated Theorem 1.1 in a more general setting, deriving bounds for R(mH,nG) for arbitrary graphs H and G without isolated vertices. However, in the particular case of Theorem 1.1 , their method does not allow one to compute the constant c explicitly in terms of H , nor does it provide bounds on m_{0} . A few years later, Burr [ 8 ] refined their results by determining the exact dependence of the constant c on the graphs for the cases R(G,mH) and R(mK_{r},mK_{s}) . More recently, Bucić and Sudakov [ 7 ] showed that m_{0}=2^{O(k)} suffices, and determined the constant c(H) in the case where H is a clique. The statement of Theorem 1.1 naturally leads to an inverse version of the Ramsey problem for graph tilings, which we formulate as follows. Question 1.2 . For n\in\mathbb{N} and a given graph H , how large a monochromatic H -tiling is guaranteed in any r -colouring of the edges of K_{n} ? Given two graphs H and G , we will write Rt_{r}(H,G) for the largest integer m such that in every r -colouring of the edges of G , there is a monochromatic H -tiling of size m in G , with all the copies of the same colour. When r=2 , we simply write Rt(H,G) . Using this notation, we can restate the result of Burr, Erdős, and Spencer [ 9 ] for R(nH) as follows. Theorem 1.3 (Burr, Erdős, and Spencer [ 9 ] ) . Let H be a graph on k vertices that contains no isolated vertices and whose independence number is \alpha . There exist constants n_{0}\in\mathbb{N} and c=c(H) such that Rt(H,K_{n})=\left\lfloor{\frac{n}{2k-\alpha}-c}\right\rfloor for all n\geqslant n_{0} . A variant of this problem was considered by Balogh, Freschi, and Treglown [ 5 ] who studied the setting in which the host graph is not complete. In particular, they studied the case where the host graph G has linear minimum degree. They determined the exact value of Rt(K_{3},G) when 4n/5\leqslant\delta(G)\leqslant{5n}/{6} and when \delta(G)\geqslant{65n}/{66} . However, the value of Rt(K_{3},G) remains unknown in the intermediate range of \delta(G) . For general graphs H , the question remains wide open. Another natural setting arises when the host graph is the random graph. Gishboliner, Krivelevich, and Michaeli [ 19 ] determined the threshold for the property that, in any r -colouring of the edges of \mathbb{G}(n,p) , there exists an almost monochromatic path of size 2n/(r+1)-o(n) , possibly excluding a constant number of edges. Their result (Theorem 1.5 in [ 19 ] ) immediately yields the following random version of Theorem 1.3 for perfect matchings. Theorem 1.4 (Gishboliner, Krivelevich, and Michaeli [ 19 ] ) . Let r\geqslant 2 be a positive integer. For every \varepsilon>0 , there exists C=C(\varepsilon)>0 such that the following holds. If p\geqslant C/n and G\sim\mathbb{G}(n,p) , then \displaystyle Rt_{r}(K_{2},G)\geqslant\frac{n}{r+1}-\varepsilon n with high probability. This result was later extended to random hypergraphs by Gishboliner, Glock, Michaeli, and Sgueglia [ 18 ] . In this paper, we investigate 1.2 in the case r=2 when the host graph