Hyperfinite transversal theory

A famous theorem of P. Hall gives a necessary and sufficient condition for a bipartite graph $\Gamma$ to possess a matching f. (A bipartite graph $\Gamma$ is a subset of the cartesian product of two finite sets X and Y. A matching f of $\Gamma$ is a 1-1 function f which is a subset of $\Gamma$ and which has the same domain as $\Gamma$.) The graph $\Gamma$ can be thought of as a finite family of finite sets $\{\Gamma(x) : {x}{\in}{X})\}$. Thus, the existence of a matching of $\Gamma$ is equivalent to the existence of a system of distinct representatives of the corresponding family of finite sets, i.e., to the existence of an injective choice function of the family $\{\Gamma(x) : {x}{\in}{X})\}$. The part of Graph Theory which deals with refinements and variants of P. Hall's theorem is called Transversal Theory.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Zivaljevic, Bosko T.

• Mathematics

Statement dc:rights

• Copyright 1989 Zivaljevic, Bosko T.

Language dc:language

eng

Identifier

AAI9011091
(UMI)AAI9011091

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/20628