共 50 条
Poset Ramsey Numbers for Boolean Lattices
被引:7
|作者:
Lu, Linyuan
[1
]
Thompson, Joshua C.
[1
]
机构:
[1] Univ South Carolina, Columbia, SC 29208 USA
来源:
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS
|
2022年
/
39卷
/
02期
关键词:
Ramsey;
Poset;
Embeddings;
Boolean lattice;
Boolean algebra;
ALGEBRAS;
D O I:
10.1007/s11083-021-09557-4
中图分类号:
O1 [数学];
学科分类号:
0701 ;
070101 ;
摘要:
For each positive integer n, let Q(n) denote the Boolean lattice of dimension n. For posets P, P', define the poset Ramsey number R(P, P') to be the least N such that for any red/blue coloring of the elements of Q(N), there exists either a subposet isomorphic to P with all elements red, or a subposet isomorphic to P' with all elements blue. Axenovich and Walzer introduced this concept in Order (2017), where they proved R(Q(2), Q(n)) <= 2n + 2 and R(Q(n), Q(m)) <= mn + n + m. They later proved 2n <= R(Q(n), Q(n)) <= n(2) + 2n. Walzer later proved R(Q(n), Q(n)) <= n(2)+1. We provide some improved bounds for R(Q(n), Q(m)) for various n, m is an element of N. In particular, we prove that R(Q(n), Q(n)) <= n(2) - n + 2, R(Q(2), Q(n)) <= 5/3 n + 2, and R(Q(3), Q(n)) <= inverted right perpendicular37/16n + 55/16inverted left perpendicular. We also prove that R(Q(2), Q(3)) = 5, and R(Q(m), Q(n)) <= inverted right perpendicular(m - 1 + 2/m+1) n + 1/3 m + 2inverted left perpendicular for all n > m >= 4.
引用
收藏
页码:171 / 185
页数:15
相关论文