Multiset Covers with a Uniformity Condition

41 Views Asked by At

I was playing around with the indices of tuples of functions, and these objects came up naturally. Is there a name for them? Are there any resources on them that provide some properties or even a classification?

Let $\mathcal{A}\subseteq P([n])$. It has the property that there exists a multiset $\widetilde{\mathcal{A}}$ with elements in $\mathcal{A}$ such that every $i\in [n]$ is in exactly $k$ elements of $\widetilde{\mathcal{A}}$, counted with multiplicity.

Say $\cal{A}=\{S_1 ,\ldots, S_m\}$. I've shown that this roughly corresponds to the binary matrix $[\varepsilon_{i,j}]$, where $\varepsilon_{i,j}=1$ if and only if $i\in S_j$, such that $$ \begin{bmatrix} \varepsilon_{1,1} & \dots & \varepsilon_{1,m}\\ \vdots & \ddots & \vdots\\ \varepsilon_{n,1} & \dots & \varepsilon_{n,m} \end{bmatrix} \begin{bmatrix} l_1\\ \vdots\\ l_m \end{bmatrix}= \begin{bmatrix} 1\\ \vdots\\ 1 \end{bmatrix} $$ has a solution for some nonnegative rational-entried vector $[l_i]$.

1

There are 1 best solutions below

1
On BEST ANSWER

A hypergraph is a generalisation of a graph where each (hyper)edge can connect an arbitrary number of vertices. If we view the elements of $[n]$ as vertices, then $\mathcal A$ is a multiset of hyperedges and $\widetilde{\mathcal A}$ is a $k$-regular hypergraph.

Without further restrictions such hypergraphs are very easy to generate – simply pick for each vertex the $k$ hyperedges that contain it.