## Section 14.8 Daniel Král

Daniel Král is a Czech mathematician and computer scientist who works as a professor of mathematics and computer science at the Masaryk University. He obtained his Ph.D. from Charles University in Prague in 2004, under the supervision of Jan Kratochvil.

In 2011, Professor Král won the European Prize in Combinatorics for his work in graph theory, particularly citing his solution to the Plummer–Lovasz conjecture and his results on graph colouring. In 2014, he won a Philip Leverhulme. Prize in Mathematics and Statistics. Professor Král is a Fellow of the American Mathematical Society. [14.8.3.1]

Král and our instructor Dr. Veselin Jungic co–authored two papers. ([14.8.3.5], [14.8.3.6])

### Subsection 14.8.1 Daniel Král's favourite Ramsey theory statement.

Dr. Král's favourite Ramsey theory statement is the Canonical Ramsey Theorem, due to Erdős and Rado. [14.8.3.5]

This is from Dr. Král's message to us:

Suppose that you colour \(k\)–tuples of integers (with as many or as few colours as you like). Clearly, one cannot ask that in each colouring there is an infinite set such that all its \(k\)–tuples are monochromatic, as if each \(k\)–tuple can get a different colour.

So, one needs to permit as an outcome that all \(k\)–tuples have different colours.

Suppose that to each \(k\)–tuple a colour is assigned based on the smallest element, i.e., a \(l\)–tuple \(a_1\lt \cdots \lt a_k\) is coloured by \(a_1\text{.}\) So, we need to permit this outcome as well.

The statement of the theorem uses the following notion. for a set \(R\text{,}\) a subset of \(\{1,\ldots,k\}\text{,}\) we say that a colouring of \(k\)–tuples is \(R\)–canonical if two \(k\)–tuples \(a_1\lt \cdots \lt a_k\) and \(b_1\lt \cdots \lt b_k\) have the same colour if and only if \(a_i=b_i\) for all \(i\) in \(R\text{.}\) [14.8.3.3]

## Theorem 14.8.1. The Canonical Ramsey Theorem.

Any colouring of integers has an infinite subset such that the restriction of the colouring to the \(k\)–tuples formed by elements of this subset is \(R\)–canonical for some \(R\text{.}\)

Note that If \(R\) is the empty set, then all \(k\)–tuples have the same colour and if \(R=\{1,\cdots,k\}\text{,}\) then all \(k\)–tuples have different colours. [14.8.3.3]

###### Remark 14.8.2.

We included the proof of the Canonical Ramsey Theorem in Section 14.9

### Subsection 14.8.2 Reflection

As we are undergraduate students studying both computing science and mathematics ourselves, we were thrilled to be able to communicate with and learn form such an established mathematician and computer scientist.

### References 14.8.3 References

Daniel Král. Wikipedia. Retrieved April 7, 2024, from Wikipedia

Daniel Král. Personal Website. Retrieved April 7, 2024, from Highlights from recent work

Daniel Král. Personal Communication. February 15, 2024.

Erdős, P., Rado, R., *A combinatorial theorem*, J. London Math. Soc. 25, 249–255, 1950.

Jungic, V., Král, D., Škrekovski, R., *Colorings of Planar Graphs with no Rainbow Faces*, Combinatorica, Vol. 6, No. 2, 169–182, 2006.

Jungic, V., Kaiser, T., Král, D., *A note on edge–colourings avoiding rainbow \(K_4\) and monochromatic \(K_m\)*, The Electronic Journal Of Combinatorics 16 (2009), #N19.