Recent graduate student awarded first in Faculty of Mathematics Doctoral Prize competition

Recent PhD graduate Tom Kelly has been awarded first place in the Faculty of Mathematics Doctoral Prize competition. Now in its second year, these prizes are awarded annually to recognize the achievements of top graduating doctoral students in the Faculty of Mathematics. As a gold recipient, Kelly will receive $1,500 and is nominated for the Governor General’s Gold Medal.

Supervised by Professor Luke Postle, a faculty member with the Department of Combinatorics and Optimization, Kelly defended his thesis, His thesis, Cliques, Degrees, and Coloring: Expanding the \(\omega, \Delta, \chi\) paradigm, on July 16, 2019.

Kelly’s thesis made significant contributions to long-standing open problems, including the launch of two major paradigms in graph coloring – a research area for more than 100 years. The study of graph coloring focuses on the following problem: a collection of objects needs a color assigned to each one to satisfy some basic rules such as certain pairs are not allowed to receive the same color. The mathematician’s task is to find a color assignment using as few colors as possible. One application of the use of graph coloring is the correspondence of colors to time slots to model a scheduling problem.

“I believe the results of Tom’s thesis are of the highest caliber and that they will leave a lasting impact on the field,” said Postle. “He is an excellent mathematician with an eye for good problems, more than that for field-changing paradigms.”

Kelly was able to prove a unifying theorem based on Johansson’s results from the 1990s while also providing a new bound on the chromatic number. He also strengthens one of Reed’s theorems and made progress toward Hadwiger’s Conjecture. Finally, he developed a new theory that he called “fractional coloring with local demands” which connected classical graph coloring and extremal graph theory, providing a more robust version of Turan’s Theorem which improves the Caro-Wei bound on the independence number.

“Ultimately, I was surprised by how deep this theory turned out to be,” said Kelly. “There were unexpected connections to other areas of combinatorics, and there are still many opportunities for more research to be done.”

Kelly came to the University of Waterloo as a Master’s student in 2015 after completing his undergraduate degree at Princeton University. He was quickly transferred directly into the PhD program.

Kelly is currently a postdoctoral researcher at the University of Birmingham in the United Kingdom.