Date: September 18, 1992

Title: On the Strength of K"onig's Duality Theorem
       for Countable Bipartite Graphs

Author: Stephen G. Simpson

Definitions: A bipartite graph is an ordered triple (X,Y,E) such that
X and Y are disjoint sets and E is a subset of {{x,y}:x in X, y in Y}.
The vertices are the elements of X union Y.  The edges are the
elements of E.  A covering is a set of vertices which meets every
edge.  A matching is a pairwise dijoint set of edges.

History: K"onig's duality theorem says that, for every finite
bipartite graph, the minimum cardinality of a covering is equal to the
maximum cardinality of a matching.  This is proved by showing that for
every finite bipartite graph there exists a K"onig covering, i.e. an
ordered pair (C,M) such that C is a covering, M is a matching, and C
consists of exactly one vertex from each edge in M.  Podewski and
Steffens showed that every countably infinite bipartite graph has a
K"onig covering.  Aharoni proved the same result for uncountable
bipartite graphs.  Aharoni, Magidor, and Shore (Journal of
Combinatorial Theory (B), 54, 1992, 257-290) studied the following
logical or foundational question: Which set existence axioms are
needed to prove the Podewski-Steffens theorem and Aharoni's theorem?
They showed that the Podewski-Steffens theorem logically implies the
axioms of ATR_0, this implication being provable in RCA_0.  (Here
ATR_0 is the subsystem of second order arithmetic with arithmetical
transfinite recursion and restricted induction, and RCA_0 is the
subsystem of second order arithmetic with recursive comprehension and
restricted induction.)

New results: We show that the Podewski-Steffens theorem is provable in
ATR_0.  This solves a problem stated by Aharoni, Magidor and Shore.
Combining our result with theirs, we see that the Podewski-Steffens
theorem is logically equivalent to the principal axiom of ATR_0, this
equivalence being provable in RCA_0.  Thus ATR_0 is the weakest
natural subsystem of second order arithmetic in which the
Podewski-Steffens theorem is provable.

Author email: simpson@math.psu.edu
Available: http://math.psu.edu/simpson/papers/bipartite.ps
Format: PostScript (AMS-LaTeX source is also available)
Publication: Journal of Symbolic Logic, vol. 59, 1994, pp. 113-123.