The equivalence of maximal matching and maximal independent matching

Let athsfMMathsf{MM} denote the maximal matching principle and let athsfMIMathsf{MIM} denote the maximal independent matching principle, both formulated over peratornameRCA0peratorname{\mathsf{RCA}}_0. Let athsfPMathsf{PM} denote the perfect matching principle.

The computational-strength conjecture. athsfMMathsf{MM} and athsfMIMathsf{MIM} are equivalent over peratornameRCA0peratorname{\mathsf{RCA}}_0, i^1_1\text{-}\mathsf{TR}}_0 proves athsfPMathsf{PM}, and i^1_2\text{-}\mathsf{CA}}_0 proves athsfMMathsf{MM}.

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

Never refreshed

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.