A topological method in matching theory
21/11/2008 Sexta-feira, 21 de Novembro de 2008, 15h30, Anfiteatro
Ron Aharoni
(Technion-Israel Institute of Technology, Israel)
A "marriage" in a bipartite graph is an injective function contained in the edge set of the graph. Hall's classical "marriage theorem" gives a necessary and sufficient condition for the existence of a marriage. A topological proof of the theorem turns out to be particulary productive, yielding a more general marriage theorem, in which the range of the injective function can be required to belong to some simplicial complex (=closed down hypergraph).
|