IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Poset Ramsey Numbers for Boolean Lattices

  • March 29, 2019
  • 2:30 p.m.
  • LeConte 312

Abstract

A subposet $Q'$ of a poset $Q$ is a 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 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 Order (2017), where they proved $R(Q _ 2, Q _ n) \le 2n+ 2$ and $n+m \le 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$ and $R(Q _ 2, Q _ n) \le \frac{5}{3}n + \frac{2}{3}$.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC