On the strength of König's duality theorem for infinite bipartite graphs

DOI10.1016/0095-8956(92)90057-5zbMath0754.05053OpenAlexW2065601606MaRDI QIDQ1193566

Menachem Magidor, Richard A. Shore, Ron Aharoni

Publication date: 27 September 1992

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(92)90057-5

zbMATH Keywords

computational complexitycompactnessbipartite graphscoverTuring jumpmaximality propertyKönig's duality theorem

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Second- and higher-order arithmetic and fragments (03F35) Axiom of choice and related propositions (03E25) Relative consistency and interpretations (03F25) Hierarchies of computability and definability (03D55)

Related Items

Reverse Mathematics: The Playground of Logic ⋮ ON THE UNCOUNTABILITY OF ⋮ On the strength of König's duality theorem for countable bipartite graphs ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ The computational strength of matchings in countable graphs ⋮ Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\) ⋮ (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE ⋮ Computing maximal chains ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ Infinite matching theory ⋮ Matchings from a set below to a set above ⋮ Ordinals and graph decompositions ⋮ Hamiltonian paths in infinite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Schmerl's effective version of Brooks' theorem
• Harvey Friedman's research on the foundations of mathematics
• Proof theory. 2nd ed
• Matching theory
• Injective choice functions for countable families
• A theory of recursive dimension of ordered sets
• Strong transfinite version of König's duality theorem
• The Effective Version of Brooks' Theorem
• An Effective Version of Dilworth's Theorem
• Recursive Colorings of Graphs
• On a Duality Principle in Infinite Bipartite Graphs
• König's Duality Theorem for Infinite Bipartite Graphs
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory
• Injective choice functions