Down Arrow Ramsey Sets
Masters Thesis
This is the work done for my Masters thesis at Youngstown State University available here.
Collaborators
Dr. Alexis Byers (committee chair)
Dr. Anita O'Mellan
Dr. Alina Lazar
Abstract
A graph G is said to arrow a graph H if every red-blue edge coloring of G presents a monochromatic H, and is written G → H. The down-arrow Ramsey set reports all subgraphs H of a graph G for which G → H. Formally, the down-arrow Ramsey set is a graph G is ↓G:= {H ⊆ G: G → H}. Calculating this set by way of scientific computing is computationally prohibitive with the resources commonly available to graph theorists and other academics. Using existing research into complete graphs, the down-arrow Ramsey sets for small complete graphs (K_n for 2 ≤ n ≤ 7) can be generated quickly. For larger complete graphs (K_n for 8 ≤ n ≤ 11) specific pre-processing steps are leveraged to speed up calculations in addition to the existing research. Presented is work on the development of a Python script to generate the down-arrow Ramsey set of a graph through efficient memory management and parallel computing methodologies. The down-arrow generator is used to report new results on complete graphs as well as complete bipartite graphs, and assorted other graphs.
Masters of Science in Mathematics Thesis
Applying_Computational_Resources_to_the_Down_Arrow_Problem_Defense_Slides.pdfSpring meeting of the Ohio MAA
In preparation of my thesis defense, I spoke at the spring section meeting of the Ohio MAA meeting at Baldwin Wallace University on 31 March 2023. Due to time constraints, much of my work was truncated in this talk.
Applying_Computational_Resources_to_the_Down_Arrow_Problem_Slides.pdfPreliminaries
A simple, undirected, isolate-free graph is two sets: A vertex set, and an edge set. Edges are unordered pairs of vertices, and every vertex is contained in at least one edge.
We considered all graphs up to isomorphism.
A red-blue edge coloring is an assignment of each edge of a graph, either red or blue.
If every red-blue edge coloring of a graph induces either a red or a blue copy of a graph H, it is said that G arrows H (G → H).
Key Idea
The down-arrow Ramsey set of complete graphs up to K_8 are generated and shown to align with the body of knowledge that already exists. The down-arrow Ramsey set of complete bipartite graphs up to K_5,5 is generated, of which ↓K_5,5 is new to the literature. All fan graphs are classified which also adds to the literature. A few small graphs are also inspected, and the down-arrow Ramsey set of is given to the literature.