In order to fully understand the basis of our project, here is some basic background information and definitions. These definitions are necessary in understanding graph theory and Ramsey Numbers.

Definitions

• Graph: A finite set of dots (called nodes or vertices) connected by links (called edges or arcs). Throughout our project, we use somewhat non-standard notation and may also refer to a graph as a map. There is no difference between these two terms.
  
  
  
  Examples of graphs.
  Sources:
  http://www.utm.edu/departments/math/graph/glossary.html
  http://www.stephanspencer.com
  http://www.math.fau.edu
  
  
  
• Node or Vertex: The “dots” in a graph that are connected by edges
• Edge or Arc: The connections between different nodes
• Complete graph: A complete graph is one such that each of its n vertices is connected to each of the other points
  
  
  
  The first 5 complete graphs.
  Source:
  http://www.utm.edu/departments/math/graph/glossary.html
  
  
  
• Subgraph: A graph that contains a certain set of nodes that are contained in the original graph with all of the edges between the nodes of the subgraph.
  
  
  
  The second graph is a subgraph of the first graph.
  Source:
  http://www.math.fau.edu
  
  
  
• Ramsey Numbers: A part of graph theory where there are independent variables b and r. The Ramsey number for those independent variables is the minimum number n such that any coloring of a K_n with each edge colored either red or blue will have a complete, monochromatic subgraph colored all blue with b nodes or colored all red with r nodes. This is a representation of the classic “party problem” which tries to determine the minimum number of people such that there are b people who all know each other or r people who all do not know each other.
  
  
  
  Solving for an R(3,3) using traditional methods.
  Source:
  http://www.cs.ucsb.edu/~rich/class/cs290I-grid/notes/Ramsey/index.html

---

Notation

• K_n: A complete graph with n nodes
• R(r, b) = n: The function that returns the Ramsey number n. The r and b denote the size of the mono-colored subgraphs that are to be used (r is used to mean red while b is used to mean blue). Note that a R(r, b) = R(b, r) because the only difference is that the colors are reversed, but the same values are being used.

---

Background on Ramsey Numbers and the Project

The reason why we choose this project is that it is a relatively new topic in mathematical history (it is only about 75 years old) and is also a relatively unexplored topic; to date, there has not been a very large effort by the mathematical community to calculate these numbers, possibly because of the extreme complexity for high values of inputs r and b. As you can see from Appendix C, many Ramsey number variables have not been solved for. Therefore, we decided to choose this problem to see if we could make a small yet significant contribution to the mathematical community that future researchers could use as part of a more intensive project to reduce the complexity of calculating Ramsey numbers for larger values of r and b. We also realized that a project to calculate Ramsey umbers would easily lends itself directly to a computer-based solution as it is only pure mathematics that is going on. There are no random occurrences and no variables that might make the computer model different from a real life model.

Ramsey numbers have a plethora of theoretical applications. While many of those applications are purely mathematical, many others connect to fields like communications, computer network security, telecommunications, theoretical computer science, and nearly anything that deals with networking.

One of the interesting applications where Ramsey numbers could be used is network security. Suppose a network administrator has a certain number of computers. In this network, every pair of computers either has a connection between them or they do not have a connection. The network administrator wants to achieve a balance of security and networking. To improve security, no set of b number of computers may all be connected at once since fewer connections will allow for less of a chance of a virus spreading or for information being sent when it should not. However, productivity must still continue at an adequate pace and therefore no set of r number of computers may be completely unconnected. This is related to Ramsey numbers since connections between computers could be represented by red edges and absent connections between computers could be represented by blue edges. Now the problem is turned into a Ramsey number problem looking at R(b,r). Therefore, if the network administrator knows what the Ramsey number is for an R(b,r), then he can determine if a network with his parameters may be created with the number of computers that are inside of the network. If R(b,r) is greater than the number of computers in the network, then there is a way to network the computers together under those parameters and a program could figure out possible ways to connect the computers. If R(b,r) is less than or equal to the number of computers that are being networked, there will be no way to avoid breaking one of those parameters. Therefore, Ramsey numbers have a theoretical application in network security, among other fields.