서브메뉴
검색
Borel Graphs: Measurable Consequences of Their Geometry and Complexity of Labeling Problems
Borel Graphs: Measurable Consequences of Their Geometry and Complexity of Labeling Problems
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202104645
- ISBN
- 9798280757691
- DDC
- 510
- 서명/저자
- Borel Graphs: Measurable Consequences of Their Geometry and Complexity of Labeling Problems
- 발행사항
- [Sl] : University of California, Los Angeles, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 64 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-12, Section: B.
- 주기사항
- Advisor: Marks, Andrew;Bernshteyn, Anton.
- 학위논문주기
- Thesis (Ph.D.)--University of California, Los Angeles, 2025.
- 초록/해제
- 요약This dissertation investigates Borel graphs on Polish spaces. It explores two main directions: the relationship between a Borel graph's geometry and its measurable properties, and the projective complexity of labeling problems in Borel combinatorics.Chapter 2 contains joint work with Clark Lyons on the Baire measurable combinatorics of Borel graphs with non-amenable connected components. In this setting, we show that a Baire measurable perfect matching exists when the graph is vertex transitive, and that a Baire measurable balanced orientation exists when all degrees are even.Chapter 3 presents a proof that Borel graphs of subexponential growth are measure hyperfinite, and includes a discussion of recent advances concerning hyperfiniteness under growth rate constraints.Chapter 4 introduces a problem of Kechris and Chen about the σ-structurability of compressible countable Borel equivalence relations. We provide a proof in non-probabilistic language that a locally finite vertex transitive connected graph has a realization as a probability-measure-preserving graph if and only if it is unimodular. We also generalize this result to the case of countable relational structures with compact stabilizers.Chapter 5 explores the projective complexity of characterizing which Borel graphs admit Borel solutions to labeling problems. We introduce a formal notion of gadget reduction and use this notion to lift NP-completeness results in finite combinatorics to Σ12 -completeness results for their Borel analogues. We then give several concrete examples where this idea is applied.Chapter 6 contains joint work with Clark Lyons to provide a classical proof that for a Borel family of games, the set of games where player II wins is Baire measurable, universally measurable, and Ramsey measurable.
- 일반주제명
- Mathematics
- 일반주제명
- Theoretical mathematics
- 키워드
- Borel graphs
- 키워드
- Geometry
- 키워드
- Complexity
- 기타저자
- University of California, Los Angeles Mathematics 0540
- 기본자료저록
- Dissertations Abstracts International. 86-12B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017358328
■00520260202104645
■006m o d
■007cr#unu||||||||
■020 ▼a9798280757691
■035 ▼a(MiAaPQ)AAI32114497
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a510
■1001 ▼aKastner, Alexander Sebastien.
■24510▼aBorel Graphs: Measurable Consequences of Their Geometry and Complexity of Labeling Problems
■260 ▼a[Sl]▼bUniversity of California, Los Angeles▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a64 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-12, Section: B.
■500 ▼aAdvisor: Marks, Andrew;Bernshteyn, Anton.
■5021 ▼aThesis (Ph.D.)--University of California, Los Angeles, 2025.
■520 ▼aThis dissertation investigates Borel graphs on Polish spaces. It explores two main directions: the relationship between a Borel graph's geometry and its measurable properties, and the projective complexity of labeling problems in Borel combinatorics.Chapter 2 contains joint work with Clark Lyons on the Baire measurable combinatorics of Borel graphs with non-amenable connected components. In this setting, we show that a Baire measurable perfect matching exists when the graph is vertex transitive, and that a Baire measurable balanced orientation exists when all degrees are even.Chapter 3 presents a proof that Borel graphs of subexponential growth are measure hyperfinite, and includes a discussion of recent advances concerning hyperfiniteness under growth rate constraints.Chapter 4 introduces a problem of Kechris and Chen about the σ-structurability of compressible countable Borel equivalence relations. We provide a proof in non-probabilistic language that a locally finite vertex transitive connected graph has a realization as a probability-measure-preserving graph if and only if it is unimodular. We also generalize this result to the case of countable relational structures with compact stabilizers.Chapter 5 explores the projective complexity of characterizing which Borel graphs admit Borel solutions to labeling problems. We introduce a formal notion of gadget reduction and use this notion to lift NP-completeness results in finite combinatorics to Σ12 -completeness results for their Borel analogues. We then give several concrete examples where this idea is applied.Chapter 6 contains joint work with Clark Lyons to provide a classical proof that for a Borel family of games, the set of games where player II wins is Baire measurable, universally measurable, and Ramsey measurable.
■590 ▼aSchool code: 0031.
■650 4▼aMathematics
■650 4▼aTheoretical mathematics
■653 ▼aBorel graphs
■653 ▼aGeometry
■653 ▼aComplexity
■653 ▼aLabeling problems
■653 ▼aSubexponential growth
■690 ▼a0405
■690 ▼a0642
■71020▼aUniversity of California, Los Angeles▼bMathematics 0540.
■7730 ▼tDissertations Abstracts International▼g86-12B.
■790 ▼a0031
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358328▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
