{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20628"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20628","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Hyperfinite transversal theory","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.","abstract_html":"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.","abstract_has_math":true,"creators":["Zivaljevic, Bosko T."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:44:43Z","date_published":"2011-05-07T12:44:43Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Mathematics"],"languages":["eng"],"rights":["Copyright 1989 Zivaljevic, Bosko T."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9011091","(UMI)AAI9011091"],"render_values":[{"text":"AAI9011091","href":null,"code":true},{"text":"(UMI)AAI9011091","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20628","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Zivaljevic, Bosko T."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:44:43Z","10000-01-01","1989"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Zivaljevic, Bosko T."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9011091","(UMI)AAI9011091","http://hdl.handle.net/2142/20628"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.\"","Made available in DSpace on 2011-05-07T12:44:43Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9011091.pdf: 6005476 bytes, checksum: 96691122b2ef98806c231ce450de7a3b (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:11Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:19:59-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Hyperfinite transversal theory"]}]}],"canonical_facts":{"dc:creator":["Zivaljevic, Bosko T."],"dc:date":["2011-05-07T12:44:43Z","10000-01-01","1989"],"dc:description":["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.\"","Made available in DSpace on 2011-05-07T12:44:43Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9011091.pdf: 6005476 bytes, checksum: 96691122b2ef98806c231ce450de7a3b (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:11Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:19:59-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9011091","(UMI)AAI9011091","http://hdl.handle.net/2142/20628"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Zivaljevic, Bosko T."],"dc:subject":["Mathematics"],"dc:title":["Hyperfinite transversal theory"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:16Z"}