Date on Master's Thesis/Doctoral Dissertation

8-2023

Document Type

Doctoral Dissertation

Degree Name

Ph. D.

Department

Mathematics

Degree Program

Applied and Industrial Mathematics, PhD

Committee Chair

Kezdy, Andre

Committee Co-Chair (if applicable)

Powers, Robert

Committee Member

Powers, Robert

Committee Member

Wildstrom, David

Committee Member

Williger, Gerard

Author's Keywords

reinforcement learning; Ramsey graphs; Trahtenbrot-Zykov problem; constant link; Cayley graphs; undecidable problem

Abstract

Attempts at approaching the well-known and difficult problem of constructing Ramsey graphs via machine learning lead to another difficult problem posed by Zykov in 1963 (now commonly referred to as the Trahtenbrot-Zykov problem): For which graphs F does there exist some graph G such that the neighborhood of every vertex in G induces a subgraph isomorphic to F? Chapter 1 provides a brief introduction to graph theory. Chapter 2 introduces Ramsey theory for graphs. Chapter 3 details a reinforcement learning implementation for Ramsey graph construction. The implementation is based on board game software, specifically the AlphaZero program and its success learning to play games from scratch. The chapter ends with a description of how computing challenges naturally shifted the project towards the Trahtenbrot-Zykov problem. Chapter 3 also includes recommendations for continuing the project and attempting to overcome these challenges. Chapter 4 defines the Trahtenbrot-Zykov problem and outlines its history, including proofs of results omitted from their original papers. This chapter also contains a program for constructing graphs with all neighborhood-induced subgraphs isomorphic to a given graph F. The end of Chapter 4 presents constructions from the program when F is a Ramsey graph. Constructing such graphs is a non-trivial task, as Bulitko proved in 1973 that the Trahtenbrot-Zykov problem is undecidable. Chapter 5 is a translation from Russian to English of this famous result, a proof not previously available in English. Chapter 6 introduces Cayley graphs and their relationship to the Trahtenbrot-Zykov problem. The chapter ends with constructions of Cayley graphs Γ in which the neighborhood of every vertex of Γ induces a subgraph isomorphic to a given Ramsey graph, which leads to a conjecture regarding the unique extremal Ramsey(4, 4) graph.

Download

Share

COinS