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 条
  • [31] SINGLE IDENTITIES FORCING LATTICES TO BE BOOLEAN
    Chajda, Ivan
    Laenger, Helmut
    Padmanabhan, Ranganathan
    MATHEMATICA SLOVACA, 2018, 68 (04) : 713 - 716
  • [32] Subgraphs of hypercubes and subdiagrams of Boolean lattices
    Mitas, J
    Reuter, K
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1996, 13 (01): : 41 - 64
  • [33] Sperner theory in a difference of Boolean lattices
    Logan, MJ
    DISCRETE MATHEMATICS, 2002, 257 (2-3) : 501 - 512
  • [34] Generalizations of the correspondence between Boolean algebras and Boolean rings to orthomodular lattices
    Länger, H
    TATRA MOUNTAINS MATHEMATICAL PUBLICATIONS, VOL 15, 1998: QUANTUM STRUCTURES II, 1998, : 97 - 105
  • [35] Poset Ramsey number R(P, Qn). III. Chain compositions and antichains
    Winter, Christian
    DISCRETE MATHEMATICS, 2024, 347 (07)
  • [36] Poset Ramsey Number R(P, Qn). I. Complete Multipartite Posets
    Winter, Christian
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2024, 41 (02): : 391 - 399
  • [37] Orthomodular lattices that are horizontal sums of Boolean algebras
    Chajda, Ivan
    Laenger, Helmut
    COMMENTATIONES MATHEMATICAE UNIVERSITATIS CAROLINAE, 2020, 61 (01): : 11 - 20
  • [38] Hamiltonian Cycles and Symmetric Chains in Boolean Lattices
    Noah Streib
    William T. Trotter
    Graphs and Combinatorics, 2014, 30 : 1565 - 1586
  • [39] Boolean algebras and distributive lattices treated constructively
    Bell, JL
    MATHEMATICAL LOGIC QUARTERLY, 1999, 45 (01) : 135 - 143
  • [40] The l(p)-function on finite Boolean lattices
    Ortega, Oscar
    Garcia-Martinez, C.
    Adamski, K.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2016, 8 (03)