Definable combinatorics in descriptive set theory, computability theory, and beyond

This thesis is about finding solutions to combinatorial problems on graphs such as proper coloring or perfect matching in the presence of extra definability constraints. For  example,  we  might  ask  that  a  coloring  of  a  graph  on  the  natural  numbers  be computable, or that a coloring of a graph on the real numbers be measurable, or that a coloring of a finite graph be presented by some efficient algorithm. 

We give new positive and negative results on the existence of such solutions for several natural problems, but especially those related to edge colorings and matchings. 

Furthermore, we consider these problems in the abstract, and prove several theorems relating the existence of solutions in one setting to the existence of solutions in another.  This has been an active area of research in the last few years, but our work is among the first to include the computable setting in this discussion.