Topological methods in matching theory.

摘要

The use of topological methods in matching theory has proven lately to be very fruitful. In this thesis we address several problems in matching theory, apply topological methods to them and compare the result obtained through topological methods to those obtained through combinatorial methods.; In this work we study the Knaster-Kuratowski-Mazurkiewicz (KKM) theorem, a powerful tool in many areas of mathematics, introduce a version of the KKM theorem for trees and use it to prove several combinatorial theorems.; A 2-tree hypergraph is a family of nonempty subsets of T ∪ R (where T and R are trees), each of which has a connected intersection with T and with R.; For each such hypergraph H we denote by tau( H) the minimal cardinality of a set intersecting all sets in the hypergraph and by nu(H) the maximal number of disjoint sets in it.; The methods developed in this work will allow us to prove that in a 2-tree hypergraph tau(H) ≤ 2nu(H).; Another classical theorem studied in this work is Edmonds' theorem that provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a "covering" parameter. We generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the case r = 3 of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter---the maximal number of disjoint sets, all spanning in each of two given matroids.