A Construction for Boolean Cube Ramsey Numbers

被引:5
作者
Bohman, Tom [1 ]
Peng, Fei [2 ]
机构
[1] Carnegie Mellon Univ, Dept Math, Pittsburgh, PA 15213 USA
[2] Natl Univ Singapore, Dept Math, Singapore, Singapore
来源
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 2023年 / 40卷 / 02期
关键词
Poset Ramsey; Construction; FAMILIES;
D O I
10.1007/s11083-022-09613-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let Q(n) be the poset that consists of all subsets of a fixed n-element set, ordered by set inclusion. The poset cube Ramsey number R(Q(n), Q(n)) is defined as the least m such that any 2-coloring of the elements of Q(m) admits a monochromatic copy of Q(n). The trivial lower bound R(Q(n), Q(n)) >= 2n was improved by Cox and Stolee, who showed R(Q(n), Q(n)) >= 2n + 1 for 3 <= n <= 8 and n >= 13 using a probabilistic existence proof. In this paper, we provide an explicit construction that establishes R(Q(n), Q(n)) >= 2n + 1 for all n >= 3. The best known upper bound, due to Lu and Thompson, is R(Q(n), Q(n)) <= n(2) - 2n + 2.
引用
收藏
页码:327 / 333
页数:7
相关论文
共 9 条
[1]   Boolean Lattices: Ramsey Properties and Embeddings [J].
Axenovich, Maria ;
Walzer, Stefan .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2017, 34 (02) :287-298
[2]   Q2-free Families in the Boolean Lattice [J].
Axenovich, Maria ;
Manske, Jacob ;
Martin, Ryan .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2012, 29 (01) :177-191
[3]   Ramsey Numbers for Partially-Ordered Sets [J].
Cox, Christopher ;
Stolee, Derrick .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2018, 35 (03) :557-579
[4]   Existence thresholds and Ramsey properties of random posets [J].
Falgas-Ravry, Victor ;
Markstrom, Klas ;
Treglown, Andrew ;
Zhao, Yi .
RANDOM STRUCTURES & ALGORITHMS, 2020, 57 (04) :1097-1133
[5]  
Graham RL., 1990, RAMSEY THEORY, V20
[6]  
Grosz D., 2021, ARXIV
[7]   An upper bound on the size of diamond-free families of sets [J].
Grosz, Daniel ;
Methuku, Abhishek ;
Tompkins, Casey .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2018, 156 :164-194
[8]   Poset Ramsey Numbers for Boolean Lattices [J].
Lu, Linyuan ;
Thompson, Joshua C. .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2022, 39 (02) :171-185
[9]   ON THE ERDOS-SZEKERES CONVEX POLYGON PROBLEM [J].
Suk, Andrew .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2017, 30 (04) :1047-1053