Partitions that are "mutually nested"

Question

Let $\mathcal{P}_1,\dots,\mathcal{P}_m$ be a collection of ordered $n$-partitions of a set $\mathcal S$, which is to say that that $$\mathcal{P}_i = \{P^i_1\cup\dots\cup P^i_n\}$$ for all $i$. Suppose that these partitions satisfy the property that for all $i,j,k$, we have that either $P^i_k\subset P^j_k$ or $P^i_k\supset P^j_k$. I have two questions:

1. Is there a name for this property?
2. If $\mathcal{S}$ is measurable, and we define $a_{ij} = \lambda(P^i_j)$, are there any necessary or sufficient conditions on the matrix $[a_{ij}]$?

Regarding the second question, it is not hard to verify that any matrix of dimensions $2\times n$ or $m\times 2$ admits a suitable collection of partitions. The diagram below depicts a solution for $[a_{ij}] = \left(\begin{array}{ccc} 5 & 4 & 3\\ 2 & 5 & 5\\ 3 & 8 & 1 \end{array}\right)$ of the set $\mathcal{S}=\{1,\dots,12\}$, where red denotes $P_1^i$ (the first column), green denotes $P_2^i$, and blue denotes $P_3^i$:

Answer 1

Let $s=|S|$.

We show that the question boils down to deciding whether a given $s$-uniform hypergraph admits a panchromatic coloring (when all colors are present in every edge) in $s$ colors. Moreover, the two questions are in fact equivalent, so a good criterion for them exists or not simultaneously. (Seems that such crterion is unknown.)

This may be a dual setup to that in Aaron Meyerowitz’s answer. We also treat the integer case; the general one seems to be easily reducible to it.

1. First of all, we rephrase the nestedness condition. Fix a $j$ and consider a collection of all the $P_j^i$. This collection is nested, so one may enumerate the elements of the largest of them as $x_j^1, \dots, x_j^{k_j}$ so that each set $P_j^i$ consists of some prefix of that list; i.e., if $|P_j^i|=a_{ij}$, then $$ P_j^i=\left\{x_j^t\colon t\leq a_{ij}\right\}. $$

2. Now, given an (integer nonnegative) matrix $A$ whose row sums are all equal to $s$, we construct an $s$-uniform hypergraph $(V,E)$ as follows.

For every column $j$, we find the maximal number $$ k_j=\max_i a_{ij} $$ in it, and introduce $k_j$ vertices $v_j^1,\dots, v_j^{k_j}$.

For every row $i$, we introduce an edge $$ e_i=\left\{v_j^t\colon 1\leq j\leq n, \; t\leq a_{ij}\right\}. $$

So, if the matrix $A$ correspond to a nested system of partitions, then the vertex $v_j^t$ is in $e_i$ iff the element $x_j^t$ introduced above lies in $P_j^i$. This means that, in this case, the constructed hypergraph admits a panchromatic coloring in $s$ colors, whih are the elements of $S$.

Vice versa, if such coloring exists, one can merge all vertices having the same color in one vertex, thus obtaining an $s$-element set with desired partitions.

THus we are really interested whether the constructed $s$-uniform gypergraph admits a panchromatic coloring in $s$ colors.

3. Finally, notice that we can obtain any $s$-uniform hypergraph by the procedure above, even while considering only 0-1 matrices $A$. Thus the two questions are really equivalent.

Remark. We can go further, introducing a graph on the same set of vertices and drawing an edge $(x,y)$ whenever $x$ and $y$ lie in one hyper-edge constructed above. Then we are interested in a proper coloring of the obtained graph in $s$ colors. (However, now not every graph can be obtained in this way, since this graph is a union of several cliques of size $s$.)

Answer 2

I have a few comments on the integer case including (I think) a solution for $m=3.$ I won't tackle the second question, although it may be no harder.

I found the notation confusing so let me restate. You have a non-negative matrix $A=[a_{ij}]$ with $n$ rows, $m$ columns, and constant row sum $s.$

Optional motivation: This specifies a particular type of list of $m$ colorings of a set $S$ with $|S|=s,$ each using some or all of a set $\{c_1,c_2,\cdots,c_n\}$ of colors. We wish to either find a list of colorings of this type or show that there is none. If there is such a list of colorings, we will describe it by a matrix with $m$ rows and $s$ columns showing, for each element, the color it gets in each coloring.

The goal is to create an $m\times s$ matrix $C$ whose entries are colors $c_1,c_2,..,c_n$ with these properties:

• $a_{ij}$ is the number of times that row $i$ of $C$ contains the color $c_j$.
• If $a_{pj} \le a_{qj},$ then the columns of $C$ having $c_j$ in position $p$ are a subset of those having $c_j$ in position $q$.

All that really matters is the multi-set of columns of $C$, their order isn't important. Call $A$ realizable if there is such a matrix $C.$ and call $C$ a realization of $A.$

The following condition is necessary for $m=3.$ I think that might be sufficient, at least for $n=3$. That might even be easy to show (or false.)

For each column of $A$, look at the set of numbers which appear there and take the second smallest. The sum of these numbers should be no more than $s.$

A first comment is that we may assume that each column of $A$ has a $0$ entry because $\min_i a_{ij}$ is the number of columns of $C$ with $c_j$ in all $m$ positions.

A second comment is that if $A=A'+A''$ with each of $A'$ and $A''$ realizable, then also $A$ is realizable. If has only one realization then $A$ and $A''$ are either both realizable or neither is.

The first comment is simply the observation that an $A$ with constant columns is easily seen to be feasible in a unique way.

I will now drop down to the case $m=3.$ If the matrix $A$ has a $0$ in each column, it is necessary that the smallest non-negative entries in each column, when added, are no larger than the row sum. This is because if column $j$ of $A$ is $\left(\begin{array}{c}u\\v\\0\end{array}\right)$ with $0<u \le v,$ then there must be $u$ columns in $C$ which have $c_j$ in the first two positions. These must be different than the columns with $c_k$ in two specified positions.

Let me illustrate by using your matrix $$\left(\begin{array}{ccc} {\color{red}5} & {\color{green}4} & {\color{blue}3}\\ {\color{red}2} & {\color{green}5} & {\color{blue}5}\\ {\color{red}3} & {\color{green}8} & {\color{blue}1} \end{array}\right)=\left(\begin{array}{ccc} 2 & 4 & 1\\ 2 & 4 & 1\\ 2 & 4 & 1 \end{array}\right)+\left(\begin{array}{ccc} 3 & 0 & {\mathbf 2}\\ 0 & {\mathbf 1} & 4\\ {\mathbf 1} & 4 & 0 \end{array}\right)$$

I want a $3 \times 12$ color matrix. I see that I need $2$ red, $4$ green and $1$ blue column. These are the first $7$ columns in the illustration below.

I have $5$ columns to go. The matrix with row sum $5$ tells me what is required. Since the highlighted entries add to $2+1+1 \leq 5,$ the original matrix is feasible. I will further break down the second matrix (losing constant row sums, as it happens):

$$\left(\begin{array}{ccc} 3 & 0 & {\mathbf 2}\\ 0 & {\mathbf 1} & 4\\ {\mathbf 1} & 4 & 0 \end{array}\right)=\left(\begin{array}{ccc} 1 & 0 & {\mathbf 2}\\ 0 & {\mathbf 1} & 2\\ {\mathbf 1} & 1 & 0 \end{array}\right)+\left(\begin{array}{ccc} 2 & 0 & 0\\ 0 & 0 & 2\\ 0& 3 & 0 \end{array}\right)$$

Looking at the smallest positive entry in each column tells me that that I need one column red on the top and bottom, one green in the middle and bottom and two blue in the top and middle positions. These $4$ columns are distinct. Since I have $5$ columns to play with, this is possible. The illustration below shows the situation at this point. Off to the right are the colors still to be inserted in each row. There is no choice and no problems arise.

Answer 3

Here is another answer. It may be essentially Ilya's from a more naive perspective.

Again I will treat the question as: We are given an $n \times m$ non-negative integer matrix $A$ with row sums $s$. We may imagine that the entries are colored with $n$ colors, a unique one for each column. Do one or the other of the following

• Construct a a collection of $m$ ordered partitions of an $s$-set $\mathcal S$ into $n$ parts, some of which may be empty, having the sizes specified by the entries of $A$ and having the desired nesting property.
• Prove that this is impossible.

I will represent (or at least imagine) such a collection of partitions as a multiset of $s$ column vectors of height $m$ with each entry one of the $n$ given colors.

I will sketch a method which transforms it into an elaboration of a the Bin Packing Problem . This achieves two things.

• It suggests that the problem is probably NP-complete.
• It also suggests that there are algorithms, based on the extensive work on bin packing, that will, in practice, quickly settle even very large instances.

At any rate,

Here is the bin problem as is I want to use it here, followed by some added features. The method is below that, and can be consulted before or during the following.

1. We are given a multiset of $sn$ non-negative integers with total sum $sm$ and must determine if they can be partitioned into $s$ groups each of sum $m.$ (There is no harm in deleting the $0$s)

Furthermore,

2. The integers are colored, each with one of $n$ colors. There are $s$ of each color and the groups must contain $n$ members, of different colors. (Or up to $n$ non-negative members of distinct colors)

Additionally,

3. Each of the colored positive integers , say a red $j$, on closer inspection is actually a column vector of height $m$ with $m-j$ blank entries and the other $j$ entries red. So the original set is actually of $sn$ vectors of height $m$, $n$ of each color. And within the groups, no two vectors are allowed to have a non-blank entry in the same place. (Again, no harm in discarding the all blank vectors, each of which has an official color.)

At this point I will illustrate the method via a partial example and relate it to the above.

Suppose $A$ is $4 \times n$ with row sums $100$ and first two columns

$\left( \begin{array}{ccc} {\color{red}1}&{\color{green}2}& \cdots \\{\color{red}0}&{\color{green}6}& \cdots \\{\color{red}5}&{\color{green}0}& \cdots \\{\color{red}3}&{\color{green}4}& \cdots\end{array} \right)$

Then I will make the following $5$ red vectors and $6$ green vectors. (Perhaps along with $95$ blank red vector and $94$ blank green vectors.)

And similar vectors for the other $n-2$ colors.

When we then attempt to assemble the 100 groups of (up to) $n$ columns We see that, of the $30$ red/green pairs, $12$ cannot be in the same group: None of the first three red can pair with any of the first four green. The other $18$ are possible.

In the colored bin packing simplification we have colored integers $$\color{red}{ 3\ 2\ 2\ 1\ 1} \ \ \ \color{green}{ 3\ 3\ 2\ 2\ 1\ 1}$$

Now it seems that one could have group with a red $2$ and a green $2$, but the vector version shows that is forbidden.

One often effective technique in bin packing is to sort the integers in decreasing order of size and then put them into bins in a greedy manner. Here one might take the partially filled columns in decreasing order of size. If there are more than $s$ no two of which can be in the sme group, that is an obstacle. If not then we have some groups fairly far along. next we can continue withe a greedy strategy. If we get to the stage where the remaining unassigned vectors have only one or two non-blank entries, it should be rapid to decide if we can finish.

Admittedly, that is fairly vague. But it makes he problem fit into a well studied framework.