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
相关论文
共 50 条
  • [1] Poset Ramsey Numbers for Boolean Lattices
    Linyuan Lu
    Joshua C. Thompson
    Order, 2022, 39 : 171 - 185
  • [2] Boolean Lattices: Ramsey Properties and Embeddings
    Axenovich, Maria
    Walzer, Stefan
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2017, 34 (02): : 287 - 298
  • [3] Boolean Lattices: Ramsey Properties and Embeddings
    Maria Axenovich
    Stefan Walzer
    Order, 2017, 34 : 287 - 298
  • [4] Poset Ramsey numbers: large Boolean lattice versus a fixed poset
    Axenovich, Maria
    Winter, Christian
    COMBINATORICS PROBABILITY & COMPUTING, 2023, 32 (04): : 638 - 653
  • [5] Almost tiling of the Boolean lattice with copies of a poset
    Tomon, Istvan
    ELECTRONIC JOURNAL OF COMBINATORICS, 2018, 25 (01):
  • [6] A Boolean topological orthomodular poset
    Harding, John
    ALGEBRA UNIVERSALIS, 2012, 68 (3-4) : 193 - 196
  • [7] A Boolean topological orthomodular poset
    John Harding
    Algebra universalis, 2012, 68 : 193 - 196
  • [8] Incomparable Copies of a Poset in the Boolean Lattice
    Katona, Gyula O. H.
    Nagy, Daniel T.
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2015, 32 (03): : 419 - 427
  • [9] Incomparable Copies of a Poset in the Boolean Lattice
    Gyula O. H. Katona
    Dániel T. Nagy
    Order, 2015, 32 : 419 - 427
  • [10] Partitioning the Boolean lattice into copies of a poset
    Gruslys, Vytautas
    Leader, Imre
    Tomon, Istvan
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2019, 161 : 81 - 98