3
$\begingroup$

Following Fedor Petrov's remarks, here is a "set-theoretic version" of the question I asked a while ago.


For integer $n\ge 1$, denote by $\mathcal M_n$ the family of all (finite) multisets with the ground set $[n]$. Considering the multisets from $\mathcal M_n$ as functions from $[n]$ to the set of non-negative integers, we can speak about the support ${\rm supp} A\subseteq[n]$ of a multiset $A\in\mathcal M_n$; thus, $|{\rm supp} A|$ is just the number of distinct elements of the ground set contained in $A$. Also, define a partial order on $\mathcal M_n$ writing $A\preceq B$ if $A(i)\le B(i)$ for each $i\in[n]$; that is, if the multiplicity of every $i\in[n]$ in $A$ does not exceed its multiplicity in $B$.

The shadow of a multiset $A\in\mathcal M_n$ is the set of all those $A'\in\mathcal M_n$ with $|{\rm supp} A'|=|{\rm supp} A|-1$ and $A'\preceq A$; the shadow of a family $\mathcal A\subseteq \mathcal M_n$ is the set of all those $A'\in\mathcal M_n$ which are the shadow of at least one multiset $A\in\mathcal A$.

Fix now $k\in[1,n]$ and $N\ge 1$, and suppose that $\mathcal A\subseteq\mathcal M_n$ is a family of $N$ multisets with $|{\rm supp} A|=k$ for each $A\in\mathcal A$. How small can the shadow of $\mathcal A$ be (in terms of $N,k$, and $n$)?


It should be possible to work this out, but I wonder whether this problem has already been studied. I am aware of the paper by Bekmetjev, Brightwell, Czygrinow, and Hurlbert, but they seem to treat the things a little differently.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.