Ramsey-Sperner theory (Q1821793): Difference between revisions

For positive integers k, \(\ell\), n let \(f_{\ell}(n,k)\) denote the least positive integer f such that for every family \({\mathcal F}\subseteq 2^ n\) of subsets of \(\{\) 1,...,n\(\}\) and for every k-coloring \(\Delta: \{1,...,n\}\to \{1,...,k\}\) there exists a chain \(F_ 1\varsubsetneq...\varsubsetneq F_{\ell +1}\) with \(F_ i\in {\mathcal F}\) for \(i=1,...,\ell +1\) such that the difference \(F_{\ell +1}\setminus F_ 1\) is monochromatic, i.e. \(\Delta \upharpoonright (F_{\ell +1}\setminus F_ 1)=const\). The Sperner case is obtained for \(k=1\), whereas monochromacity refers to Ramsey. The authors survey the known results for 1-colorings, in particular \(f_{\ell}(n,1)\sim \ell \left( \begin{matrix} n\\ \lfloor n/2\rfloor \end{matrix} \right)\) for \(\ell\) fixed and n large enough. For the case of 2-colorings it is shown that \[ f_{\ell}(n,2)=\ell \left( \begin{matrix} n\\ \lfloor n/2\rfloor \end{matrix}\right) \quad for\quad \ell =1,2 \] and \[ f_{\ell}(n,2)<\ell \cdot \left( \begin{matrix} n\\ \lfloor n/2\rfloor \end{matrix} \right)\quad for\quad \ell \geq 3. \] Using previous results for 1-colorings, they proved, in connection with a question of Graham, the existence of a constant \(\phi_{\ell}(k)\) such that \[ f_{\ell}(n,k)\sim \phi_{\ell}(k)\cdot \left( \begin{matrix} n\\ \lfloor n/2\rfloor \end{matrix} \right) \] for large n, where \(\phi_{\ell}(k)\sim \ell \cdot \sqrt{\frac{\pi k}{4\ell nk}}\) for fixed \(\ell\) and \(k\to \infty.\) Extending this generalizations to symmetric chain orders as well as variants of such problems are discussed.