The equivalence of maximal matching and maximal independent matching
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.