References & Citations
Mathematics > Combinatorics
Title: Two Ramsey problems in blowups of graphs
(Submitted on 25 May 2022 (v1), last revised 26 Apr 2024 (this version, v3))
Abstract: Given graphs $G$ and $H$, we say $G \stackrel{r}{\to} 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 \stackrel{r}{\to} H;t)$ is the minimum $n$ such that $G[n] \stackrel{r}{\to} H[t]$. Fox, Luo and Wigderson refined an upper bound of Souza, showing that, given $G$, $H$ and $r$ such that $G \stackrel{r}{\to} H$, there exist constants $a=a(G,H,r)$ and $b=b(H,r)$ such that for all $t \in \mathbb{N}$, $B(G \stackrel{r}{\to} H;t) \leq ab^t$. 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 \stackrel{r}{\to} F;t)$ is independent of $G$.
Second, we show that for any $r,t \in \mathbb{N}$, any sufficiently large $r$-edge coloured complete graph on $n$ vertices with $\Omega(n^{2-1/t})$ edges in each colour contains a member from a certain finite family $\mathcal{F}^r_t$ of $r$-edge coloured complete graphs. This answers a conjecture of Bowen, Hansberg, Montejano and M\"uyesser.
Submission history
From: Robert Hancock [view email][v1] Wed, 25 May 2022 14:55:15 GMT (381kb,D)
[v2] Mon, 30 May 2022 15:27:58 GMT (18kb,D)
[v3] Fri, 26 Apr 2024 07:58:43 GMT (20kb,D)
Link back to: arXiv, form interface, contact.