Splitting numbers of grids
type: Item
instance of: scholarly article
title: Splitting numbers of grids
zbMATH Open document ID: 1060.06005
author: Dwight Duffus
author: Bill Sands
published in: The Electronic Journal of Combinatorics
publication date: 2005-04-25T00:00:00Z
full work available at URL: https://eudml.org/doc/124430
full work available at URL: v12i1r17.html
review text: 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''.
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 2161318
zbMATH Keywords: finite ordered sets
zbMATH Keywords: maximal antichain
MaRDI profile type: MaRDI publication profile
Recommended article: Q4342906
Recommended article: Splitting squares
Recommended article: Counting Divisions of a 2 × n Rectangular Grid
Recommended article: Q3218129
Recommended article: Q3312234
Recommended article: Grid spanners
Recommended article: A divide-and-conquer algorithm for grid generation
Recommended article: Q4362237
Recommended article: Q4393372
description: scientific article; zbMATH DE number 2161318