Tran-Ngoc Danh, David E. Daykin
Sets of 0,1 vectors with minimal sets of subvectors
The paper is published: Rostocker Mathematisches Kolloquium, Rostock. Math. Kolloq. 50, 47-52 (1997)
MSC:
05A99 None of the above but in this section
06A07 Combinatorics of partially ordered sets
Abstract: Let ${\cal C}(n)$ be the 0,1 vectors
$\underset{\displaystyle\tilde{}}{a} = a_1 \ldots a_n$.
To get a subvector of $\underset{\displaystyle\tilde{}}{a}$ delete any $a_i$. If
${\cal A} \subseteq {\cal C} (n)$ then $\Delta {\cal A}$ is the set of all subvectors
of members of ${\cal A}$, so $\Delta {\cal A }\subseteq {\cal C}(n-1)$.
Put $W \underset{\displaystyle\tilde{}}{a}
= a_1 + \ldots + a_n$.
We order ${\cal C}(n)$ by $
\underset{\displaystyle\tilde{}}{a} <
\underset{\displaystyle\tilde{}}{b} $ if (i)
$W \underset{\displaystyle\tilde{}}{a} < W
\underset{\displaystyle\tilde{}}{b} $ or (ii)
$W \underset{\displaystyle\tilde{}}{a} = W
\underset{\displaystyle\tilde{}}{b}$ and $1=a_i > b_i = 0$ for the least $i$
with $a_i \neq b_i$. We present a completely new proof of our
\underline {Theorem}. If ${\cal A} \subseteq {\cal C} (n)$ and $\cal I$
is the first $|{\cal A}|$ members in ${{\cal C}} (n)$ then $|\Delta \cal I| \le
|\Delta \cal A|$.
Keywords: Combinatorial problems; Combinatorics of partially ordered sets; Combinatorics on words