Jan Severin Reimann, Thesis Supervisor Victoria V Sadovskaya, Thesis Honors Advisor
Keywords:
math Ramsey theory combinatorics
Abstract:
Ramsey theory is concerned with the question: Given two graphs G_1 and G_2, how large does n have to be so that any two coloring of K_n, the complete graph on n vertices, with red and blue either contains a red G_1 or a blue G_2 subgraph? This number is denoted as the Ramsey number for G_1 and G_2, notationally written as R(G_1,G_2). Any graph can be represented as an adjacency matrix. Using matrix norms such as the edit norm and the cut norm, we can define a meaningful notion of distance between two graphs. We investigate Ramsey numbers for subgraphs which are a certain distance away from a complete graph using the edit norm and the cut norm.