No label defined (Q4249726)

Many theorems in combinatorics have the following structure: for every object \(A\) in a class there is an object \(B\) having a property \(P\) (for example, König's lemma states that any infinite unbounded tree \(T\) has an infinite branch). Typically, the existence of \(B\) is proved non-constructively. The present survey considers some classical results of the above type and reviews for each of them what is known regarding the following questions: (a) Is the recursive analogue true? (b) Is some modification of the recursive analogue true? (c) How hard is it in the arithmetical hierarchy to determine if a given instance of the theorem has a recursive solution? The combinatorial problems considered in detail (with the presentation of most proofs) are: König's lemma, Ramsey's theorem, the colorings of infinite graphs, Hall's theorem on bipartite graphs, and Dilworth's theorem for partial orders. The recursive aspects of some other combinatorics results are surveyed without proofs. For the entire collection see [Zbl 0905.03002].