The computational strength of matchings in countable graphs

DOI10.1016/j.apal.2022.103133OpenAlexW3036418308WikidataQ114202053 ScholiaQ114202053MaRDI QIDQ2672158

Matthew Jura, Oscar Levin, Tyler Markkanen, Stephen Flood

Publication date: 8 June 2022

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.11334

zbMATH Keywords

computability theoryreverse mathematicsgraph matching

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Computability and recursion theory (03D99) Recursive ordinals and ordinal notations (03F15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
• Matchings in infinite graphs
• On the strength of König's duality theorem for infinite bipartite graphs
• Computable structures and the hyperarithmetical hierarchy
• Embeddings between well-orderings: computability-theoretic reductions
• Completion of choice
• Reverse mathematics and marriage problems with unique solutions
• Matchings in Countable Graphs
• On the strength of König's duality theorem for countable bipartite graphs
• Weihrauch Complexity in Computable Analysis
• Partial impredicativity in reverse mathematics
• SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE

This page was built for publication: The computational strength of matchings in countable graphs