Products, internal homs and Hedetniemi's Conjecture

2012-09-19T16:33:50Z

I'm looking for interesting examples and non-examples of the following property:

Let $\mathcal{C}$ be a category admitting finite products. An object $K$ has the property (*) if: $$\forall C,D\in \mathcal{C}(\exists C\times D\to K\Rightarrow \exists C\to K\ or\ \exists D\to K).$$

If the category has internal homs then by some abstract nonsense this can be reformulated as:

$K$ has the property that $\nexists C\to K$ then $\exists hom(C,K)\to K$.

Of course the category should be non-additive (otherwise every object $K$ has property (*) since the product is a coproduct).

The question arose from the subject of graph theory: $K_n$ has property (*) is equivalent to Hedetniemi's Conjecture (that if the categorical product of two graphs is $n$-colorable then one of the graphs is $n$-colorable)

I'm also interested in answers dealing with the tensor product instead of the product.

Answer by Todd Trimble for Products, internal homs and Hedetniemi's Conjecture

2012-09-19T21:57:49Z

Any category with a zero object (e.g., pointed sets) has the property.

Any category with a terminal object $1$ such that every object $C$ is either initial or has a point $1 \to C$ has the property. For example, the category of sets or of topological spaces.

Most toposes do not satisfy the property: if $C$ and $D$ are subterminal, then $K = C\times D = C \wedge D$ usually produces a counterexample.

Products, internal homs and Hedetniemi's Conjecture - MathOverflow

Products, internal homs and Hedetniemi's Conjecture

Answer by Todd Trimble for Products, internal homs and Hedetniemi's Conjecture