Splitting numbers of grids

Dwight Duffus ; Bill Sands

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

For a subset $S$ of a finite ordered set $P$, let $$S\!\uparrow\;=\{x\in P:x\ge s \hbox{ for some }s\in S\}\quad\hbox{and} \quad S\!\downarrow\;=\{x\in P:x\le s \hbox{ for some }s\in S\}.$$ For a maximal antichain $A$ of $P$, let $$s(A)=\max_{A=U\cup D}{|U\!\uparrow|+|D\!\downarrow|\over|P|}\ ,$$ the maximum taken over all partitions $U\cup D$ of $A$, and $$s_k(P)=\min_{A\in {\cal A}(P),|A|=k}s(A)$$ where we assume $P$ contains at least one maximal antichain of $k$ elements. Finally, for a class ${\cal C}$ of finite ordered sets, we define $$s_k({\cal C})=\inf_{P\in {\cal C}}s_k(P).$$ Thus $s_k({\cal C})$ is the greatest proportion $r$ satisfying: every $k$-element maximal antichain of a member $P$ of ${\cal 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({\cal G}_k)$ for all $k\ge 1$, where ${\cal G}_k=\{{\bf k}\times{\bf n}:n\ge k\}$ is the family of all $k$ by $n$ "grids".

Détail

DOI : 10.37236/1914

Classification : 06A07
Mots-clés : finite ordered sets, maximal antichain