论文标题
图形爆炸中的两个拉姆齐问题
Two Ramsey problems in blowups of graphs
论文作者
论文摘要
给定图形$ g $和$ h $，我们说$ g \ stackrel {r} {\ to}令$ h [t] $表示$ h $的$ t $ blowup。爆炸拉姆西号$ b（g \ stackrel {r} {\ to} h; t）$是最小$ n $，以至于$ g [n] \ stackrel {r} {r} {\ to} h [t] $。 Fox，Luo和Wigderson完善了Souza的上限，表明，给定$ G $，$ H $和$ R $ $ g \ stackrel {r} {r} {\ to} h $，存在常数$ a = a = a = a（g，h，h，r）$和$ b = b = b（h，r）$ \ stackrel {r} {\ to} h; t）\ leq ab^t $。他们猜想存在一些图表$ h $，根据$ g $，常量$ a $的$ h $。我们通过证明$ h $是$ 3 $ chromatial Connection的说明是正确的，我们证明了这一猜想，特别是包括三角形。另一方面，也许令人惊讶的是，我们表明，对于森林$ f $，功能$ b（g \ stackrel {r} {\ to} f; t; t; t）$独立于$ g $。 其次，我们证明，对于任何$ r，t \ in \ mathbb {n} $，在$ n $ dertices上具有$ω（n^{2-1/t}）$ edges上的任何足够大的$ r $ - 边缘彩色完整的图形，每个颜色都包含来自某个有限族的$ \ nathcal $ \ nathcal $ \ nathcal {f}^r $ $ r_t $ r_-edde的成员。这回答了Bowen，Hansberg，Montejano和Müyesser的猜想。
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 $Ω(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üyesser.
