## Section14.8Daniel 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])

### Subsection14.8.1Daniel 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]

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]

###### Remark14.8.2.

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

### Subsection14.8.2Reflection

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.

### References14.8.3References

[1]

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

[3]

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

[4]

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

[5]

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

[6]

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.