Below you will find pages that utilize the taxonomy term “Graph Theory”
Minimum Degrees of Minimal Ramsey Graphs for Almost-Cliques
Audrey Grinshpun, Raj Raina, and Rik Sengupta
Combinatorics is a field of mathematics that has always fascinated me. Specifically, graph theory, a branch of combinatorics, has always piqued my interest. In general, graph theory deals with the study of mathematical structures, modeled by vertices with edges connecting them. While these graphs can be very simple, they can also get exceedingly complicated in structure; indeed, there are very interesting properties we can say about these graphs. The field is both enormously complex as well as incredibly enlightening … In the summer of ninth grade, I had my first experience with graph theory at a summer math camp called PROMYS. There, I researched the invariant measures of graphs under arbitrary permutations of vertices. An invariant measure is a certain quality of a graph that is preserved by any permutation of the set of vertices. In that project, the question at hand was the following: given a graph G, what methods can be used to determine if the graph has an invariant measure? Furthermore, what constructions of this invariant measure are possible? This topic is of importance in several issues relating to network connectivity. By examining the invariant measures on graphs, one can relate the network connectivity of graphs under, say, arbitrary permutations (or any other measure) and show possible relatedness between structures …
On the Workday Number for Finite Multigraphs in a Variation of Cops and Robbers
Eric Schneider
Oftentimes, there are “bad guys” such as diseases, wildfires, or thieves that the “good guys” such as the CDC, firemen, or police wish to control or capture. However, the good guys only have a limited quantity of assets such as money, people, and time, so it is important for them to use the least amount of resources. One well-known way of analyzing such problems is known as “Cops and Robbers on a Graph”. I analyzed a different version of this model to find out how to minimize the cost (called the Workday Number) to catch the bad guys. I discovered how to compute a way to catch the bad guys in two days while still minimizing the cost … How did I come up with my research topic? During the proof-based power round of the national American Regions Mathematics League Competition (ARML), there was one problem which introduced and asked questions about the Workday Number. In answering it, I realized that I could combine the idea of flow networks from computer science with monovariants from my math experience to give bounds on the Workday number. Unknown to me at the time, the panel of judges, all mathematicians, had deliberated for over thirty minutes over the correctness of my solution. Although it appeared correct, and they could not find any holes in it, it simply did not match any of the official proofs that they had.