Return to Answer

We show that the question boils down to deciding whether a given $n$-uniform hypergraph admits a panchromatic coloring (when all colors are present in every edge) in $n$ 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 $n$, we construct an $n$-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 i\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 $n$ 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 $n$-element set with desired partitions.

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

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

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$.)

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

This may be a dual set up 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.

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

For every column $j$, we find it he 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 t\leq a_{ij}\right\}. $$

If the matrix represents a nested partition system, then the hypergraph can be colored panchromatically in $n$ colors representing the elements of $S$: just assign to $v_j^t$ the color corresponding to the element $x_j^t$ introduced above. Vice versa, such coloring corresponds to a nested system of partitions in the same way.

3. Finally, notice that,, even while considering only 0-1 matrices $A$, we get all $n$-uniform hypergraph. So the questions are really equivalent.

We show that the question boils down to deciding whether a given $n$-uniform hypergraph admits a panchromatic coloring (when all colors are present in every edge) in $n$ 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 $n$, we construct an $n$-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 i\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 $n$ 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 $n$-element set with desired partitions.

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

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

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

This may be a dual set up 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.

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

For every column $j$, we find it he 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 t\leq a_{ij}\right\}. $$

If the matrix represents a nested partition system, then the hypergraph can be colored panchromatically in $n$ colors representing the elements of $S$: just assign to $v_j^t$ the color corresponding to the element $x_j^t$ introduced above. Vice Vera’s, such coloring corresponds to a nested system of partitions in the same way.

3. Finally, notice that,, even while considering only 0-1 matrices $A$, we get all &n&-uniform hypergraph. So the questions are really equivalent.

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

This may be a dual set up 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.

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

For every column $j$, we find it he 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 t\leq a_{ij}\right\}. $$

If the matrix represents a nested partition system, then the hypergraph can be colored panchromatically in $n$ colors representing the elements of $S$: just assign to $v_j^t$ the color corresponding to the element $x_j^t$ introduced above. Vice versa, such coloring corresponds to a nested system of partitions in the same way.

3. Finally, notice that,, even while considering only 0-1 matrices $A$, we get all $n$-uniform hypergraph. So the questions are really equivalent.