The past three posts have been building up to the statement of the recently disproved Hedetniemi’s conjecture. I wanted to make an attempt to write about this, because from a first reading the main ideas of the counterexample seemed very familiar to an algebraic geometer. (More about this in a future post, hopefully.)
Definition. A colouring of a loopless graph with
colours is a graph homomorphism
. The chromatic number
of
is the smallest positive integer
such that
admits a colouring with
colours.
Note that if has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is
, since
is a subgraph of the complete graph on
.
Example. We have if and only if
has no edges (we say that
is discrete), and
if and only if
contains no odd cycles (we say that
is bipartite). Indeed, if you try to produce a
-colouring by colouring adjacent vertices opposite colours, either this produces a
-colouring or you find an odd cycle.
Conjecture (Hedetniemi). Let and
be graphs. Then
Remark. Note that : if
is a colouring, then the composition
is a colouring of
, and similarly for
. Thus, it remains to rule out
with
and
.
Example. The case where is easy to check:
- If
and
, then both
and
have an edge, hence so does
. Then
.
- If
and
, then both
and
contain an odd cycle. If
has an
-cycle and
an
-cycle with
and
odd, then these give morphisms
and
. Wrapping around
(resp.
) times gives morphisms
,
, hence to the product:
. Thus,
does not admit a
-colouring since
doesn’t.
Thus, if , then
.