Feasible combinatorial matrix theory

DOI10.1007/978-3-642-40313-2_68MaRDI QIDQ2849961zbMATH OpenOpenAlexWikidataFDO

Authors Ariel Germán Fernández, Michael Soltys

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

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

zbMATH Keywords

\(\mathrm{VTC}^{0}\)LAmin-max principleproof complexity

Mathematics Subject Classification ID

Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Abstract: 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 $Sigm{a}_1^B$ formulas. This is an improvement over the standard textbook proof of KMM which requires $P{i}_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 $Sigm{a}_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.

Recommendations

• A short proof of K�nig's matching theorem
• König's theorem and bimatroids
• A generalization of a theorem of König
• New proofs of Konig-Egervary theorem and maximal flow-minimal cut capacity theorem using O.R. techniques
• Butterfly Embedding Proof of a Theorem of Konig

Cited in

(3)

• scientific article; zbMATH DE number 3852942 (Why is no real title available?)
• Butterfly Embedding Proof of a Theorem of Konig
• Combinatorial Matrix Theory

This page was built for publication: Feasible combinatorial matrix theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849961)