4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Though I make occasional excursions into combinatorics, I am primarily a number theorist; it is entirely possible that this question is well-known to some. Indeed, I hope this is the case. I explicitly do not apologize if this question has well-known answers or very easy for experts; a good-faith search on my part has been fruitless, and what is MO good for if not for this? On the other hand, if this is well-known AND it's written someplace that I "really should have looked", then I do apologize, and I just ask that you tell me where. $\endgroup$
    – Cap Khoury
    Mar 3, 2010 at 16:45
  • 1
    $\begingroup$ There's the fact that T_Y needs at most |X|-many subsets of Y, and vice versa. Other than that, there is very little control: for any collection of tolerable subsets T_X, there are many T_Y's which will admit a strict coloring. You can say "if z-many subsets of T_X are realized which contain element x in a coloring, then T_Y will need a set with at most |Y|- z elements", and other properties which (must) name both X and Y. Perhaps looking at literature on 0-1 matrices and things like Hall's marriage theorem will help. Gerhard "Ask Me About System Design" Paseman, 2010.03.03 $\endgroup$ Mar 3, 2010 at 17:11
  • 1
    $\begingroup$ Also, if one of T_X, T_Y contains the full set and both contain proper nonempty subsets, then there is a strict coloring. It might be easier to study special T_X and see what T_Y are allowed where, e.g., T_Y contains sets of size at most alpha*|Y|. Gerhard "Ask Me About System Design" Paseman, 2010.03.03 $\endgroup$ Mar 3, 2010 at 17:23
  • 1
    $\begingroup$ For instance, if all elements of $T_X$ have cardinality $\leq \alpha|X|$ and all elements of $T_Y$ have cardinality $\leq \beta |Y|$ then a necessary condition for the exaistence of a coloring $\alpha +\beta \geq 1$. $\endgroup$ Sep 5, 2010 at 13:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.