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 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. 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. |