The computational content of Koenig's duality theorem
Abstract: Koenig's theorem states that, in any finite bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover. The generalization of Koenig's theorem to infinite graphs is known as Koenig's duality theorem (KDT). We investigate the computational content of KDT for countable graphs. In particular, we show that it is closely connected to pseudohierarchies, which are nonstandard versions of the H-sets from hyperarithmetic theory.