We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. We wish to determine whether there is a function $A\to B$ so that no member of $B$ is the image of more than $k$ members of any $T\in S$.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
This is an example of a constraint satisfaction problem. The variables of the problem are the "colors" of the elements of $A$, where $B$ is the set of colors. For each set $T \in S$ and each $(k+1)$-subset $T'$ of $T$, there is a constraint stating that the elements of $T'$ cannot all have the same color.
If $k=1$ and all $T \in S$ have cardinality $2$, then this is just graph coloring. You can similarly put graph hypercoloring in this framework.
answered Feb 24, 2015 at 20:18
-
$\begingroup$ This uses an
alldifferentconstraint; there are some survey papers about this, e.g. andrew.cmu.edu/user/vanhoeve/papers/alldiff.pdf It might be found in there (or not). $\endgroup$ Commented Feb 24, 2015 at 22:22