Fractional Hedetniemi’s conjecture and Chromatic Ramsey number – Ramsey DocCourse Prague 2016 – Mike Pawliuk

The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.

Title: Fractional Hedetniemi’s conjecture and Chromatic Ramsey number

Lecturer: Xuding Zhu

Date: November 9, 2016

Main Topics: Chromatic Ramsey numbers, lower bound for them, Hedetniemi’s conjecture, fractional Hedetniemi’s conjecture.

Definitions: $\rho$ -Ramsey number, $\chi$ -Ramsey number, wreath product, product graph, graph homomorphism, fractional chromatic number

Introduction

We introduce a natural generalization of Ramsey number for graphs first investigated by Burr, Erdős and Lovasz in the 1970s. We look for Ramsey witnesses of minimal chromatic number, not of minimal number of vertices. We look at bounds for this quantity and show that a conjectured lower bound of Burr-Erdős-Lovasz is tight.

At the heart of these discussions is Hedetniemi’s product conjecture that the graph product preserves chromatic number. In one construction we would like to use this conjecture, but instead we work around and use a weaker version of the product conjecture that is known to hold.

Warning: Unlike most of the rest of the DocCourse, subgraphs are not induced, they are subcollections of edges.

Definitions

Definition. For a graph $G=(V,E)$ , the chromatic number $\chi(G)$ is the least numbers of colours $n$ such that there is a vertex colouring $f: V \rightarrow [n]$ such that $f^{-1}(i)$ is an independent set for each $i \leq n$ .

Equivalently, $\chi(G)$ is the least number of clours $n$ , such that for any partition of $V$ into $n-1$ sets, one colour contains an edge.

We’ve looked at chromatic number in Bootcamp 6.

We now define (weak) Ramsey for two classes.

Definition. Let $\mathcal{F}, \mathcal{G}$ be families of graphs, let $H = (V,E)$ be a graph. We say

$\displaystyle H \longrightarrow (\mathcal{F}, \mathcal{G})$
if for all colourings $c: E \rightarrow [2]$ there is either an $F \in \mathcal{F} \cap c^{-1}(0)$ or there is a $G \in \mathcal{G} \cap c^{-1}(1)$ .

We define

$\displaystyle H \longrightarrow (\mathcal{G}) :\equiv H \longrightarrow (\mathcal{G}, \mathcal{G}).$
Again, note that these are weak subgraphs, not necessarily induced subgraphs.

Ramsey’s theorem for graphs states that for all $\mathcal{G}, \mathcal{F}$ there is an $H$ such that $H \longrightarrow (\mathcal{F}, \mathcal{G})$ . This leads to the question of “What is the minimum such $H$ ?”. Of course we need to specify what “minimum means”. We could use any of the following scales:

$\rho_1(H) = \vert V(H) \vert$ , the number of vertices of $H$ .
$\rho_2(H) = \vert E(H) \vert$ , the number of edges of $H$ .
$\rho_3(H) = \text{deg}(H)$ , the maximal degree of $H$ .
$\rho_4(H) = \chi(H)$ , the chromatic number of $H$ .

Traditional Ramsey numbers are measured using $\rho_1$ . We introduce Ramsey numbers subject to the other scales.

Definition. Let $\rho$ be a monotone graph parameter, which is fixed. For families of graphs $\mathcal{F}, \mathcal{G}$ define the $\rho$ -Ramsey number of $(\mathcal{F}, \mathcal{G})$ by

$\displaystyle R_\rho(\mathcal{F}, \mathcal{G}) := \inf \{\rho(H) : H \longrightarrow (\mathcal{F}, \mathcal{G})\}.$

In particular, $R_\chi (G) = \min\{\chi(G) : H \longrightarrow (\mathcal{F}, \mathcal{G})\}$ .

The quantity $R_\chi(G)$ was first studied by Burr-Erdős-Lovasz in 1976. On the surface it seems more difficult, but in reality it’s just different. We have many techniques for constructing graphs of a specific chromatic number.

Bounds and basic equivalences

One approach to understanding $R_\chi(G)$ is to fix $\chi(G)=n$ and ask about upper and lower bounds for $R_\chi(G)$ (as a function of $n$ ).

Exercise (possibly hard). There are $G_1, G_2$ such that $\chi(G_1) = \chi(G_2)$ , but $R_\chi(G_1) \neq R_\chi (G_2)$ .

One way to investigate the quantity $R_\chi(G)$ is through a type of “maximal” equivalence. Before we give it, we give some relevant definitions.

Definition. Let $G,H$ be graphs. A (graph) homomorphism from $G$ to $H$ is a function $f: V(G) \rightarrow V(H)$ such that

$\displaystyle \{x,y\} \Rightarrow \{f(x), f(y)\} \in E(H).$

The class of every homomorphism $f$ , for which there is a $G \in \mathcal{G}$ , such that $f$ is onto $V(G)$ is denoted $\text{Hom}(\mathcal{G})$ .

When $\mathcal{G}$ has a single element $G$ , we denote $\text{Hom}(G) := \text{Hom}(\mathcal{G})$ .

We now give the equivalence.

Theorem (Burr-Erdős-Lusasz, 1976). Let $\mathcal{F}, \mathcal{G}$ be families of graphs. We have

$\displaystyle \text{Hom}(\mathcal{F}, \mathcal{G}) = \min \{m : K_m \rightarrow (\text{Hom}(\mathcal{F}), \text{Hom}(\mathcal{G}))\}.$
Therefore, if $G$ is a graph, we have

$\displaystyle \text{Hom}(G) = \min \{m : K_m \rightarrow (\text{Hom}(G))\}.$

This allows us to relate to classical Ramsey numbers, and that large body of work. We can also relate to $n$ -partite graphs in the following way.

Definition. Let $G = (V,E)$ be a graph. Let $I_k$ be an independent set with $k$ vertices. The wreath product $G[I_k]$ is the graph obtained by replacing each vertex $v \in V$ with a copy $I(v) \cong I_k$ , and putting an edge between all vertices in $I(v)$ and $I(w)$ iff $\{v,w\} \in E$ .

More generally, we could replace each vertex of $V$ with an independent set of possibly different cardinality. Denote this by $G[\mathcal{I}_\omega]$ .

Even more generally, if $\mathcal{G}, \mathcal{H}$ are families of graphs, then $\mathcal{G}[\mathcal{H}]$ is the class of all graphs obtained by replacing each vertix $v \in V(G)$ of some $G \in \mathcal{G}$ with a copy of $H_v \in \mathcal{H}$ , and extended the edge relation as before.

This wreath product plays very well with homomorphisms.

Lemma. $G^\prime \in \text{Hom}(G)$ iff there is an $I_k$ such that $G^\prime \subset G^\prime[I_k]$ .

Proof. The $k$ here is anything larger than $\max\{\vert f^{-1}(v)\vert : v \in V(G)\}$ , where $f$ is a graph homomorphism from $G^\prime$ to $G$ . Conversely, given such an $I_k$ , the graph homomorphism is the projection onto $G$ .

Lemma. Let $G$ be a graph.

For all $k$ , $\chi(G) = \chi(G[I_k])$ .
$\chi(G) = n$ iff there is a homomorphism from $G$ onto $K_n$ .

Proof. The vertex colouring that witnesses one will witness the other (possibly extending or restricting the colouring).

For the second part, collapsing all vertices of the same colour is a homomophism.

We are now in a position to relate the BEL characterization, and chromatic Ramsey numbers, to wreath products.

Lemma. If $K_m \longrightarrow (G^\prime)$ , then there is a $k$ such that $K_m[I_k] \longrightarrow (G^\prime[I_k])$ .

Proof.
[Exercise, for now.]

Putting this all together, the question about finding the chromatic Ramsey number can be framed as follows (using the example of $C_5$ ):

Exercise. Find

$\displaystyle R_\chi(C_5) = \min \{m : K_m \longrightarrow (\{C_3, C_5\})\}.$
Note that $\text{Hom}(C_5) = \{C_3, C_5\}$ .

Bounds

Lemma (Upper bound for $R_\chi$ ). Let $\chi(G)=n$ , and let $R(k,k)$ be the classicial Ramsey number. Then $R_\chi(G) \leq R(n,n)$ . Moreover, if $G = K_n$ , then this is an equality.

Proof. Fix $\chi(G)=n$ .

$\displaystyle R_\chi(G) = \min\{m : K_m \longrightarrow (\text{Hom}(G))\}$
by definition, and this is

$\displaystyle \leq \min\{m : K_m \longrightarrow (K_n)\} := R(n,n).$

In the case that $G=K_n$ , the only $\leq$ becomes an equality.

Put another way we have the following:

Upper bound. $\max\{R_\chi(G) : \chi(G) = n\} = R(n,n)$ .

Now we give a lower bound. This will involve constructing an interesting graph and colouring.

Proposition (Lower bound)(BRL, 1976). $(n-1)^2 + 1 \leq \min\{R_\chi(G) : \chi(G) = n\}$ .

Proof. We will show that if $\chi(G)=n$ , then $K_{(n-1)^2} \not\longrightarrow (G)$ . This invloves giving an edge colouring on $K_{(n-1)^2}$ that doesn’t have a monochromatic $G$ .

Let $B = K_{n-1}$ be a complete graph on $n-1$ vertices with all of its edges blue. Let $R = K_{n-1}$ be the same, but with red edges.

The graph $R[B]$ , obtained by replacing each vertex in $R$ with a copy of $B$ and extending the red edges between copies of $B$ , is the desired graph. It is straightforward to show it does not contain a monochromatic copy of $K_n$ (and so no monochromatic copy of $G$ ).

This lower bound made BEL conjecture that it was tight.

Conjecture (BEL 1976). $\min\{R_\chi(G) : \chi(G) = n\} = (n-1)^2+1$ .

This conjecture was proved by Zhu, and we will see a partial proof. Before that we introduce a conjecture that would greatly simplify the proof.

Hedetniemi’s product conjecture

Recall the following product construction we introduced in Bootcamp 6.

Definition. The product of two graphs $G_1 = (V_1, E_1), G_2 = (V_2, E_2)$ is the graph $G_1 \times G_2$ with vertex set $V_1 \times V_2$ and edges $\{(u,u^\prime), (v,v^\prime)\}$ where $\{u,v\} \in E_1$ , $\{u^\prime,v^\prime\} \in E_2$ .

Conjecture (Hedetniemi 1966). $\chi(G \times H) = \min\{\chi(G), \chi(H)\}$ .

This conjecture is natural, and the $\geq$ direction is immediate. (In this case check that a vertex-partition of $G$ pushes up to a vertex-partition of $G \times H$ . However, a vertex partition of $G \times H$ need not project onto $G$ or $H$ .)

This conjecture was vigourously debated in the Workshop on Colourings and Homomorphisms in Vancouver BC, in July 2000, and remains an important open problem in chromatic graph theory. (Mike: I’ve included a link to the original conference schedule, but it appears the links are all broken. It still contains the speakers and their talk titles.)

See the references below for surveys about this conjecture.

Proof of the BEL conjecture

We give a proof that relies on the Hedetniemi conjecture. After this proof we discuss how to fix this. Interestingly, this construction appears in the 1976 BEL paper, but they did not see how to overcome the use of Hedetniemi’s conjecture.

Proof of the BEL conjecture (assuming the Hedetniemi conjecture).. We wish to find a graph $G$ such that $\chi(G)=n$ and $R_\chi (G) = (n-1)^2 +1$ . This means that

$\displaystyle K_{(n-1)^2+1} \longrightarrow (\text{Hom}(G)).$
Let $c_1, \ldots, c_N$ be a list of all possible $2$ edge-colourings of $K_{(n-1)^2+1}$ .

For each $c_i$ there is a monochromatic subgraph $G_i$ with $\chi(G_i)=n$ .

Let $G = G_1 \times \ldots \times G_N$ . (“A quite natural candidate.”)

Assuming Hedetniemi’s conjecture, we know $\chi(G) = n$ . So $R_\chi(G) = (n-1)^2+1$ as desired.

It will turn out that we can use a slightly weaker (and true!) form of Hedetniemi’s conjecture. This will require that we find slightly more sophisticated graphs $G_i$ . More on that in a moment.

Fractional chromatic number

We introduce the fractional chromatic number.

Definition. Let $G$ be a graph and let $\mathcal(I)$ be the collection of all nonempty independent subsets of $G$ . Let $f: \mathcal{I} \longrightarrow [0,1]$ be a function such that

$\displaystyle \sum_{x \in I} f(I) \geq 1, \forall x \in V(G).$

In this case, the fractional chromatic number of $G$ (with respect to $f$ ) is

$\displaystyle \chi_f(G) := \min \sum_{I \in \mathcal{I}} f(I).$

Exercise. Show that if $f : \mathcal{I} \rightarrow \{0,1\}$ , then $\chi_f (G) = \chi(G)$ .

Theorem (Lovasz). $\chi_f (G) \leq \chi(G)$ , and the gap can be arbitrarily large.

The corresponding fractional Hedetniemi’s conjecture is true. (Again, the $\geq$ direction is an easy exercise.)

Theorem (Zhu 2011). $\chi_f (G \times H) = \min\{\chi_f(G), \chi_f(H)\}$ .

Tardif observed that the fractional Hedetniemi’s conjecture would be enough to prove the BEL conjecture.

Proof of the BEL conjecture (assuming the fractional Hedetniemi conjecture).. The proof will proceed as before, but with a variation on the graphs $G_i$ .

Exercise. Show that

$\displaystyle \chi_f(G) \geq \frac{\vert V \vert}{\alpha(G)},$
where $\alpha(G)$ is the largest cardinality of an independent set in $G$ , called the independence number of $G$ .

If $\chi_f(\text{Red}) \leq n-1$ , then $\chi(G) \leq n-1$ , which implies $\omega(\text{Blue}) \geq n$ , which implies $\chi_f (\text{Blue}) \geq n$ . Here $\omega(G)$ is the largest size of a complete subgraph of $G$ , called the clique number of $G$ .

Use this observation to construct the $G_i$ , and then the result follows from the fractional Hedetniemi conejcture.

Exercise. Fill in the details of the above sketch.

Zhu’s proof of the fractional Hedetniemi conjecture

Mike’s comment. In lecture Zhu provided a proof of the fractional conjecture. I have not included it here, but it can be found in his 2011 paper (reference below).

References

Burr, Erdős, Lovasz. “On graphs of Ramsey type”, 1976
Hedetniemi. “Homomorphisms of graphs and automata”, 1966
Zhu. “The fractional version of Hedetniemi’s conjecture is true”, 2011

Surveys (by date published)

Tardif. “Hedetniemi’s conjecture, 40 years later”, 2008
Sauer. “Hedetniemi’s conjecture—a survey.”, 2001
Zhu. “A survey on Hedetniemi’s conjecture”, 1998)

Other summaries

3 thoughts on “Fractional Hedetniemi’s conjecture and Chromatic Ramsey number – Ramsey DocCourse Prague 2016”

saf says:

November 13, 2016 at 1:16 pm

Thanks for the write-up, Mike! And let me remind the readers of Boolesrings that the infinitary version of Hedetniemi’s conjecture was resolved in this paper.

(Mike- I cleaned up the link.)

LikeLike

1. saf says:
  
  November 13, 2016 at 1:16 pm
  
  here: http://www.assafrinot.com/paper/16
  
  LikeLike
  
2. Micheal Pawliuk says:
  
  November 13, 2016 at 5:03 pm
  
  Indeed! I was pleasantly surprised to see your name while I was looking for references. I’ll embed it into the main text soon.
  
  LikeLike