Splitting numbers of grids
Summary: For a subset \(S\) of a finite ordered set \(P\), let \[ S\!\!\uparrow\;=\{x\in P:x\geq s\text{ for some }s\in S\}\quad\text{and} \quad S\!\!\downarrow\;=\{x\in P:x\leq s\text{ for some }s\in S\}. \] For a maximal antichain \(A\) of \(P\), let \[ s(A)=\max_{A=U\cup D}\frac {|U\!\!\uparrow\!\!|+|D\!\!\downarrow\!\!|} {|P|}, \] the maximum taken over all partitions \(U\cup D\) of \(A\), and \[ s_k(P)=\min_{A\in{\mathcal A}(P),|A|=k} s(A) \] where we assume \(P\) contains at least one maximal antichain of \(k\) elements. Finally, for a class \({\mathcal C}\) of finite ordered sets, we define \[ s_k({\mathcal C})=\inf_{P\in{\mathcal C}}s_k(P). \] Thus \(s_k({\mathcal C})\) is the greatest proportion \(r\) satisfying: every \(k\)-element maximal antichain of a member \(P\) of \({\mathcal C}\) can be ``split'' into sets \(U\) and \(D\) so that \(U\!\!\uparrow\!\cup\;D\!\!\downarrow\) contains at least \(r|P|\) elements. In this paper we determine \(s_k({\mathcal G}_k)\) for all \(k\geq 1\) where \({\mathcal G}_k=\{{\mathbf k} \times{\mathbf n}:n\geq k\}\) is the family of all \(k\) by \(n\) ``grids''.
scientific article; zbMATH DE number 2161318