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

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


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.


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.

  1. For all k , \chi(G) = \chi(G[I_k]) .
  2. \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]) .
[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\} .


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).


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

Surveys (by date published)

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

Other summaries

  1. Wikipedia entry for “Hedetniemi’s Conjecture”.
  2. Open Problem Garden entry for “Hedetniemi’s Conjecture”.

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

  1. 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.)


    1. Indeed! I was pleasantly surprised to see your name while I was looking for references. I’ll embed it into the main text soon.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s