Products, internal homs and Hedetniemi's Conjecture - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:38:30Z http://mathoverflow.net/feeds/question/107591 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107591/products-internal-homs-and-hedetniemis-conjecture Products, internal homs and Hedetniemi's Conjecture Julian Kuelshammer 2012-09-19T16:33:50Z 2012-09-19T21:57:49Z <p>I'm looking for interesting examples and non-examples of the following property:</p> <blockquote> <p>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).$$</p> </blockquote> <p>If the category has internal homs then by some abstract nonsense this can be reformulated as:</p> <blockquote> <p>$K$ has the property that $\nexists C\to K$ then $\exists hom(C,K)\to K$.</p> </blockquote> <p>Of course the category should be non-additive (otherwise every object $K$ has property (*) since the product is a coproduct).</p> <p>The question arose from the subject of graph theory: $K_n$ has property (*) is equivalent to <a href="http://garden.irmacs.sfu.ca/?q=op/hedetniemis_conjecture" rel="nofollow">Hedetniemi's Conjecture</a> (that if the categorical product of two graphs is $n$-colorable then one of the graphs is $n$-colorable)</p> <p>I'm also interested in answers dealing with the tensor product instead of the product.</p> http://mathoverflow.net/questions/107591/products-internal-homs-and-hedetniemis-conjecture/107623#107623 Answer by Todd Trimble for Products, internal homs and Hedetniemi's Conjecture Todd Trimble 2012-09-19T21:57:49Z 2012-09-19T21:57:49Z <p>Any category with a zero object (e.g., pointed sets) has the property. </p> <p>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. </p> <p>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. </p>