Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|cite|improve this question
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. – Cap Khoury Mar 3 '10 at 16:45
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 – Gerhard Paseman Mar 3 '10 at 17:11
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 – Gerhard Paseman Mar 3 '10 at 17:23
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$. – Pietro Majer Sep 5 '10 at 13:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.