MATH 793H. SPTP: Injective Choice Functions.

Credit Hours: 
Semester Offered: 
Comments From Graduate Director: 
The goal is to prove the following result for arbitrary bipartite graphs without any cardinality restrictions. This result is a generalization of K├Ânig's Theorem which has the same statement but is restricted to finite bipartite graphs. Theorem (Aharoni): For every bipartite graph there exists an independent set of edges and a vertex cover containing exactly one vertex of each edge. The algebra content of this course will concern ideals in boolean rings, and in particular the nonstationary ideal in the boolean ring consisting of all subsets of a regular cardinal number. The operation of multiplication in such a ring is the intersection and the operation of addition is the symmetric difference. The course will include introduction to ordinal and cardinal numbers. For Ph.D. students, this course would be suitable as part of a minor or major in either Algebra or Discrete Mathematics.