= Solution
\b[True in some cases and false in others:] the two numerical inequalities do not guarantee a solution.
For an unsatisfiable example satisfying both inequalities, take six <variables>, a <constraint domain> with five values, and $k=4$, $m=3$, with <all-different constraints> on
$$
\{X_1,X_2,X_3,X_4\},\qquad
\{X_1,X_2,X_5,X_6\},\qquad
\{X_3,X_4,X_5,X_6\}.
$$
Any pair of the six <variables> occurs together in at least one of these scopes: view the <variables> as the three pairs $\{1,2\},\{3,4\},\{5,6\}$, and each scope as the union of two pairs. All six values must therefore be distinct. This is impossible with five available values, even though $5>4$ and $5>3$.
For a satisfiable example with the same $k,m,|D|$, take three disjoint groups of four <variables> and impose one <all-different constraint> on each group. Assign values $1,2,3,4$ separately in every group. All three constraints hold with $D=\{1,2,3,4,5\}$.
$$
\boxed{|D|>k\text{ and }|D|>m\text{ are insufficient.}}
$$
These examples concern the intended cases in which the antecedent holds; they do not rely on vacuous truth of an implication.
Back to article page
