서브메뉴
검색
Measurable Brooks's Theorem for Directed Graphs and the Complexity of Finite Borel Asymptotic Dimension
Measurable Brooks's Theorem for Directed Graphs and the Complexity of Finite Borel Asymptotic Dimension
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202105139
- ISBN
- 9798293815982
- DDC
- 510
- 서명/저자
- Measurable Brookss Theorem for Directed Graphs and the Complexity of Finite Borel Asymptotic Dimension
- 발행사항
- [Sl] : University of California, Los Angeles, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 102 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-03, Section: B.
- 주기사항
- Advisor: Marks, Andrew;Bernshteyn, Anton.
- 학위논문주기
- Thesis (Ph.D.)--University of California, Los Angeles, 2025.
- 초록/해제
- 요약This dissertation concentrates on two prominent lines of research in modern descriptive set theory: Descriptive combinatorics and the theory of definable equivalence relations.Chapter 2 is focused on a body of results related to Brooks's theorem, a fundamental graph theory result that characterizes the graphs of maximum degree d having chromatic number at most d. Measurable versions of Brooks's theorem, as well as definable versions of a similar result on list coloring known as Gallai's theorem, are surveyed in Section 2.2. Classical results that extend Brooks's theorem and Gallai's theorem to directed graphs are also discussed in Section 2.3. The chapter culminates in the proofs of both a definable version of Gallai's theorem for directed graphs and a measurable version of Brooks's theorem for directed graphs in Section 2.4. In the final two sections, potential connections with Johansson's theorem and the theory of LOCAL algorithms are explored.Chapter 3 contains joint work with Jan Grebik on the projective complexity of finite Borel asymptotic dimension. The chapter begins with an overview of the study of countable Borel equivalence relations, followed by a survey of open problems related to the well-known question of whether the set of Borel codes of hyperfinite equivalence relations is Σ1/2 -complete. An overview of Borel asymptotic dimension and the role it plays in the study of hyperfiniteness is provided in Sections 3.3 and 3.4. The main theorem that the set of Borel codes of locally finite Borel graphs having finite Borel asymptotic dimension is Σ1/2 -complete is described in Section 3.5. The chapter concludes with a brief section concerning potential extensions to the study of Borel semigroup actions.
- 일반주제명
- Mathematics
- 일반주제명
- Logic
- 일반주제명
- Theoretical mathematics
- 키워드
- Combinatorics
- 키워드
- Graph theory
- 기타저자
- University of California, Los Angeles Mathematics 0540
- 기본자료저록
- Dissertations Abstracts International. 87-03B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017359573
■00520260202105139
■006m o d
■007cr#unu||||||||
■020 ▼a9798293815982
■035 ▼a(MiAaPQ)AAI32240546
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a510
■1001 ▼aHiggins, Cecelia.
■24510▼aMeasurable Brooks's Theorem for Directed Graphs and the Complexity of Finite Borel Asymptotic Dimension
■260 ▼a[Sl]▼bUniversity of California, Los Angeles▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a102 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-03, Section: B.
■500 ▼aAdvisor: Marks, Andrew;Bernshteyn, Anton.
■5021 ▼aThesis (Ph.D.)--University of California, Los Angeles, 2025.
■520 ▼aThis dissertation concentrates on two prominent lines of research in modern descriptive set theory: Descriptive combinatorics and the theory of definable equivalence relations.Chapter 2 is focused on a body of results related to Brooks's theorem, a fundamental graph theory result that characterizes the graphs of maximum degree d having chromatic number at most d. Measurable versions of Brooks's theorem, as well as definable versions of a similar result on list coloring known as Gallai's theorem, are surveyed in Section 2.2. Classical results that extend Brooks's theorem and Gallai's theorem to directed graphs are also discussed in Section 2.3. The chapter culminates in the proofs of both a definable version of Gallai's theorem for directed graphs and a measurable version of Brooks's theorem for directed graphs in Section 2.4. In the final two sections, potential connections with Johansson's theorem and the theory of LOCAL algorithms are explored.Chapter 3 contains joint work with Jan Grebik on the projective complexity of finite Borel asymptotic dimension. The chapter begins with an overview of the study of countable Borel equivalence relations, followed by a survey of open problems related to the well-known question of whether the set of Borel codes of hyperfinite equivalence relations is Σ1/2 -complete. An overview of Borel asymptotic dimension and the role it plays in the study of hyperfiniteness is provided in Sections 3.3 and 3.4. The main theorem that the set of Borel codes of locally finite Borel graphs having finite Borel asymptotic dimension is Σ1/2 -complete is described in Section 3.5. The chapter concludes with a brief section concerning potential extensions to the study of Borel semigroup actions.
■590 ▼aSchool code: 0031.
■650 4▼aMathematics
■650 4▼aLogic
■650 4▼aTheoretical mathematics
■653 ▼aCombinatorics
■653 ▼aDescriptive set theory
■653 ▼aGraph theory
■690 ▼a0405
■690 ▼a0395
■690 ▼a0642
■71020▼aUniversity of California, Los Angeles▼bMathematics 0540.
■7730 ▼tDissertations Abstracts International▼g87-03B.
■790 ▼a0031
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17359573▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
