Uwe Leck
Optimal shadows and ideals in submatrix orders
Preprint series: Preprints aus dem Fachbereich Mathematik, Universitt Rostock

MSC:

06A07 Combinatorics of partially ordered sets

05D05 Extremal set theory

Abstract: We consider the poset of all submatrices of a given matrix,
ordered by containment. The unique rank function for this poset is given by
$r(M)=R(M)+C(M)-1$, where $R(M)$ and $C(M)$ denote the number of rows and
columns of a nonempty matrix $M$, respectively, and the rank of the empty matrix
is 0. For fixed $k$ and $i$ our objective is to find a set $\mathcal{M}$ of
submatrices $M_1,M_2,\dots ,M_k$ such that $r(M_j)=i$ for all $j$ and the shadow of
$\mathcal{M}$ is minimal, that is, the number of submatrices $M$
with $r(M)=i-1$ contained in a member of $\mathcal{M}$ should be smallest
possible.

Partial results concerning the shadow minimization problem for our poset were
obtained by Sali. In general, he conjectured a theorem of Kruskal--Katona type
to hold. We show that this conjecture is true. In fact, our result covers
a slightly more general case (the cartesian product of a Submatrix
Order and a Boolean lattice).

The mentioned result can be formulated in terms of finite sets: Let $A,B$ be
two disjoint subsets of a finite set $N$. We consider all subsets $F\subseteq N$
satisfying $A\not\subseteq F$ and $B\not\subseteq F$. For fixed $i,k$ we
determine a family $\mathcal{F}=\{F_1,\dots,F_k\}$ of such $i$--subsets of $N$
which has minimum number of $(i-1)$--sets contained in some $F\in\mathcal{F}$.

Finally, as an application we give a solution to the problem of finding an
ideal of given size and maximum weight in Submatrix Orders and in their
duals.
Keywords: partially ordered set, Kruskal-Katona theorem, shadows, submatrix orders