Erdős-Gyárfás problem for partially ordered sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918499316662272 |
|---|---|
| author | Katona, Gyula O. H. Mao, Yaping |
| author_facet | Katona, Gyula O. H. Mao, Yaping |
| contents | 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^{\sharp}(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}^{\sharp}_{k,t}(\mathcal{B}\mid Q)$ for every integer $k\ge1$, every $t\ge1$, 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^{\sharp}(n,p,2)$. Next, using the symmetric Lovász local lemma, we obtain a probabilistic upper bound on $f_t^{\sharp}(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10229 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Erdős-Gyárfás problem for partially ordered sets Katona, Gyula O. H. Mao, Yaping Combinatorics 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^{\sharp}(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}^{\sharp}_{k,t}(\mathcal{B}\mid Q)$ for every integer $k\ge1$, every $t\ge1$, 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^{\sharp}(n,p,2)$. Next, using the symmetric Lovász local lemma, we obtain a probabilistic upper bound on $f_t^{\sharp}(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. |
| title | Erdős-Gyárfás problem for partially ordered sets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.10229 |