Finding Order in Chaos: The Construction and Properties of the Graph R(5)

Ramsey theory is built around a striking idea: in a large enough system, patterns become unavoidable. Even if connections are arranged randomly or designed to avoid structure order eventually appears simply because the network is so large and interconnected. One classic way to study this phenomenon is through graphs, which are networks made of vertices (points) and edges (connections). In this project, we explored a famous Ramsey-type problem related to the search for a graph that avoids two opposite extremes: a set of five vertices where every pair is connected (a 5-clique) and a set of five vertices where no connections occur (an independent set of size five). Graphs that avoid both patterns offer insight into the boundary between randomness and guaranteed structure. Our approach centered on self-complementary graphs, which are graphs that remain structurally similar even after taking the complement graph, where connections become non-connections and non-connections become connections. These graphs are especially interesting because they naturally balance the “connected” and “disconnected” sides of Ramsey-type conditions. To investigate these constructions, we combined mathematical reasoning with large-scale computation. Using a Java-based algorithm, we generated extensive collections of potentially self-complementary degree sequences, which describe how many connections each vertex has and help narrow down which graphs are possible. We then refined and filtered these sequences to focus on candidates relevant to the 45-vertex setting. Next, using computational tools including Python and Nauty, we generated graphs from these candidates and tested both the graphs and their complements for forbidden clique patterns. This workflow supported an efficient search process and helped highlight structural features that promising candidates would likely need to have. Overall, this project demonstrates how computation can support theoretical mathematics by enabling systematic exploration of rare graph structures and guiding future investigation of Ramsey-type constructions.