A note on Pseudorandom Ramsey graphs
A note on Pseudorandom Ramsey graphs
复制标题
关于伪随机 Ramsey 图的注释
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
D. Mubayi;Jacques Verstraëte
对于固定的$ s ge 3 $，我们证明，如果存在最佳$ k_s $ -free pseudorandom图，则Ramsey编号
$ r（s，t）= t^{s-1+o（1）} $ as $ t
ightarrow infty $。我们的方法还改善了Bohman和Keevash从随机$ C_ {ELL} $获得的$ r（C_ {ell}，t）$的最佳下限 - polygarithmic因子的免费过程，用于所有奇数$ ell geq 5 $和$ Ell in {6,10} $。对于$ ell = 4 $，它与$ c_4 $ free流程相匹配。
我们还通过另一种方法证明$ R（C_5，T）>（1+O（1））T^{11/8} $和$ R（C_7，T）>（1+O（1） ）t^{11/9} $。这些改善了以前最佳结果中$ t $的指数，似乎是图形$ f $的第一个示例，其周期为$ r（f，t）$的指数改善，在给定的边界上显示通过随机$ f $ f $ fre-fre-fre-freage和随机图。
For fixed $s ge 3$, we prove that if optimal $K_s$-free pseudorandom graphs exist, then the Ramsey number
$r(s,t) = t^{s-1+o(1)}$ as $t
ightarrow infty$. Our method also improves the best lower bounds for $r(C_{ell},t)$ obtained by Bohman and Keevash from the random $C_{ell}$-free process by polylogarithmic factors for all odd $ell geq 5$ and $ell in {6,10}$. For $ell = 4$ it matches their lower bound from the $C_4$-free process.
We also prove, via a different approach, that $r(C_5, t)> (1+o(1))t^{11/8}$ and $r(C_7, t)> (1+o(1))t^{11/9}$. These improve the exponent of $t$ in the previous best results and appear to be the first examples of graphs $F$ with cycles for which such an improvement of the exponent for $r(F, t)$ is shown over the bounds given by the random $F$-free process and random graphs.