scientific article; zbMATH DE number 1303203
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].
- Recursive combinatorial structures: enumeration, probabilistic analysis and random generation
- The combinatorialization of linear recurrences
- A Survey of Problems in Combinatorial Number Theory
- On solutions to a general combinatorial recurrence
- On an extension of a recurrent relation from combinatorics
- Recurrent combinatorial sums and binomial-type theorems
- scientific article; zbMATH DE number 749926
- scientific article; zbMATH DE number 1409903
- A Selection of Problems and Results in Combinatorics
- Introduction to enumerative combinatorics
- The complexity of optimization problems
- On the strength of König's duality theorem for infinite bipartite graphs
- Generalizations of Opt P to the polynomial hierarchy
- Handbook of recursive mathematics. Vol. 2: Recursive algebra, analysis and combinatorics
- Index sets for ^0_1 classes
- Ramsey degrees of bipartite graphs: a primitive recursive proof
- Undecidability of equality for codata types
- On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
- Forbidden substructures and combinatorial dichotomies: WQO and universality
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Combinatorics in ZFC limbo
- Domatic partitions of computable graphs
- One query reducibilities between partial information classes
- Slicing the truth. On the computable and reverse mathematics of combinatorial principles
- Subrecursive Complexity of Identifying the Ramsey Structure of Posets
- scientific article; zbMATH DE number 3900785 (Why is no real title available?)
- Reverse Mathematics and Recursive Graph Theory
- scientific article; zbMATH DE number 4118364 (Why is no real title available?)
- scientific article; zbMATH DE number 749926 (Why is no real title available?)
- Regular separability of well-structured transition systems
- Computing planarity in computable planar graphs
- Foundations of online structure theory. II: The operator approach
- Graph Ramsey theory and the polynomial hierarchy
- Recursively defined combinatorial functions: Extending Galton's board
- Primitive recursive reverse mathematics
- Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
- Recursive-combinatorial properties of subsets of the natural numbers
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249726)
