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 条
  • [41] Hamiltonian Cycles and Symmetric Chains in Boolean Lattices
    Streib, Noah
    Trotter, William T.
    GRAPHS AND COMBINATORICS, 2014, 30 (06) : 1565 - 1586
  • [42] On Learning Families of Ideals in Lattices and Boolean Algebras
    Bazhenov, Nikolay
    Mustafa, Manat
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024, 2024, 14637 : 1 - 13
  • [43] The complete cd-index of Boolean lattices
    Fan, Neil J. Y.
    He, Liao
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (02)
  • [44] On induced Ramsey numbers for k-uniform hypergraphs
    Dellamonica, Domingos, Jr.
    La Fleur, Steven
    Roedl, Vojtech
    RANDOM STRUCTURES & ALGORITHMS, 2016, 48 (01) : 5 - 20
  • [45] Rings with Boolean Lattices of One-Sided Annihilators
    Jastrzebska, Malgorzata
    SYMMETRY-BASEL, 2021, 13 (10):
  • [46] Boolean-valued analysis and injective Banach lattices
    A. G. Kusraev
    Doklady Mathematics, 2012, 85 : 341 - 343
  • [47] COVER-PRESERVING ORDER EMBEDDINGS INTO BOOLEAN LATTICES
    WILD, M
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1992, 9 (03): : 209 - 232
  • [48] ON MULTICOLOR RAMSEY NUMBERS OF TRIPLE SYSTEM PATHS OF LENGTH 3
    Bohman, Tom
    Zhu, Emily
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (03) : 1419 - 1435
  • [49] Some Generalized Bipartite Ramsey Numbers Involving Short Cycles
    Ernst J. Joubert
    Graphs and Combinatorics, 2017, 33 : 433 - 448
  • [50] Some Generalized Bipartite Ramsey Numbers Involving Short Cycles
    Joubert, Ernst J.
    GRAPHS AND COMBINATORICS, 2017, 33 (02) : 433 - 448