{
  "id": "1909.08680",
  "version": "v1",
  "published": "2019-09-18T20:09:49.000Z",
  "updated": "2019-09-18T20:09:49.000Z",
  "title": "Poset Ramsey Numbers for Boolean Lattices",
  "authors": [
    "Linyuan Lu",
    "Joshua C. Thompson"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A subposet $Q'$ of a poset $Q$ is a \\textit{copy of a poset} $P$ if there is a bijection $f$ between elements of $P$ and $Q'$ such that $x \\le y$ in $P$ iff $f(x) \\le f(y)$ in $Q'$. For posets $P, P'$, let the \\textit{poset Ramsey number} $R(P,P')$ be the smallest $N$ such that no matter how the elements of the Boolean lattice $Q_N$ are colored red and blue, there is a copy of $P$ with all red elements or a copy of $P'$ with all blue elements. Axenovich and Walzer introduced this concept in \\textit{Order} (2017), where they proved $R(Q_2, Q_n) \\le 2n + 2$ and $R(Q_n, Q_m) \\le mn + n + m$, where $Q_n$ is the Boolean lattice of dimension $n$. They later proved $2n \\le R(Q_n, Q_n) \\le n^2 + 2n$. Walzer later proved $R(Q_n, Q_n) \\le n^2 + 1$. We provide some improved bounds for $R(Q_n, Q_m)$ for various $n,m \\in \\mathbb{N}$. In particular, we prove that $R(Q_n, Q_n) \\le n^2 - n + 2$, $R(Q_2, Q_n) \\le \\frac{5}{3}n + 2$, and $R(Q_3, Q_n) \\le \\frac{37}{16}n + \\frac{39}{16}$. We also prove that $R(Q_2,Q_3) = 5$, and $R(Q_m, Q_n) \\le (m - 2 + \\frac{9m - 9}{(2m - 3)(m + 1)})n + m + 3$ for all $n \\ge m \\ge 4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-09-18T20:09:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "06A07",
      "05C55"
    ],
    "keywords": [
      "boolean lattice",
      "poset ramsey numbers",
      "blue elements",
      "red elements"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}