Let $X$ and $Y$ be finite sets, and let $T_X$ (resp. $T_Y$) be a subset of the power set of $X$ (resp. of $Y$). (I think of the elements of $T_X$ as the tolerable subsets of $X$.)
A strict $(T_X,T_Y)$-coloring is a pair of sets $(A,B)$ whose disjoint union is $X\times Y$, such that
- for every $x\in X$, $\{y:(x,y)\in A\}\in T_Y$
- for every $y\in Y$, $\{x:(x,y)\in B\}\in T_X$
The definition of a lax $(T_X,T_Y)$-coloring is the same, except we don't require disjointness. All I want to know is, for a particular $T=(T_X,T_Y)$, do any $T$-colorings exist?
Notice that the strict problem is a generalization of the lax one. If $T^\star_X$ (resp. $T^\star_Y$) is the set of all subsets of elements of $T_X$ (resp. $T_Y$), then the existence of a lax $(T_X,T_Y)$-coloring is equivalent to the existence of a strict $(T^\star_X,T^\star_Y)$-coloring. In all the cases I actually care about, subsets of tolerable sets are always tolerable, so the distinction disappears. I mention this because I am aware that solving the strict problem in general seems to be much more delicate than anything I need.
The way I usually visualize this is as coloring a grid with two colors, where certain configurations of red are forbidden in each row and certain configurations of blue are forbidden in each column.
There is a trivial necessary condition on $T$ for there to be a (lax) $T$-coloring. Namely, we must have at least one of the following:
For every subset $S$ of $X$, there must exist a tolerable subset of $X$ containing at least half the elements of $S$.
For every subset $S$ of $Y$, there must exist a tolerable subset of $Y$ containing at least half the elements of $S$.
Is this sufficient? (I doubt it.) Are there any other known necessary conditions? Sufficient conditions? Anything even a smidgeon less trivial than the above is likely to be very helpful to me.
(Of course there is a natural generalization to coloring products $X\times Y\times Z$ with three colors, etc.; at this point it is not yet clear whether this generalization is relevant to my work.)