Hypergraph Ramsey numbers of cliques versus stars
Hypergraph Ramsey numbers of cliques versus stars
复制标题
超图拉姆齐派系与明星的数量
DOI：
10.1002/rsa.21155
复制
发表时间：
2023
影响因子：
1
通讯作者：
Verstraëte, Jacques
中科院分区：
文献类型：
--
作者：
Conlon, David;Fox, Jacob;He, Xiaoyu;Mubayi, Dhruv;Suk, Andrew;Verstraëte, Jacques
设Km(3)$$ {K}_m^{(3)} $$ 表示m上的完全3‐均匀超图$$ m $$ 顶点和Sn(3)$$ {S}_n^{(3)} $$ n+1上的3‐均匀超图$$ n+1 $$ 由n2个顶点组成$$ \left(\genfrac{}{}{0ex}{}{n}{2}\right) $$ 关联到给定顶点的边。然而许多超图Ramsey数要么以多项式增长，要么以指数增长，我们证明了非对角线Ramsey数r(K4（3),Sn(3)）$$ r\left({K}_4^{(3)},{S}_n^{(3)}\right) $$ 表现出不寻常的中间生长速率，即2clog2n≤r(K4(3),Sn(3))≤2c 'n2/3logn；$$ {2}^{c\log^2n}\le r\left({K}_4^{(3)},{S}_n^{(3)}\right)\le {2}^{c^{\prime }{n}^{2/3}\log n}, $$对于某个正常数c$$ c $$ c '$$ {c}^{\prime } $$． 这些界限的证明带来了网格图上一个新的Ramsey问题，这可能是一个独立的兴趣：最小N是什么$$ N $$ 使得笛卡尔积的任意2边着色KN□KN$$ {K}_N\square {K}_N $$ 包含红色矩形或蓝色Kn$$ {K}_n $$？
Let Km(3)$$ {K}_m^{(3)} $$ denote the complete 3‐uniform hypergraph on m$$ m $$ vertices and Sn(3)$$ {S}_n^{(3)} $$ the 3‐uniform hypergraph on n+1$$ n+1 $$ vertices consisting of all n2$$ \left(\genfrac{}{}{0ex}{}{n}{2}\right) $$ 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(K4(3),Sn(3))$$ r\left({K}_4^{(3)},{S}_n^{(3)}\right) $$ exhibits an unusual intermediate growth rate, namely, 2clog2n≤r(K4(3),Sn(3))≤2c′n2/3logn,$$ {2}^{c\log^2n}\le r\left({K}_4^{(3)},{S}_n^{(3)}\right)\le {2}^{c^{\prime }{n}^{2/3}\log n}, $$for some positive constants c$$ c $$ and c′$$ {c}^{\prime } $$. 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$$ N $$ such that any 2‐edge‐coloring of the Cartesian product KN□KN$$ {K}_N\square {K}_N $$ contains either a red rectangle or a blue Kn$$ {K}_n $$?
登录
查看更多内容
DOI：
10.1007/978-0-8176-8092-3
发表时间：
2021-06
期刊：
Complexity of Infinite-Domain Constraint Satisfaction
影响因子：
--
作者：
Lane Barton
通讯作者：
Lane Barton
拉姆齐理论中的多项式到指数转变
影响因子：
1.8
作者：
Mubayi, Dhruv;Razborov, Alexander
通讯作者：
Razborov, Alexander
关于网格拉姆齐问题及相关问题
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
D. Conlon;J. Fox;Choongbum Lee;B. Sudakov
通讯作者：
B. Sudakov
影响因子：
1.1
作者：
D. Conlon;J. Fox;B. Sudakov
通讯作者：
B. Sudakov
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
D. Mubayi;Andrew Suk
通讯作者：
Andrew Suk