2022/05/25 by António Girão, Girão, António, Robert Hancock +1
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2205.12826
openalex publication_date 2022/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given graphs G and H, we say G \stackrelr→ H if every r-colouring of the edges of G contains a monochromatic copy of H. Let H[t] denote the t-blowup of H. The blowup Ramsey number B(G \stackrelr→ H;t) is the minimum n such that G[n] \stackrelr→ H[t]. Fox, Luo and Wigderson refined an upper bound of Souza, showing that, given G, H and r such that G \stackrelr→ H, there exist constants a=a(G,H,r) and b=b(H,r) such that for all t ∈ ℕ, B(G \stackrelr→ H;t) ≤ abt. They conjectured that there exist some graphs H for which the constant a depending on G is necessary. We prove this conjecture by showing that the statement is true in the case of H being 3-chromatically connected, which in particular includes triangles. On the other hand, perhaps surprisingly, we show that for forests F, the function B(G \stackrelr→ F;t) is independent of G. Second, we show that for any r,t ∈ ℕ, any sufficiently large r-edge coloured complete graph on n vertices with Ω(n2-1/t) edges in each colour contains a member from a certain finite family Frt of r-edge coloured complete graphs. This answers a conjecture of Bowen, Hansberg, Montejano and Müyesser.