The equivalence of maximal matching and maximal independent matching
Let denote the maximal matching principle and let denote the maximal independent matching principle, both formulated over . Let denote the perfect matching principle.
The computational-strength conjecture. and are equivalent over , i^1_1\text{-}\mathsf{TR}}_0 proves , and i^1_2\text{-}\mathsf{CA}}_0 proves .
These assertions compare the reverse-mathematical strength of matching principles. The source presents them as a conjectural computational-strength statement; the supplied status is unknown.
References
Primary source
Stephen Flood, Matthew Jura, Oscar Levin and Tyler Markkanen, “The computational strength of matchings in countable graphs”, arXiv:2006.11334 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.