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
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.
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.
if for all colourings there is either an or there is a .
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.
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 ).
One way to investigate the quantity is through a type of “maximal” equivalence. Before we give it, we give some relevant definitions.
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.
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.
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.
- For all , .
- iff there is a homomorphism from onto .
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.
[Exercise, for now.]
Putting this all together, the question about finding the chromatic Ramsey number can be framed as follows (using the example of ):
Note that .
by definition, and this is
In the case that , the only becomes an equality.
Put another way we have the following:
Now we give a lower bound. This will involve constructing an interesting graph and colouring.
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.
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.
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.
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.
In this case, the fractional chromatic number of (with respect to ) is
The corresponding fractional Hedetniemi’s conjecture is true. (Again, the direction is an easy exercise.)
Tardif observed that the fractional Hedetniemi’s conjecture would be enough to prove the BEL conjecture.
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.
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).
- 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)