Damir D. Dzhafarov

Department of Mathematics University of Connecticut (United States)



Computable combinatorics: the past, present, and future

Early on in the history of computability theory, it was noticed that the subject can be applied to study the effectivity not just of subsets of the natural numbers but also of various classes of mathematical theorems. This has taken on many forms over the years, from effective mathematics to computable structure theory to reverse mathematics. One especially prominent class of theorems in this endeavor are those that have the form of PI1/2 statements of second-order arithmetic, or more generally, the form for every set X of numbers, there is a set Y with certain properties. The effective study of these theorems has been especially fruitful in the realm of combinatorics, giving rise to a highly active industry of research. I will survey some of the work in this area, from the pioneering results of Jockusch in the 1970s on Ramseys theorem, through the ongoing investigation in reverse mathematics of so-called irregular principles, and into some of the exciting new directions of research being opened up by interactions between computable combinatorics and computable analysis. Along the way, I will mention a number of open problems.


Damir Dzhafarov obtained his PhD in 2011 from the University of Chicago under the supervision of Denis Hirschfeldt, Antonio Montalbán, and Robert Soare.

He held an NSF Postdoctoral Fellowship at the University of Notre Dame and the University of California, Berkeley, before joining the Department of Mathematics at the University of Connecticut, where he is Associate Director of the Connecticut Group in Philosophical and Mathematical Logic.

His research is in computability theory, reverse mathematics, effective combinatorics, and computable analysis. He has also worked on developing applications of logic to other disciplines, including philosophy of mathematics and cognitive science.