Feasible combinatorial matrix theory

We show that the well-known Konig's Min-Max Theorem (KMM), a fundamental result in combinatorial matrix theory, can be proven in the first order theory $\LA$ with induction restricted to $Σ_1^B$ formulas. This is an improvement over the standard textbook proof of KMM which requires $Π_2^B$ induction, and hence does not yield feasible proofs --- while our new approach does. $\LA$ is a weak theory that essentially captures the ring properties of matrices; however, equipped with $Σ_1^B$ induction $\LA$ is capable of proving KMM, and a host of other combinatorial properties such as Menger's, Hall's and Dilworth's Theorems. Therefore, our result formalizes Min-Max type of reasoning within a feasible framework.

No reviews yet.

No comments yet.