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 1026281
- Splitting squares
- Counting Divisions of a 2 × n Rectangular Grid
- scientific article; zbMATH DE number 3884166
- scientific article; zbMATH DE number 3841867
- Grid spanners
- A divide-and-conquer algorithm for grid generation
- scientific article; zbMATH DE number 1081132
- scientific article; zbMATH DE number 1161375
This page was built for publication: Splitting numbers of grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773209)
