Good books combining recursion theory and combinatorics

Question

Are there any introductory texts available on mathematical recursion theory (i.e., not aimed at computer scientists) that include a good amount of applications to mathematical combinatorics or other areas of discrete math? For example, are there any that draw explicit connections with recurrence relations in combinatorics?

I haven't had much luck searching online.

Answer 1

There has been a great deal of work on combinatorics in computability theory. However, there is little on the subject in "introductory" books, such as books aimed at undergraduates or at readers who don't know the basics of computability theory already.

One recent graduate-level book on the subject is Slicing the Truth by Denis Hirschfeldt. He has an expository article with most of the content online as well.

Most of the work in this area is not in books, however, and is simply in research papers. A famous and exceptional older paper is "Ramsey's Theorem and Recursion Theory" by Carl Jockusch (J. Symb. Logic, 1972; doi: 10.2307/2272972, jstor). That might be a good starting point, for a reader who knows the basics of computability theory (such as the beginning parts of Soare's book). More modern papers worth reading include:

• "Logical analysis of some theorems of combinatorics and topological dynamics" by Blass, Hirst, and Simpson (Contemp. Math. 65, 1987)
• "On the strength of Ramsey's theorem for pairs" by Cholak, Jockusch, and Slaman (J. Symb. Logic, 2001)
• "On uniform relationships between combinatorial problems" by Dorais, Dzhafarov, Hirst, Mileti, and Shafer (Trans. AMS, 2016).