KELDESIGN


Home

Math Home

Tuple-Chromatic Ramsey Graphs

Tuple-chromatic Ramsey numbers are a generalization of multi-color Ramsey Numbers. This comes from an area of combinatorics called Ramsey Theory. I wrote a paper on tuple-chromatic Ramsety Theory that can be found here: http://www.keldesign.com/math/TCRamsey/Tuple-Chromatic-Ramsey.pdf.

In simpler terms, tuple-chromatic Ramsey numbers are the smallest complete graph with edges colored with r different colors such that there must exist a complete subgraph of size k with edges colored in at most q colors. The numbers are written as tcR(r,q;k). Classical multi-color Ramsey numbers only consider subgraphs of size k with edges colored in at most 1 color (monochrome) and are often written as R(r,k). Based on this, we have R(r,k) = tcR(r,1;k).

Currently, it is very difficult to determine exact values for tuple-chromatic Ramsey numbers or for classical Ramsey numbers. On the other hand, lower bounds for these numbers can be determined by creating graphs that do not have complete subgraphs of at most q colors. These are called witnesses, because they tell us that the corresponding tuple-chromatic Ramsey numbers would have to be larger. The following images represent such witnesses.

Tuple-chromatic Ramsey number witnesses have an interesting property. If a witness if for tcR(r,q;k), then choose any k points. The edges joining the k points in pairs must be colored in atleast q+1 colors.

For example, the following graph is a witness for tcR(3,2;3). If you pick any 3 points, then the 3 edges joining those points will be colored in 2+1=3 colors. In other words, every triangle in this graph contains all three colors.


tcR(3,2;4)

The next graph is for tcR(3,2;4), so every 4 points will have edges of all 3 colors.


tcR(3,2;5)

The next graph is for tcR(3,2;5), so every 5 points will have edges of all 3 colors.


tcR(3,2;6)


tcR(4,2;4)


tcR(4,2;5)


tcR(4,3;4)

One of my favorite witnesses. This one has an interesting symmetry. In this picture, red, green and yellow all have a triangle and two separate lines, whereas blue has two triangles. You can see that red and blue are symmetric about the center vertical axis. Yellow and green mirror each other.


tcR(4,3;5)


tcR(4,3;6)


tcR(4,3;7)


tcR(5,2;3)

This one has thicker lines, just because I thought it looked better. Notice that the edges leaving each vertex have all 5 colors.


tcR(5,2;4)


tcR(5,2;5)


tcR(5,3;4)


tcR(5,3;5)


tcR(5,3;6)


tcR(5,3;7)


tcR(5,3;15)


tcR(5,4;5)


tcR(5,4;6)


tcR(5,4;7)