Square-free graphs are multiplicative

or

A topological approach related to Hedetniemi's conjecture

November 7, BGW, Bordeaux
Marcin Wrochna

(Torus example)

Hedetniemi's conjecture (1966)

[$\chi(G\times H) = \min(\chi(G),\chi(H))$]

Where [$G \times H$] is defined as:

also known as categorical product.

Tensor product

(Product of paths example)

Graph homomorphism

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$]

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: (Equivalence of closed walks)

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.

(Tensor product of paths)

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.

(Tensor product of paths)

Walk types

(Equivalence of closed walks)

Fundamental group

(Fund. group multiplication example)

[$\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)]$].

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) $]

Example with products

(Torus example) (Torus example)
[$([C_G], \varepsilon)$][$(\varepsilon, [C_H])$]

Example with products

(Torus example)
[$([C_G], \varepsilon) + (\varepsilon, [C_H])\ =\ ([C_G], [C_H])\ =\ (\varepsilon, [C_H]) + ([C_G], \varepsilon)$]

Using the idea

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:

(Tree folding example)

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$]

The case of circular [$K$]

Thank you!     Questions?

/