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

DOI10.2307/2275254MaRDI QIDQ4292597zbMATH OpenOpenAlexFDO

Authors Stephen G. Simpson

Publication date 3 November 1994

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275254

zbMATH Keywords

countably infinite bipartite graphmatchingrecursive comprehensionreverse mathematicssubsystem of second-order arithmeticvertex covering

Mathematics Subject Classification ID

Second- and higher-order arithmetic and fragments (03F35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Recommendations

• On the strength of König's duality theorem for infinite bipartite graphs
• scientific article; zbMATH DE number 4185652
• scientific article; zbMATH DE number 671722
• Duality for finite bipartite graphs (with an application to II\(_ 1\) factors)
• Density theorems for bipartite graphs and related Ramsey-type results
• Bounds for the Kirchhoff index of bipartite graphs
• scientific article; zbMATH DE number 6766028
• scientific article; zbMATH DE number 5130735
• Couterexample to a conjecture on the structure of bipartite partionable graphs
• On the Bollobás–Eldridge Conjecture for Bipartite Graphs

Cites work

• Borel quasi-orderings in subsystems of second-order arithmetic
• scientific article; zbMATH DE number 4063093 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Injective choice functions for countable families
• On the strength of König's duality theorem for infinite bipartite graphs
• Patras Logic Symposion. Proceedings of the Logic Symposion held at Patras, Greece, August 18--22, 1980

Cited in

(12)

• On the strength of König's duality theorem for infinite bipartite graphs
• Formalizing forcing arguments in subsystems of second-order arithmetic
• The computational strength of matchings in countable graphs
• 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
• Reverse mathematics: the playground of logic
• Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
• The model-theoretic ordinal analysis of theories of predicative strength
• A Model-Theoretic Approach to Ordinal Analysis
• Computing maximal chains
• Ordinals and graph decompositions
• On the relationship between ATR₀ and
• Halin's infinite ray theorems: complexity and reverse mathematics

This page was built for publication: On the strength of König's duality theorem for countable bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4292597)