论文标题
Ramsey在随机图中的树木善良
Ramsey goodness of trees in random graphs
论文作者
论文摘要
对于图$ g $，我们编写$ g \ rightarrow \ big（k_ {r+1}，\ Mathcal {t}（t}（n，n，d）\ big）$，如果$ g $的每种蓝色的颜色包含$ k_ {r+1} $的蓝色副本，或者是每种$ n $ n $ ed $ edges的蓝色副本，则最多可达$ dgges $ dd $ dd $ dd $ dd $ dd $ dd $ dd $ dd $ d。 1977年，Chvátal证明，对于任何整数，$ r，n，d \ ge 2 $，$ k_n \ rightarrow \ big（k_ {r+1}，\ mathcal {t}（t}（n，n，d）\ big）$，则仅在$ n \ ge rn+1 $中。我们证明了chvátal的定理的随机模拟，也就是说，我们表明，对于每个$ r，d \ ge 2 $，存在常数$ c，c'> 0 $，以便如果$ p \ ge c {n}^{ - 2/（2/（r + 2）} $和$ n \ geq rn + c rn + c'/p $，n，然后\ big（k_ {r+1}，\ Mathcal {t}（n，d）\ big）\] \] \] \ highosigation $ n \ to \ infty $。该证明将稳定性参数与树木图中的树木嵌入结合在一起。此外，稳定性结果的证明是基于erdős-s-Sós的稀疏随机类似物，这些猜想是线性尺寸和有界最大程度的树木，这可能具有独立的关注。
For a graph $G$, we write $G\rightarrow \big(K_{r+1},\mathcal{T}(n,D)\big)$ if every blue-red colouring of the edges of $G$ contains either a blue copy of $K_{r+1}$, or a red copy of each tree with $n$ edges and maximum degree at most $D$. In 1977, Chvátal proved that for any integers $r,n,D \ge 2$, $K_N \rightarrow \big(K_{r+1},\mathcal{T}(n,D)\big)$ if and only if $N \ge rn+1$. We prove a random analogue of Chvátal's theorem for bounded degree trees, that is, we show that for each $r,D\ge 2$ there exist constants $C,C'>0$ such that if $p \ge C{n}^{-2/(r+2)}$ and $N \geq rn + C'/p$, then \[G(N,p) \rightarrow \big(K_{r+1},\mathcal{T}(n,D)\big)\] with high probability as $n\to \infty$. The proof combines a stability argument with the embedding of trees in expander graphs. Furthermore, the proof of the stability result is based on a sparse random analogue of the Erdős--Sós conjecture for trees with linear size and bounded maximum degree, which may be of independent interest.
