A graph homomorphism [$\mu : G \to H$]
is a function [$ V(G)\to V(H) $]
such that [$uv$] is an edge [$\implies \mu(u)\mu(v)$] is an edge.
Also called an [$H$]-coloring of [$G$]
([$k$]-coloring = [$K_k$]-coloring)
We write [$G\to H$] if there is any.
Hedetniemi's conjecture
[$\chi(G\times H) = \min(\chi(G),\chi(H))$]
equivalently
[$G \times H \to K_k\quad\Leftrightarrow\quad G\to K_k\ \mbox{ or }\ H\to K_k$]
A graph [$K$] is multiplicative if
[$G \times H \to K\quad\Leftrightarrow\quad G\to K\ \mbox{ or }\ H\to K$]
Multiplicative graphs
A graph [$K$] is multiplicative if
[$G \times H \to K\quad\Leftrightarrow\quad G\to K\ \mbox{ or }\ H\to K$]
Hedetniemi's conjecture: all cliques [$K_n$] are multiplicative?
El-Zahar & Sauer ('85): [$K_3$]
Häggkvist et al. ('88): all cycles [$C_n$]
Tardif (2005): circular cliques [$K_{p/q}$] with [$\frac{p}{q}<4$]
W.: all square-free graphs (= graphs with no [$C_4$] subgraph)
Delhommé & Sauer (2002): all square-free graphs, if we only consider [$G,H$] containing triangles.
General idea – graphs as spaces
Every graph gets a corresponding topological space:
a copy of [$[0,1]$] for every edge, endpoints glued into vertices.
Every [$K$]-coloring of [$G$] corresponds to a continuous map:
Walk types
Consider closed walks [$C = g_0 g_1 g_2 \dots g_0$] (vertices and edges may repeat) in [$G$], based at [$g_0$].
We define an equivalence relation:
Walk types
Consider closed walks [$C = g_0 g_1 g_2 \dots g_0$] (vertices and edges may repeat) in [$G$], based at [$g_0$].
Let the equivalence class (its type) be [$[C]$].
Graphs as spaces
We want the space of [$C_1 \times C_2$] to be the product of spaces for [$C_1$] and [$C_2$] – so, a torus.
Graphs as spaces
We want the space of [$C_1 \times C_2$] to be the product of spaces for [$C_1$] and [$C_2$] – so, a torus.
Walk types
Fundamental group
[$\pi(G)$] =
elements: types [$[C]$] of closed walks based at [$g_0$]
multiplication: concatenation of walks
inverse: reverse the walk
Homomorphism Lemma
Let [$\mu: G \times H \to K$] and let [$[C]\in \pi(G\times H)$].
Then [$[\mu(C)]\in \pi(K)$]
and [$[\mu(C \cdot D)] = [\mu(C)]\cdot[\mu(D)]$].
Back to products
Let [$[C]\in \pi(G\times H)$].
Then [$[C|_G]\in \pi(G)$].
Product Lemma
The mapping [$[C] \mapsto ([C|_G], [C|_H])$] is an isomorphism onto its image
[$ \pi(G\times H) \to \pi(G) \times \pi(H) $]
Let [$[C_G] \in \pi(G),\ [C_H] \in \pi(H)$], and [$\mu : G\times H \to K$].
[$ ([C_G],\varepsilon) $] is a type that commutes with [$(\varepsilon,[C_H])$] in [$\pi(G \times H)$] .
Hence [$ \mu([C_G],\varepsilon) $] commutes with [$\mu(\varepsilon,[C_H])$] in [$\pi(K)$].
For square-free [$K$], this means winding around the same cycle!
Because for two different cycles, [$X \cdot Y \neq Y \cdot X$] in [$\pi(K)$].
Using the idea
Let [$[C_G] \in \pi(G),\ [C_H] \in \pi(H)$].
Then if [$K$] is square-free:
[$ \mu([C_G],\varepsilon) = R^{\cdot i}$] and [$\mu(\varepsilon,[C_H]) = R^{\cdot j}$]
for some [$R \in \pi(K)$] (the root) and [$i,j\in \mathbb{Z}$].
Using the idea
Theorem Let [$\mu : G\times H \to K$] for a square-free [$K$]. Either:
[$ \mu([C_G],\varepsilon) = \varepsilon $] for all closed walks in [$G$],
[$ \mu(\varepsilon,[C_H]) = \varepsilon $] for all closed walks in [$H$],
or [$ \mu([C]) = \mu([C|_G], \varepsilon) \cdot \mu(\varepsilon, [C|_H]) = R^{\cdot i}$] for all closed walks in [$G \times H$].
Back to reality
Suppose [$ \mu([C_G],\varepsilon) = \varepsilon $] for all closed walks in [$G$]. This means:
For any closed walk [$g_0 g_1 g_2 \dots g_0$] in [$G$] and any [$h_0 h_1 \in E(H)$],
the sequence [$\mu(g_i, h_{i{\small\mbox{ mod }}2})$] of colors in [$K$] looks like this:
Back to reality
Suppose [$ \mu([C_G],\varepsilon) = \varepsilon $] for all closed walks in [$G$]. This means:
For any closed walk [$g_0 g_1 g_2 \dots g_0$] in [$G$] and any [$h_0 h_1 \in E(H)$],
the sequence [$\mu(g_i, h_{i{\small\mbox{ mod }}2})$] of colors in [$K$] looks like this:
Recoloring
Let [$\mu: G\times H \to K$].
We change colors (values assigned by [$\mu$]) one by one
to get a [$\mu^*$] such that [$\mu^*(\cdot, h)$] is as constant as possible for each [$h \in H$].
Lemma Homotopy types essentially don't change when recoloring.
Recoloring
Let [$\mu: G\times H \to K$].
We change colors (values assigned by [$\mu$]) one by one
to get a [$\mu^*$] such that [$\mu^*(\cdot, h)$] is as constant as possible for each [$h \in H$].
Recoloring
Assume [$ \mu([C_G],\varepsilon) = \varepsilon $] for all closed walks [$C_G$] in [$G$].
Then with recoloring we get [$\mu^* : G \times H \to K$]
such that [$\mu^*(g_1,h) = \mu^*(g_2,h)$] for all [$g_1,g_2,h$].
So [$\mu^*(g,h) = \gamma(h)$], where [$\gamma : H \to K$]□
Assume [$ \mu(\varepsilon,[C_H]) = \varepsilon $] for all closed walks [$C_H$] in [$H$].
Then with recoloring we get [$G \to K$]□
Recoloring
Assume [$\mu([C]) = R^{\cdot i} $] for all closed walks in [$G \times H$], for some common [$R \in \pi(K)$].
Then after recoloring, [$\mu^*(G\times H) \subseteq R$]
[$R$] corresponds to a [$\delta: C_n \to K$],
so [$\mu^* : G\times H \xrightarrow{\quad} C_n \xrightarrow{\ \delta\ } K$]
By multiplicativity of cycles, we have
[$G \to C_n \to K$] or [$H \to C_n \to K$] □
Thank you! Questions?
The case of circular [$K$]
[$\pi(K) \simeq \mathbb{Z}$], the type of a [$\mu(C)$] says how many times it winds around [$K$].
Let [$\mu: G \times H \to K$].
Let [$C_G$], [$C_H$] be odd cycles in [$G,H$].
[$ \mu([C_G],\varepsilon) \cdot \mu(\varepsilon,[C_H]) = \mu([C]) $] for some [$[C]\in\pi(K)$] of odd length.
Hence [$\mu([C_G],\varepsilon)$] winds an odd number of times, for all odd cycles [$C_G$]
and [$\mu(\varepsilon,[C_H])$] winds an even number of times, for all odd cycles [$C_H$] (or vice-versa).
The case of circular [$K$]
Hence [$\mu([C_G],\varepsilon)$] winds an odd number of times, for all odd cycles [$C_G$].
If a cycle winds oddly, then there are two antipodal points of the cycle that map to antipodal points of [$K$].
This means every odd cycle in [$G$] has a vertex [$g$] with [$\mu(g,h_0) = \mu(g,h_1)$].
We give those vertices [$g$] this color,
and color the remaining bipartite subgraph with [$\mu(g,h_0)$] and [$\mu(g,h_1)$], alternatingly.
