November 7, BGW, Bordeaux
Marcin Wrochna
[$\chi(G\times H) = \min(\chi(G),\chi(H))$]
Where [$G \times H$] is defined as:
also known as
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.
[$\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$]
A graph [$K$] is multiplicative if [$G \times H \to K\quad\Leftrightarrow\quad G\to K\ \mbox{ or }\ H\to K$]
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:
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:
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]$].
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.
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.
[$\pi(G)$] =
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)]$].
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) $]
|
|
[$([C_G], \varepsilon)$] | [$(\varepsilon, [C_H])$] |
|
[$([C_G], \varepsilon) + (\varepsilon, [C_H])\ =\ ([C_G], [C_H])\ =\ (\varepsilon, [C_H]) + ([C_G], \varepsilon)$] |
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)$].
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}$].
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:
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:
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.
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$].
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$] □
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?
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$].
Thank you! Questions?
/