论文标题
Hypergraph Ramsey数量的集团与恒星
Hypergraph Ramsey numbers of cliques versus stars
论文作者
论文摘要
令$ k_m^{（3）} $表示完整的$ 3 $ - 均匀的超图和$ m $顶点和$ s_n^{（3）} $ $ 3 $ - 均匀的hypergraph上的$ n+1 $ n+1 $ pertices，由所有$ \ binom {n} {2} $ edges组成的所有$ n+1 $ tertices to to to to to to to to to to to to to to to to to to to to to to to vertex。虽然大多数多数级或至少是指数级增长的许多超图拉姆西的数字，但我们表明，偏离的ramsey数字$ r（k_ {4}^{（3）}，s_n^{（3）} $ r（k_ {4}^{（3）}，s_n^{（3）}）\ le 2^{c'n^{2/3} \ log n} \]，对于某些积极常数$ c $和$ c'$。这些边界的证明带来了一个新颖的拉姆西问题，这可能引起独立的兴趣：什么是最低$ n $，使得笛卡尔产品的任何$ 2 $ - edge颜色$ k_n \ square k_n $包含红色矩形或蓝色$ k_n $？
Let $K_m^{(3)}$ denote the complete $3$-uniform hypergraph on $m$ vertices and $S_n^{(3)}$ the $3$-uniform hypergraph on $n+1$ vertices consisting of all $\binom{n}{2}$ edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off-diagonal Ramsey number $r(K_{4}^{(3)},S_n^{(3)})$ exhibits an unusual intermediate growth rate, namely, \[ 2^{c \log^2 n} \le r(K_{4}^{(3)},S_n^{(3)}) \le 2^{c' n^{2/3}\log n} \] for some positive constants $c$ and $c'$. The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum $N$ such that any $2$-edge-coloring of the Cartesian product $K_N \square K_N$ contains either a red rectangle or a blue $K_n$?
