Files in this item
Files  Description  Format 

application/pdf 9011091.pdf (6MB)  (no description provided) 
Description
Title:  Hyperfinite transversal theory 
Author(s):  Zivaljevic, Bosko T. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  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 11 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. In our setting Hall's type result are proved in the case when the sets X and Y are considered to be Loeb measurable sets with respect to some uniformly distributed hyperfinite counting measure. Hall's condition is replaced by its measure theoretic analogue and for the graph $\Gamma$ we use sets of different "complexity" (in the sense of Descriptive Set Theory). At the same time the choice function, i.e., the matching in the statement of Hall's theorem, is required to be of "nice" structure, that is we ask that the function be internal. The terminology is likewise adjusted to the measure case situation. Accordingly, a matching need not have its domain equal to the domain of the graph, as was asked in the conclusion of the discrete case of Hall's theorem, but, rather, the domain of the matching should be of full measure in the domain of the graph. 
Issue Date:  1989 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/20628 
Rights Information:  Copyright 1989 Zivaljevic, Bosko T. 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9011091 
OCLC Identifier:  (UMI)AAI9011091 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics