The size-Ramsey number of 3-uniform tight paths
The size-Ramsey number of 3-uniform tight paths
复制标题
DOI：
10.19086/aic.24581
复制
发表时间：
2019-07
影响因子：
--
通讯作者：
Jie Han;Y. Kohayakawa;Shoham Letzter;G. Mota;Olaf Parczyk
中科院分区：
文献类型：
--
作者：
Jie Han;Y. Kohayakawa;Shoham Letzter;G. Mota;Olaf Parczyk
给定一个超图 H，尺寸拉姆齐数 r(H) 是最小整数 m，使得存在具有 m 个边的图 G，并且具有以下属性：在具有两种颜色的 G 边的任何着色中，存在 H 的单色副本。我们证明 n 个顶点 P_n 上的 3-均匀紧路径的尺寸拉姆齐数在 n 中是线性的，即 r(P_n)=O(n)。这回答了 Dudek、Fleur、Mubayi 和 Rödl 关于 3 均匀超图的问题 [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434]，他们证明了 r(P_n)=O(n^1.5*log^1.5 n)。
Given a hypergraph H, the size-Ramsey number r(H) is the smallest integer m such that there exists a graph G with m edges with the property that in any colouring of the edges of G with two colours there is amonochromatic copy of H. We prove that the size-Ramsey number of the 3-uniform tight path on n vertices P_n is linear in n, i.e., r(P_n)=O(n). This answers a question by Dudek, Fleur, Mubayi, and Rödl for 3-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved r(P_n)=O(n^1.5*log^1.5 n).