Erdős-Gyárfás problem for partially ordered sets

Abstract

Given integers $p,q,t$ with $1\le t\le p$ and $1\le q\le h_p(t)$, a strong $(p,q,t)$-coloring of the Boolean lattice $B_n$ is a coloring of its $t$-chains such that every induced copy of $B_p$ in $B_n$ uses at least $q$ colors on its $t$-chains. Let $f_t^{♯}(n,p,q)$ denote the minimum number of colors in such a coloring. We study this Boolean-lattice analogue of the Erdős-Gyárfás function.We first show that every finite poset strongly embeds into a Boolean lattice. Combined with a structural Ramsey theorem for finite posets with linear extensions, this implies the existence of the strong Boolean Ramsey number ${\mathrm{R}}_{k,t}^{♯}(\mathcal{B}\mid Q)$ for every integer $k\ge 1$, every $t\ge 1$, and every nonempty finite poset $Q$. In particular, this gives an affirmative answer to a problem of Cox and Stolee and yields the existence of $f_t^{♯}(n,p,2)$. Next, using the symmetric Lovász local lemma, we obtain a probabilistic upper bound on $f_t^{♯}(n,p,q)$. Finally, we prove lower bounds by combining Turán-type extremal estimates for $t$-chains, a double-counting argument, and a generalized Lubell-type framework for $t$-chains.

23 pages