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:** -Ramsey number, -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 , the chromatic number is the least numbers of colours such that there is a vertex colouring such that is an independent set for each .

Equivalently, is the least number of clours , such that for any partition of into 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 be families of graphs, let be a graph. We say

if for all colourings there is either an or there is a .

We define

Again, note that these are weak subgraphs, not necessarily induced subgraphs.

Ramsey’s theorem for graphs states that for all there is an such that . This leads to the question of “What is the *minimum* such ?”. Of course we need to specify what “minimum means”. We could use any of the following scales:

- , the number of vertices of .
- , the number of edges of .
- , the maximal degree of .
- , the chromatic number of .

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

**Definition**. Let be a monotone graph parameter, which is fixed. For families of graphs define

**the -Ramsey number of**by

In particular, .

The quantity 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 is to fix and ask about upper and lower bounds for (as a function of ).

**Exercise (possibly hard)**. There are such that , but .

One way to investigate the quantity is through a type of “maximal” equivalence. Before we give it, we give some relevant definitions.

**Definition**. Let be graphs. A

**(graph) homomorphism**from to is a function such that

The class of every homomorphism , for which there is a , such that is onto is denoted .

When has a single element , we denote .

We now give the equivalence.

**Theorem (Burr-Erdős-Lusasz, 1976)**. Let be families of graphs. We have

Therefore, if is a graph, we have

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

**Definition**. Let be a graph. Let be an independent set with vertices. The

**wreath product**is the graph obtained by replacing each vertex with a copy , and putting an edge between all vertices in and iff .

More generally, we could replace each vertex of with an independent set of possibly different cardinality. Denote this by .

Even more generally, if are families of graphs, then is the class of all graphs obtained by replacing each vertix of some with a copy of , and extended the edge relation as before.

This wreath product plays very well with homomorphisms.

**Lemma**. iff there is an such that .

**Proof**. The here is anything larger than , where is a graph homomorphism from to . Conversely, given such an , the graph homomorphism is the projection onto .

**Lemma**. Let be a graph.

- For all , .
- iff there is a homomorphism from onto .

**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 , then there is a such that .

**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 ):

**Exercise**. Find

Note that .

## Bounds

**Lemma (Upper bound for )**. Let , and let be the classicial Ramsey number. Then . Moreover, if , then this is an equality.

**Proof**. Fix .

by definition, and this is

In the case that , the only becomes an equality.

Put another way we have the following:

**Upper bound**. .

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

**Proposition (Lower bound)(BRL, 1976)**. .

**Proof**. We will show that if , then . This invloves giving an edge colouring on that doesn’t have a monochromatic .

Let be a complete graph on vertices with all of its edges blue. Let be the same, but with red edges.

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

This lower bound made BEL conjecture that it was tight.

**Conjecture (BEL 1976)**. .

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 is the graph with vertex set and edges where , .

**Conjecture (Hedetniemi 1966)**. .

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

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 such that and . This means that

Let be a list of all possible edge-colourings of .

For each there is a monochromatic subgraph with .

Let . (“A quite natural candidate.”)

Assuming Hedetniemi’s conjecture, we know . So 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 . More on that in a moment.

### Fractional chromatic number

We introduce the fractional chromatic number.

**Definition**. Let be a graph and let be the collection of all nonempty independent subsets of . Let be a function such that

In this case, the **fractional chromatic number of (with respect to )** is

**Exercise**. Show that if , then .

**Theorem (Lovasz)**. , and the gap can be arbitrarily large.

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

**Theorem (Zhu 2011)**. .

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 .

**Exercise**. Show that

where is the largest cardinality of an independent set in , called the independence number of .

If , then , which implies , which implies . Here is the largest size of a complete subgraph of , called the clique number of .

Use this observation to construct the , 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)

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

here: http://www.assafrinot.com/paper/16

LikeLike

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