Ramsey Theory - Study Guide

Ramsey Theory Contents 1 Introduction 1.1 Ramsey Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Useful Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 2 History of Ramsey Theory 2.1 Van der Waerden’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Ramsey’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Contributions of Erdös . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5 5 6 3 Ramsey Numbers 3.1 Important Properties of Ramsey Numbers 3.2 Values for Ramsey Numbers . . . . . . . . 3.3 Proofs of Known Ramsey Numbers . . . . 3.3.1 R(1, k) = 1 . . . . . . . . . . . . . 3.3.2 R(2, k) = k . . . . . . . . . . . . . 3.3.3 R(3, 3) = 6 . . . . . . . . . . . . . 3.3.4 R(4, 4) = 18 . . . . . . . . . . . . . 3.4 A Real Example of Ramsey Numbers . . . . . . . . . . . 6 7 9 10 10 11 11 12 13 4 Bounds for R(k, k) 4.1 Initial Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Evolution of Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 14 16 5 A Computational Method 5.1 Representing Colorings of Compelete Graphs . . . . . . . . . . . . . . . . . . 5.2 Producing Adjacency Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Testing for Monochromatic Subgraphs . . . . . . . . . . . . . . . . . . . . . 17 18 18 19 6 Closing Thoughts 20 Appendices 21 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abstract Ramsey theory is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a specific size. This paper will explore some basic definitions of and history behind Ramsey theory, but will focus on a subsection of Ramsey theory known as Ramsey numbers. A discussion of what Ramsey numbers are, some examples of their relevance in real-life scenarios, and a computational method for determining Ramsey numbers will be provided in an attempt to create an accessible, easy to understand look at an interesting topic. Acknowledgements It takes an army to raise anything, so I want to spend some time expressing my appreciation for two groups of people who helped get this paper off the ground. 2 1 Introduction When beginning research for this topic, I came to an important realization that has shaped the writing of this paper. This thought is that my work does not have a strong likelihood of producing some new development in the field of Ramsey theory and more likely serves as an overview of work done in the past. As such, the contents of this paper will instead aim to create a discussion of Ramsey theory that is accessible to individuals with different backgrounds in mathematics. Whether through the use of visuals, aggregation of proofs and examples that I believe to be understandable or relatable, or the creation of a very general computational method for Ramsey numbers, my goal is to provide something that others can utilize as a introductory step to something more. Ramsey theory and Ramsey numbers will require new mathematicians or new ways of looking at things in order to make new discoveries, and sometimes the most important first step is a clear understanding of the basics. 1.1 Ramsey Theory All of the work in this paper falls under a category of mathematics known as Ramsey theory. There are two general definitions of Ramsey theory that provide a good context into what will be discussed later in this paper. A broader understanding is summarized by the idea that “Ramsey Theory deals with finding order amongst apparent chaos,” [4] while an explanation that is more apt for the focus of this paper is that Ramsey theory is based around the idea that “any structure will necessarily contain an orderly substructure.” [8] The former quotation appeals to the essence of Ramsey theory in that it is a field of mathematics emphasizing the appearance of order in things such as sequences, groups, or graphs. The latter is more suited to the majority of what this paper chooses to focus on, namely graphs of a certain order guaranteeing subgraphs of another order. 1.2 Useful Definitions Given that graph theory representations of Ramsey theory is going to be the most prevalent aspect of this paper, we will go over some basic definitions of some frequently used terms. Additionally, a brief explanation of the relevance of definitions will accompany each definition. Definition 1.1. A graph G = (V, E) is a set of vertices and edges, where V (G) and E(G) are the sets of vertices and edges in G, respectively. Because a lot of Ramsey theory utilizes graph theory, it’s important to establish a definition of a graph. Ramsey theory can also be applied to constructs such as groups or sequences, but nearly all of the focus in this paper will be on graph theory applications of Ramsey theory. Definition 1.2. A complete graph on n vertices, denoted Kn , is a graph in which every vertex is adjacent, or connected by an edge, to every other vertex in G. 3 Complete graphs are a specific type of graph that are utilized in aspects of Ramsey theory, namely in discussions of Ramsey’s Theorem and Ramsey numbers, both of which we will discuss later in more detail. Complete graphs have known properties that are useful for analyzing problems regarding these aspects of Ramsey theory. For example, Kn will have n−1 X i=0 i= n(n − 1) 2 edges, which are analyzed to determine Ramsey numbers. This can make the identification of Ramsey numbers extremely difficult, as the number of complete graphs to be analyzed can increase significantly with a small increase in n. Definition 1.3. A clique is a subset of vertices such that there exists an edge between any pair of vertices in that subset of vertices. This is equivalent to having a complete subgraph.[10]. Definition 1.4. An independent set of a graph is a subset of vertices such that there exists no edges between any pair of vertices in that subset [10]. Cliques and independent sets are important for a certain method of defining Ramsey’s Theory and Ramsey numbers. A large number of mathematicians choose to analyze graphs in this context; however this paper will explore the method of analysis that relies solely on complete graphs and edge colorings (see the following definition). Definition 1.5. Let C be a set of colors {c1 , c2 , ..., cm } and E(G) be the edges of a graph G. An edge coloring f : E → C assigns each edge in E(G) to a color in C. If an edge coloring uses k colors on a graph, then it is known as a k-colored graph. It’s worth noting that the most common use of the term “coloring” refers to coloring of vertices and in a similar fashion a k-colored graph is often thought of in terms of the number of colors assigned to the vertices in a given graph. However, for the purposes of this paper, every time the terms “colored” or k-colored graph are used they are being used in the context of edge colorings. This is because Ramsey theory often considers structures in terms of edges (hence the references to cliques and independent sets) as opposed to vertices. Finally, there will be additional definitions presented in the appropriate sections, but for now we have the fundamental building blocks that can be used to explain the majority of content in this paper. 2 History of Ramsey Theory Now that we are armed with at least a tentative understanding of what Ramsey theory is and have been provided with some basic definitions, it’s time to work talk about some specific work in Ramsey theory. To start, we’ll delve into a discussion of some of the key figures in early Ramsey theory and their work. 4 2.1 Van der Waerden’s Theorem One of the first mathematical theorems classified as part of Ramsey theory was produced by Dutch mathematician Bartel Leendert van der Waerden, who in 1927 published a paper that established the following theorem. Theorem 2.1 (Van der Waerden’s Theorem). For any p, s ∈ N, there is an N ∈ N such that for any partition of the set {1, 2, ..., N } into p sets there will be an arithmetic sequence of s terms. [7]. While this theorem will be offered without proof, it’s worth taking some time to run through an example of what this theorem implies. We note that the van der Waerden number W (p, s) is the smallest N value satisfying van der Waerden’s Theorem for the given p, s. With this in mind, we consider the known case W (2, 3) = 9. To to see how this works, consider the set {1, 2, 3, 4, 5, 6, 7, 8, 9} randomly partitioned it into two sets. Because W (2, 3) = 9, one of our two subsets will be guaranteed to contain three terms that form an arithmetic sequence. For example, in the partition {1, 2, 3, 4, 5, 6, 7, 8, 9} → {1, 3, 4, 6, 9} , {2, 5, 7, 8} , the subset {1, 3, 4, 6, 9} contains the arithmetic sequence 3, 6, 9. 2.2 Ramsey’s Theorem The naming fame of Ramsey theory goes to British mathematician Frank Plumpton Ramsey, who published a paper in 1928 with proof of what we now call Ramsey’s Theorem and other work which would be most easily classified as a part of Ramsey theory. Interestingly, Ramsey was involved in a variety of other disciplines, most notably economics. He worked with famous economist John Maynard Keynes and produced multiple papers which were still cited into the 1990s [8]. However, Ramsey sadly died in 1930 at the age of 26 after an illness and “complications from abdominal surgery.” [8] The main contribution Ramsey made was Ramsey Theorem, which has a variety of definitions depending on the context in which the theorem is intended to be used. For our purposes, we’re going to focus in on a specific version of Ramsey’s Theorem that is based on coloring a complete graph. Theorem 2.2 (Ramsey’s Theorem (2-color version)). Let r ∈ N. Then there exists an n ∈ N such that any 2-colored Kn graph contains a monochromatic (1-colored) subgraph Kr of Kn .[11] So in reference to our second definition of Ramsey theory provided in Section 1.1, if there is an orderly substructure (i.e. a complete monochromatic subgraph Kr ) then there must be some larger 2-colored structure in which that orderly substructure exists (i.e Kn ). From this, we also develop the idea of Ramsey numbers for a 2-colored graph. Definition 2.1 (Ramsey number (2-color definition)). A Ramsey Number, written as n = R(r, b), is the smallest integer n such that the 2-colored graph Kn , using the colors red and blue for edges, implies a red monochromatic subgraph Kr or a blue monochromatic subgraph Kb . [1] 5 There are a couple things to note about this definition. First, there are definitions of Ramsey theory and Ramsey numbers that address graphs with edge colorings using more than two colors. However, relations in 2-colored graphs are much easier to analyze and thus more progress has been made in the study of 2-colored Ramsey numbers than any other. Secondly, the choice of colors is completely arbitrary, but seems to be a convention in a few journals so this paper will do the same. 2.3 Contributions of Erdös The last mathematician we will choose to discuss is the esteemed Hungarian mathematician Paul Erdös. In 1933, Erdös and George Szekeres were posed the following question by fellow mathematics student Esther Klein: “Is it true that for all n, there is a least integer g(n) so that any set of g(n) points in the plane in general position must alwyas contain the vertices of a convex n-gon?” [2] This problem is now known as the Happy End Problem, a nod to the fact Szekeres and Klein ended up getting married
after the production of a paper on the question that showed 2n−4 n−2 that 2 + 1 ≤ g(n) ≤ n−2 + 1. But the most pertinent detail for Ramsey theory was that the work for this problem caused Erdös to discover Ramsey’s 1928 paper. This in turn led Erdös to begin working on identifying Ramsey numbers and sparked the beginning of major interest in Ramsey theory problems. Erdös is also well-remembered in Ramsey theory for providing the two of the most frequently cited stories about the theory. The first is a canonical example known as the Party Problem. In this problem, we assume that there are n people at a party where any two people either know each other or do not know each other. It can be shown that if there are six people at the party, then there will be a subgroup of at least three people that all know each other or all do not know each other. This is also another way of stating that R(3, 3) = 6, something that will be proven explicitly in another section. The second example is a hypothetical situation which I have dubbed the “alien invasion problem” due to the context of the situation. The ideas brought forth by the hypothetical has relevance to the difficulty in determining exact values for Ramsey numbers and will be discussed in greater detail in Section 4.2. 3 Ramsey Numbers Of all divisions of Ramsey theory, one of the most researched and well-known is that of Ramsey numbers. Although previously defined in Section 1.1, it’s worth reestablishing a formal definition as the following subsections will rely heavily on an understanding of Ramsey numbers, which are derived from an interpretation of Ramsey’s Theorem provided in Section 2.2. Definition 3.1 (Ramsey number (2-color definition)). A Ramsey Number, written as n = R(r, b), is the smallest integer n such that the 2-colored graph Kn , using the colors red and blue for edges, implies a red monochromatic subgraph Kr or a blue monochromatic subgraph Kb . [1] 6 Once again, we note that the colors red and blue are arbitrary choices for the two different colors in the 2-colored Kn . Moreover, we specifically refer to this definition of Ramsey numbers as the “2-colored definition” because there are other ways in which Ramsey numbers are defined and analyzed. For example, it’s quite common for mathematicians to look at all graphs on n vertices and look for the existence of cliques or complete sets of specified orders. These still fit the general intent of Ramsey numbers, as if you consider the existence of an edge between two vertices as a “red” colored edge and the lack of an edge as a “blue” colored edge, you notice strong similarities between these two interpretations. 3.1 Important Properties of Ramsey Numbers Now we can discuss some useful relationships between different Ramsey numbers, known values and range of values for different Ramsey numbers, then conclude with some proofs of important Ramsey numbers with known numbers. The first important property is that Ramsey numbers are symmetric with respect to their r and b values. Theorem 3.1. For all r, b ∈ N, the relationship R(r, b) = R(b, r) holds. Proof. This result is a natural consequence of the symmetry of graphs. From the standpoint of edge colorings, consider that a 2-colored complete graph G will have an inversely 2-colored complete graph G0 , where any red edge in G will be colored blue in G0 and vice versa. We know that R(r, b) requires that any edge coloration of KR(r,b) will have a red monochromatic subgraph Kr or a blue monochromatic subgraph Kb - that also means that the inversely 20 will have a blue monochromatic subgraph Kr or a red monochromatic colored graph KR(r,b) subgraph Kb . Thus, since the inverses of all edge colorings are just all edge colorings, we have the equivalent conditions for R(b, r). The next relationship was proved in 1955 by Greenwood and Gleason, which is extremely useful recursive bound for Ramsey numbers which is used in a few proofs of specific Ramsey numbers. Theorem 3.2. For all r, b ∈ N, the inequality R(r, b) ≤ R(r − 1, b) + R(r, b − 1) holds. Proof. Let G be a 2-colored graph on R(r − 1, b) + R(r, b − 1) edges (see Figure 1a for an example). Consider vertex v ∈ G. We denote nr as the number of vertices adjacent to v via a red edge and denote nb as the number of vertices adjacent to v via a blue edge. Moreover, we let the nr vertices adjacent to v by a red edge form a set Sr (see Figure 1b) and similarly the nb vertices adjacent to v by a blue edge form the set Sb . Since v is connected to every other vertex in G, we have nr + nb + 1 = R(r − 1, b) + R(r, b − 1). From this we have two cases. If nr < R(r − 1, b), then nb ≥ R(r, b − 1) and we consider the vertices in Sb . Because nb ≥ R(r, b − 1), then in the complete subgraph of G formed from the vertices of Sb and all edges between them there is a complete monochromatic subgraph M on r vertices or s − 1 vertices. Additionally, since we established that the vertices in Sb were all connected to v by a blue edge, we can say that the complete subgraph of G 7 (a) (b) (c) Figure 1: A visualization of an edge coloring of K18 (a), the vertices in this edge coloring that would be in the set Sr (b), and the corresponding subgraph of K18 using the vertices in Sr (c). formed from the vertices of Sb + v and all edges between them will contain a blue complete monochromatic subgraph on b vertices. Thus, G has a blue monochromatic subgraph of size b, and the inequality holds in this case. In the other case, we have nr ≥ R(r − 1, b) and consider the vertices in Sr . Because nr ≥ R(r − 1, b), then in the complete subgraph of G formed from the vertices of Sr and all edges between them (see Figure 1c for a visual) there is a complete monochromatic subgraph N on r − 1 vertices or b vertices. Additionally, since all vertices in Sr are connected to v by a red edge, we can say that the complete subgraph of G formed from the vertices of Sr + v and all edges between them will contain a re complete monochromatic graph on r edges. Thus, G has a red monochromatic subgraph of size r, and the inequality also holds, meaning that the theorem is valid in all cases. The value of Theorem 3.2 is its ability to establish a general upper bound for all Ramsey numbers. While the difference between R(r, b) and R(r, b − 1) + R(r − 1, b) tends to increase as r and b increase (and therefore lessen the value of this upper limit), it’s an excellent starting point for setting up the bounds of a given R(r, b). The last theorem we will spend time discussing is one that sets another upper bound for R(r, b), but this time in relation to combinations as opposed to other Ramsey numbers. Theorem 3.3.   r+b−2 R(r, b) ≤ r−1 Proof. We will prove by induction on r, b. First, we establish the following base case r = b = 2:   2+2−2 R(2, 2) = 2 ≤ 2 = . 2−1 Now assume that the relation holds for all r = x − 1, b = y and r = x, b = y − 1 cases - we demonstrate that the r = x, b = y case holds using Theorem 3.1 and Pascal’s Rule (which is 8 not defined but is a well-known combinatorial relationship): R(r, b) ≤ R(r − 1, b) + R(r, b − 1)     (r − 1) + b − 2 r + (b − 1) − 2 ≤ + (r − 1) − 1 r−1   r+b−2 = r−1   r+b−2 R(r, b) ≤ . r−1 3.2 Values for Ramsey Numbers Since most of the talk about Ramsey numbers has been in relation to the general case R(r, b), let’s jump into some actual values for Ramsey numbers. First, it’s important to note that there is a distinction between a “known” Ramsey number and a Ramsey number for which only upper or lower bounds are known. Stanislaw P. Radziszowski, a Polish-American mathematician who has worked extensively with Ramsey theory from the late half of the 20th century up to the present, has assembled an excellent table of Ramsey numbers and citations for either proofs establishing known values or upper or lower bounds for different Ramsey numbers [14]. From his work, I have compiled a table for Ramsey numbers R(r, b) with r, b ≤ 10 (see Figure 2 on the next page). A couple things from this table stand out. First, as noted in Theorem 3.1, the values are symmetric along the main diagonal because R(r, b) = R(b, r). Second, while values are well established for Ramsey numbers where r or b is small, most values are unknown. A primary reason for this is that the number of graphs that need to be assessed increases significantly with just a small increase in either r or b. Ramsey numbers are generally found by establishing that all 2-colored complete graph of the given size satisfy the conditions of R(r, b) and then demonstrating that there is some 2-colored complete graph of size R(r, b)−1 that does not satisfy the conditions. However, with increased size for the complete graphs that need to be checked, both the number of different colorings and the difficulty of assessing a given graph for a required monochromatic subgraph increases. Thus, all Ramsey numbers with r, b ≥ 5 have yet to be determined. Finally, the last thing worth noting about Ramsey numbers is the importance of Ramsey numbers of the form R(k, k). Sometimes referred to as “main diagonal” Ramsey numbers due to their position in a table of Ramsey numbers, these specific numbers are well-known for a few reasons. The simplest is that they are one of the most well-researched and frequently mentioned. Starting with the canonical example of the Party Problem following up with studies of infinite limits of the bounds for R(k, k), these are a specific classification of Ramsey numbers that have been fairly well-researched. A likely reason for this is the symmetry of the problem (requiring a complete monochromatic subgraph of the same order no matter which of the two colors the monochromatic subgraph is). 9 Figure 2: The Ramsey numbers R(r, b) for r, b ≤ 10. Two-number cells represent undiscovered numbers, with the top number being the upper bound and the bottom number being the lower bound.[9][14] 3.3 Proofs of Known Ramsey Numbers With a brief glimpse into what Ramsey numbers have been established, now it’s time to actually provide proofs for these values. Obviously we can’t take the time to go over every single proof of all Ramsey numbers that have been found - so instead we’ll tackle two general proofs that establish all Ramsey numbers R(r, b) where r ≤ 2 or b ≤ 2, then jump into proofs of the two other main diagonal Ramsey numbers that have been identified. 3.3.1 R(1, k) = 1 We start with the simplest Ramsey numbers, which you can infer from the table in Figure 2 that R(1, k) = R(k, 1) = 1. Although a formal proof won’t be offered, it’s easy to understand why this is from a coloring standpoint. A monochromatic K1 is simply a single vertex, which requires no edges and thus either a “red” or “blue” monochromatic K1 will simply require one vertex to satisfy the 10 conditions of R(1, k) or R(k, 1). Thus, all Ramsey numbers with r = 1 or b = 1 will only need a single vertex to guarantee the existance of one of their two required subgraphs. 3.3.2 R(2, k) = k Taking one step up in complexity, we analyze all Ramsey numbers with r = 2 or b = 2 and get R(2, k) = R(k, 2) = k. Once again, an explanation will be offered instead of a formal proof. Because a K2 subgraph is simple an edge between two vertices, a monochromatic subgraph of given color will exist as long as there is a single edge of that given color in the complete graph. Thus, the only edge coloring in which the conditions for the Ramsey number wouldn’t be satisfied is if every edge in the graph is the opposite color, or if KR(2,k) is monochromatic of the opposite color. This becomes an issue when the size of the complete graph is less than k - however, once R(2, k) or R(k, 2) is equal to k, the entire graph is a monochromatic Kk of the color required by the conditions. Thus, every single subgraph of Kk will have one of the two required monochromatic subgraphs. 3.3.3 R(3, 3) = 6 Now that we’ve proved some values for simpler Ramsey numbers, we’ll focus in on known Ramsey numbers of the form R(k, k). The first Ramsey number of this form to consider is R(3, 3), the number involved in the Party Problem. Theorem 3.4. R(3, 3) = 6 Proof. We will execute this proof by showing that 5 < R(3, 3) ≤ 6. First, we demonstrate that R(3, 3) 6= 5 by showing the following edge coloring of K5 (see Figure 3 below). (a) (b) (c) Figure 3: A K5 graph (a) with no monochromatic K3 subgraph. Visuals of all blue edges (b) and red edges (c) are provided to help demonstrate this fact. We note that none of the 10 triangles formed in this configuration are monochromatic and therefore R(3, 3) must be greater than 5. So we next must consider R(3, 3) = 6. We observe that for any vertex v in K6 , there must be at least three adjacent edges of the same 11 color. Without loss of generality, let’s assume that there are three red edges (Figure 4a). Next, we consider the three vertices adjacent to v via a red edge (Figure 4b). If any edge between two of these three vertices is colored red, then there is a red monochromatic triangle. On the other hand, if none of the edges between these three vertices are red, then there are three blue edges and thus a blue monochromatic triangle (Figure 4c). (a) (b) (c) Figure 4: A step-by-step visual process for proving that K6 mst have a monochromatic K3 subgraph In other words, you are guaranteed to have either a red or blue monochromatic triangle. This logic also applies to situations where v has four or five edges of a single color, as we simply look at any three vertices that are adjacent by an edge of that common color and apply the same logic as above. Thus, R(3, 3) ≤ 6 and R(3, 3) > 5, so R(3, 3) = 6. 3.3.4 R(4, 4) = 18 The value of R(4, 4) was established in 1955 by Greenwood and Gleason [9], who wrote the proof that will be presented in this section. Their proof relies on two additional pieces of information, the first being knowledge of the relationship R(r, b) ≤ R(r − 1, b) + R(r, b − 1) (Theorem 3.2) and the second being the following definition. Definition 3.2. Let a, x ∈ Zn . Then a is a quadratic residue if there exists an x such that x2 ≡ a mod n. [12] This becomes relevant in the second part of the proof, which utilizes some graph theory and this definition. With this information in mind, we can jump into the proof. Theorem 3.5. The Ramsey number R(4, 4) is exactly 18. [9] Proof. We will prove this be showing that 17 < R(4, 4) ≤ 18. To show that R(4, 4) > 17, we will give an example of a graph without a monochromatic K4 in K17 . First, consider a set of field elements Z17 , labeled 0 to 16, which correspond to 17 vertices in a graph G. Let every edge in G be colored based on vi − vj mod 17, where we color the edge between vertices vi and vj red if this difference is a quadratic residue in Z17 and blue otherwise. Next, suppose that we have four vertices that are all connected by edges of the same color. Without loss of generality, let one be 0 and the others be a, b, c. Since all edges connecting these are the same color, then a, b, c, a − b, a − c, and b − c are either all quadratic residues or not. 12 Now, since a is not the 0 element in Z17 , and Z17 is a field because 17 is prime, we can multiply by a−1 . If we let B = ba−1 and C = ca−1 , then we can make a new set of elements {1, B, C, 1 − B, 1 − C, B − C} which all must be non-zero quadratic residues. However, the quadratic residues of Z17 are 1,2,4,8,9,13,15, and 16, and no selection of values for B and C can make every element in the set a quadratic residue. Hence, there is a contradiction, meaning that R(4, 4) 6= 17 (and consequently must be greater than 17). Finally, we show that R(4, 4) ≤ 18 by noting that R(3, 4) = R(4, 3) = 9 and applying Theorem 3.2. Thus, 17 < R(4, 4) ≤ 18, meaning it must be equal to 18. 3.4 A Real Example of Ramsey Numbers To demonstrate that Ramsey theory is not all about purely mathematical constructions, it’s worth noting a interesting example of Ramsey theory appearing in history. This example comes from computer scientist William Gasarch, whose interest in Ramsey theory led him to find interdisciplinary applications of Ramsey theory. It discusses the work of a scholar of pre-Christian England named Sir Woodsor Kneading, who was studying interactions of various lords in small regions of England. Kneading noted 42 instances from 600 to 400 BC where the arrival of a sixth lord into a peaceful region with five lords was followed by the start of a war within a short period of time, while a unique case where war did not break out occurred when there was an alliance formed between all six lords in the region [6]. Kneading writes: “I noticed that either (1) three, four, or five of them formed an alliance and, thinking themselves quite powerful, merged armies and attacked the other lords, or (2) there were three or more of them who were pairwise enemies, and in that case war broke out among the factions...” [6] This observation is astounding because it is very reminiscent of the fact that R(3, 3) = 6, in that a group of six lords guaranteed a group of at least three that were all mutual allies or mutual enemies, and thus caused the region to erupt in war in all but one exceptional case. The next historical development that Kneading observes is also extremely applicable to Ramsey theory. He notes that after 400 BC there were “cases of six lords in a region and no war,” which he argues was due to technological advancements that increased risks with fighting (this was later confirmed) [6]. But astonishingly, Kneading finds that: “Between the years of 400 and 200 BC, whenever there were 18 lords in proximity either (1) between four and seventeen of them formed an alliance and, thinking themselves quite powerful, merged armies and attacked the other lords, or (2) there were four or more of them who were pairwise enemies, and in that case war broke out among the factions.” [6] With the knowledge that R(4, 4) = 18, Kneading’s observation is another example of a natural development of two Ramsey numbers that followed from logical, historical observations! While this is not necessarily a proof that the conditions of Ramsey numbers are guaranteed to hold, it is very inspiring to see this play out in a real situation beyonds the bounds of mathematics journals. 13 4 Bounds for R(k, k) Now that we’ve spent some time focusing on specific Ramsey numbers, we’re going to jump out to a little more abstract concept and consider the generalized bounds for Ramsey numbers of the form R(k, k). 4.1 Initial Bounds The initial bounds for R(k, k) were first established in a 1947 paper by Erdös, in which it was proved that k 2 2 < R(k, k) < 4k . [5] These bounds are definitely very broad, but the two proofs for the upper and lower bounds are both interesting and deserve some attention. We’ll start with the lower bound, which is unique because it utilizes a probablistic method. While Erdös’ proof in the original paper is understandable, there is an extremely well-explained version from Hung Q. Ngo of SUNY at Buffalo that we will utilize. First, Ngo provides the following summary of a probabilistic proof: “To show that some (combinatorial) object exists, one can envision working on some probability space in which the object lives in, and show that the probability of such an existence is strictly positive.” [13] This definition resonates with Erdös’ proof of the lower bound, which is based on identifying the probability of finding a monochromatic Kk subgraph in a randomly 2-colored Kn k graph, then showing that this probability is strictly less than 1 if n = 2 2 . From this, we know that there is at least some coloring of K k2 in which there is not a monochromatic Kk , k 2 meaning that R(k, k) > 2 2 . Ngo restates and proves this probabilistic proof in the following manner.
k k Theorem 4.1. If nk 21−(2) < 1, then R(k, k) > n. From this it follows that R(k, k) > 2 2 for k ≥ 3. [13] Proof. First, we define a graph Kn where we randomly color each edge in Kn as red or blue (i.e. a 0.5 probability of coloring red or a 0.5 probability of coloring blue). We note that if we randomly choose k vertices in Kn , the probability of these vertices forming a monochromatic
k Kk is 21−(2) . The best way to explain this is by noting that k2 is the number of edges in Kk , so if it’s monochromatic then the probability is k k 0.5 ∗ 0.5 ∗ 0.5... ∗ 0.5 = 0.5(2) = 2−(2) , which when you multiply by 2 possible ways it can be monochromatic (red or blue) provides k 21−(2) .
Next, we note that the total number of Kk graphs in Kn is nk , as we are simply choosing k vertices out of the n total in Kn . So the total probability of a monochromatic Kk existing
k in Kn is nk 21−(2) , which means that if this probability is less than 1 then there is some Kn 14 without a monochromatic Kk and thus R(n, n) > n. Using this fact, we aim to show that k R(k, k) > 2 2 for n ≥ 3. We note that   k k(k−1) n! nk 21+ 2 n 1−(k2) 1− 2 = < 2 2 k k!(n − k)! k! 2 k22 because n! (n−k)! k = n(n − 1)(n − 2)...(n − k + 1) < nk and 21−(2) rearranges into k 21+ 2 k2 2 2 . Then, via k the first relationship we proved on the previous page, we want to show that letting n = 2 2 for k ≥ 3 will force this probability function to be less than 1. So we have  k k k k k k2 2 2 1−(k2) (2 2 )k 21+ 2 2 2 21+ 2 21+ 2 < 2 = = <1 k k! 2 k22 k! 2 k22 k! 1+ k k where we conclude the final step that 2 k! 2 < 1 by noting that 21+ 2 < k! for k ≥ 3. Thus, there is some 2-coloring of Kn that does not have a monochromatic K k2 subgraph, meaning 2 k that 2 2 < R(k, k). With the lower bound out of the way, we now can focus our attention on the upper bound, R(k, k) < 4k . The proof of the upper bound is derived from a more specific inequality that Erdös found with Szekeres in 1935, which is   2k − 4 R(k, k) ≤ . k−2
Given this information, it’s easy to show that 2k−4 < 4k . We simply note that k−2   2k − 4 (2k − 4)! = ((2k − 4) − (k − 2))!(k − 2)! k−2    (2k − 4)(2k − 6)(2k − 8) · · · (4)(2) (2k − 5)(2k − 7)(2k − 9) · · · (3)(1) = (k − 2)!(k − 2)!   2k (k − 2)! (2k − 5)(2k − 7)(2k − 9) · · · (3)(1) = (k − 2)!(k − 2)! k 2 (2k − 5)(2k − 7)(2k − 9) · · · (3)(1) = (k − 2)! 2k − 5 2k − 7 2k − 9 31 = 2k ··· k−2 k−3 k−4 21 k k < 2 (2 )   2k − 4 < 4k k−2
But how do we get to the relationship between R(k, k) and 2k−4 ? The 1935 paper uses two k−2
2k−4 methods to demonstrate the inequality R(k, k) ≤ k−2 , but both methods utilize geometric 15 analysis as opposed to graph theory and are unsatisfying in terms of length and clarity. However, there is another method that is much easier to understand, applies to more than just Ramsey numbers along the main diagonal (a way to refer to Ramsey numbers R(k, k)), and is also based on theorems we have already discussed and proven. We start with the general statement of this theorem.
Theorem 4.2. For all Ramsey numbers the relationship R(r, b) ≤ r+b−2 holds. r−1 Proof. We will prove by induction. First, we establish the base case r = b = 2:     2+2−2 2 = = 2 ≥ 2 = R(2, 2). 2−1 1 Now assume that the relation holds for all r = x − 1, b = y and r = x, b = y − 1 cases. We demonstrate that the r =
x, b = y
case holds as follows, using Theorem 3.2 and Pascal’s
n n−1 n−1 Rule, which states that k = k + k−1 . R(r, b) ≤ R(r − 1, b) + R(r, b − 1)     (r − 1) + b − 2 r + (b − 1) − 2 ≤ + (r − 1) − 1 r−1   r+b−2 = r−1   r+b−2 R(r, b) ≤ . r−1 We note that for the Ramsey numbers along the main diagonal, r = b, so this

can be 2k−2 2k−4 rewritten as R(k, k) ≤ k−1 . This is not quite the exact form as R(k, k) ≤ k−2 , but both
upper bounds are equal to some 2x , which means the bounds will be equivalent if we shift x
k up by one when comparing the terms. Thus, in conjunction with the relation 2k−4 < 4k , k−2 we have a proof of the inequality for the upper bound of R(k, k). 4.2 Evolution of Bounds It’s important to note that these bounds have improved overtime. The upper bound for Ramsey numbers along the main diagonal has improved most signifcantly, with the current best bound being proved by David Conlon in 2010. Using previous results, he found that the upper bound can be reduced to   log(k) −C log(log(k)) 2k R(k + 1, k + 1) ≤ k k with C being some constant [3]. The proof of this is also very long and the result is so specific that it’s better to refer to his paper as opposed to taking time to restate the proof. This bound is certainly more complicated than the initial upper bound, and in some cases it is a 16 worse estimate of the possible values of certain Ramsey numbers. For example, depending on the value of C, Conlon’s upper bound for R(5, 5) could be significantly greater than the initial upper bound of 54 provided by Erdös. An example that speaks to the difficulty of reducing bounds and identifying Ramsey numbers is the alien invasion problem introduced by Erdös. The problem is a hypothetical situation were aliens have visited Earth and have threatened to destroy the planet in six months if we cannot produce an exact value of R(5, 5) (which, as it stands, is the smallest Ramsey number of the form R(k, k) without a known value). Erdös asserts that if humanity was to put all of its computing resources into solving the problem, we would be safe - but if the aliens had asked for a solution to R(6, 6), we’d be better off trying to fight them [4]. Outside of the interesting premise and value as an icebreaker for presentations on Ramsey numbers, the example also alludes to the increasing difficulty of determining exact values of Ramsey numbers R(r, b) even if you only increase r or b by 1. 5 A Computational Method While most of the information provided in this paper is either a direct reference to work or proofs done by other mathematicians, there was one specific area in which individual work is highlighted. That area is my attempts to produce a computational method to improve bounds on unknown Ramsey numbers. This method required the ability to generate all 2-colored complete graphs of a specified order and analyze each specifically colored graph for monochromatic subgraphs satisfying the conditions of a given Ramsey number. There are a couple of caveats to this process. First, this is by no means the only way to go about the computational process for analyzing conditions for Ramsey numbers. The focus came about because I did not find satisfactory or even generalized code to identify exact values for Ramsey numbers during my research. This is troubling, because computational methods seem to be effective ways to assess complete graphs with many different colorings and different possibilities for monochromatic subgraphs, which tends to be the case for the smallest unknown Ramsey numbers such as R(5, 5) or R(3, 10). Secondly, the code that was produced and will be discussed is by no means efficient. The method I chose is the most brute force method possible, calculating all possible colorings (even those that are similarly structured or are known to already contain monochromatic complete subgraphs) and running iteratively through each complete subgraph of the size analyzed by the Ramsey number (all possible K5 subgraphs if calculating R(5, 5), for example). Finally, it’s worth noting that running my computational method for the allotted time committed to testing did not find any exceptions that would allow us to lower the bounds on some Ramsey number. This was entirely to be expected, as the chance of a personal computer running through cases and finding an exception is extremely low. Instead, my hope is that this code will be a baseline for others to possibly build off of and improve in order to generate an understandable and efficient computational method for determining exact values for Ramsey numbers. 17 5.1 Representing Colorings of Compelete Graphs Now let’s take the time to understand the process through which my method operates. The specific code I used is found in the Appendix, with three different functions being used in combination to produce the overall method. Given that there may be some readers who have not learned Python, the programming language in which the code is written, the following sections will be explained in more general terms. To start, there needs to be a way to produce all 2-colored graphs of a given order. This requires the representation of every single edge in the graph, which need to be identified as either red or blue. This binary requirement led me to consider binary numbers as a possible conduit for representing all edges in a graph. We can represent any given graph as an array of binary numbers, with a ‘1’ or a ‘0’ in a specific bit location corresponding
to a specific edge that is colored red or blue, respectively. This ends up requiring a n2 -bit
array for a given Kn in order to account for all n2 edges, which can be a little complicated. n However, an advantage of this method is that we know that there are 2( 2 ) possible colorings n of K , and moreover we can convert each number from 0 to 2( 2 ) − 1 into a unique binary n representation. More specifically, the set of all unique representations will correspond to n every possible sequence of 0s and 1s in a 2( 2 ) -bit array, meaning we have accounted for all possible colorings of Kn (see Figure 5 below for an example). The process for converting an integer to binary is a simple process and the specific code used can be found in the “BaseConverter” function listed in the first figure of the appendix. 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 Figure 5: A graphical representation of every coloring of K3 and the corresponding binary array representation that would be generated by the developed code (see the appendix for details). Each bit corresponds to an edge and is either 0 if the edge is colored blue or 1 if the edge is colored red. 5.2 Producing Adjacency Matrices While producing a binary representation is useful, it’s not very intuitive or efficient to analyze these representations. Thus, my work uses adjacency matrices, which are matrices used 18 to represent graphs. In an adjacency matrix of a graph G, the element (i, j) normally corresponds to the number of edges between the vertices vi , vj ∈ G. However, since we are looking at complete graphs that are 2-colored, we instead represent each element as either −1, 0 or −1, where -1 represents a blue edge between vi and vj , 1 represents a red edge between vi and vj , and 0 is reserved for elements (i, i) because there is no edge between vertex vi and itself. The reason for using -1 and 1 is so we can distinguish between red and blue monochromatic graphs. In order to produce these adjacency matrices, the binary array representation of the graph is transferred to the adjacency matrix by assigning each bit in the array to a location in the adjacency matrix such that a 1 bit produces a 1 in the assigned matrix location and a 0 bit produces a -1 in the assigned matrix location (see Figure 6 below for an example and the function “GraphCreator” in the first figure of the appendix for more details). 2  3 1 0 0 1 0 1 1  0 1 1 −1 1 0 1 −1   1 1 0 −1 −1 −1 −1 0 4 Figure 6: Three equivalent representations of a 2-coloring of K4 . The graphical representation corresponds to the bit array by assigning each edge color to a 0 (if blue) or 1 (if red) bit. The least significant bit corresponds to edge (1,2), the second least significant to (1,3), and so on until the most significant bit corresponds to the color of (3,4). The adjacency matrix representation relates to the graph such that each element (i, j) corresponds to the color of edge (i, j) in the graph, with a -1 if blue and 1 if red. We note that when assigning a bit array element to an adjacency matrix element (i, j), we also assign that bit array element to (j, i) (due to symmetry). For this reason, I choose to go through the bit array element by element and then assigning each element in a way that prioritizes filling each row in order, then filling in the next row, and on until all rows are filled. For example, to fill an n × n adjacency matrix, we would assign the first bit to (1, 2), the second to (1, 3), and so on. Then, when the n − 1st bit is assigned to (1, n), the nth bit starts filling in the next row at (2, 3), and the n + 1st bit goes to (2, 4) and so on until the final three bits fill in (n − 1, n − 2), (n, n − 2), and (n − 1, n − 1) respectively (see Figure 6 above for an example). 5.3 Testing for Monochromatic Subgraphs One way to test an adjacency matrix for a specific subgraph is by multiplying it by another adjacency matrix corresponding to the subgraph in question. In this case, the method represents all edges for a given complete graph of a certain size in a square matrix of order equal to that of the adjacency matrix for the 2-colored graph. For example, testing for a K5 subgraph in a K43 graph would result in a 43 × 43 adjacency matrix, but with 1s filled in for each element corresponding to an edge between vertices in the specific K5 subgraph. 19   0 1 1 −1 0 1   0 1 −1 1  1 1 0 −1 1 −1 −1 −1 0 0 1 0 1 0 1 1 0 0   0 2 1 1   0  1 2 1 = 0  1 1 2 0 −1 −1 −2  0 0  0 0 Figure 7: An example of testing for a monochromatic subgraph. In this example, an adjacency matrix for a 2-colored K4 is matrix-multiplied with an adjacency matrix associated just with the complete subgraph between vertices 1, 2, 3 ∈ K4 . The resulting matrix has 2 in each element (i, i) (where i ∈ {1, 2, 3}), indicating that this K4 coloring has a monochromatic K3 between vertices 1, 2, 3. When the adjacency matrices are multiplied, some important information can be gleaned by the main diagonal of the resulting matrix. Specifically, the elements (x, x) in the resulting matrix (where x is the row or column value of a vertex in the complete subgraph Kk under evaluation) will all be equal to ±(k − 1) if Kk is monochromatic. The reason for this is because of the way the adjacency matrix was structured (having 1s or -1s for all red or all blue edges) and the matrix multiplication identifying k−1 edges of the same color adjacent to each vertex in Kk . See the function “SubgraphFinder” in the second figure of the appendix for more details. Thus, with this process, we can test all possible subgraphs to see if there is a monochromatic Kk . This method is slow, simply testing every possible combination of vertices for a monochromatic subgraph of the desired size. If a monochromatic subgraph is found, the process then moves on to the next 2-colored graph and tests the new adjacency matrix for a monochromatic subgraph. Eventually, there is either a 2-colored graph in which no monochromatic subgraph is found and the code return the counterexample, or all colorings are evaluated successfully for a monochromatic subgraph and the conditions for the Ramsey number are satisfied (see the second figure in the appendix for an example). 6 Closing Thoughts One of the most interesting questions I’ve been asked as I’ve presented material on this project to fellow mathematics majors is when I expect the next Ramsey number to be determined. That’s definitely an impossible question for me to answer as someone with very little experience or connections in the field of Ramsey theory. Hypotheticals like the alien invasion problem or a general understanding of the sheer quantity of colorings and subgraphs that need to be considered seem to indicate that it may be extremely difficult to establish an exact value for a Ramsey number. However, the optimist in me says we may reach a new step sooner than we might expect. People have continued to work in this field for almost a century, from van der Waerden and Ramsey in the 1920s, to Erdös in the 30s and beyond, to Greenwood and Gleason since their 1955 proof of R(4, 4), and to Radziszowski’s decades of work that has continued into the 21st century. This indicates a clear commitment and drive to continually develop new findings, something that is strengthened by real-life connections to Ramsey theory like the Party Problem or Kneading’s observations of pre-Christians English lords. Additionally, advances 20 in computing technology and methodology will likely enhance the ability of mathematicians to calculate exact values without assembling the entirety of humanity’s computing resources a la the alien invasion problem. So where does this paper sit in regards to these possibilities for the future? As I noted in the introduction, the novelty of this work may be lacking, and may just be a blip on the radar of some future mathematician searching for sources on Ramsey theory. But the first step to making any advancements in Ramsey theory or with Ramsey numbers is to understand the basics, something I attempted to convey in an comprehensible fashion over the course of this paper. From there, the path may be unclear, but I hope that whoever continues to work in this amazing field will keep their heads up and make their highs low and their lows high, as that is the way we will have to alter our bounds to find the next Ramsey number. Appendices Figure 8: Two functions written in the Python language. BaseConverter takes a base 10 integer value and an integer base as its inputs and outputs an array (or list) of integers corresponding to the conversion of the base 10 integer into an integer in the input base. GraphCreator takes an base 10 integer value and a dimension n for an n × n matrix and returns an n × n matrix. The purpose of this code is to create an adjacency matrix for a specific 2-coloring of a graph Kn . The GraphCreator takes an integer value and uses BaseConverter to turn that value into a base 2 bit array that defines the specific coloring of the graph. GraphCreator then fills in the n × n matrix with 1 or -1 values based on this coloring and outputs the resulting adjacency matrix that reflects this coloring. 21 Figure 9: Code written in the Python language. The function SubgraphFinder takes an adjacency matrix and the dimension of a complete graph as inputs and outputs a true or false value depending on whether the adjacency matrix contains a complete monochromatic subgraph of the dimension entered as an input. The remaining code below the SubgraphFinder tests conditions for R(5, 5) = 45. The while loop runs through all colorings of K45 and tries to identify whether each coloring has a monochromatic K5 . If it does, a verification statement is written, while if there is no monochromatic K5 for a given coloring, then the integer value that corresponds to that K45 coloring is written to identify a counterexample for R(5, 5) = 45. Note that the while loop starts at i − 2280 because based on the way the bit array and adjacency matrix for colorings of K45 are generated, any i value less than 2280 will have a monochromatic K5 between vertices 41, 42, 43, 44, and 45. 22 References [1] Brualdi, Richard A. Introductory Combinatorics. 3rd. United States: Prentice Hall, Inc., 1999. Print. [2] Chung, Fan, and Ron Graham. Erdős on Graphs: His Legacy of Unsolved Problems. Wellesley, MA: AK Peters, Ltd, 1998. Print. [3] Conlon, David. “A New Upper Bound for Diagonal Ramsey Numbers”, Annals of Mathematics, 170 (2009) 941-960. [4] Dickson, James O. “An Introduction to Ramsey Theory on Graphs.” Virginia Tech University (2011): 85. Web. 26 Jan. [5] Erdös, Paul. “Some Remarks on the Theory of Graphs.” Bulletin of American Math Society 53 (1947): 292-294. Web. 24 Feb. 2016. [6] Gasarch, William.“Ramsey Theory and the History of Pre-Christian England: An Example of Interdisciplinary Research.” Journal of Ramsey Theory (2015): Web. 16 Feb. 2016. http://www.cs.umd.edu/ gasarch/BLOGPAPERS/ramseykings.pdf. [7] Gould, Martin. “Ramsey Theory.” University of Oxford (2010): 1-15. Web. 15 Feb. 2016. http://people.maths.ox.ac.uk/ gouldm/ramsey.pdf. [8] Graham, Ronald L., and Joel H. Spencer. “Ramsey Theory.” Scientific American. N.p., July 1990. Web. 8 Feb. 2016. [9] Greenwood, R.E., and A.M. Gleason. “Combinatorial Relations and Chromatic Graphs.” Canadian Journal of Mathematics 7 (1955): 1-7. Web. 1 Feb. 2016. https://cms.math.ca/openaccess/cjm/v7/cjm1955v07.0001-0007.pdf. [10] Kunkel, Curtis J. “Ramsey Numbers: Improving the Bounds of R(5,5).” Midwest Instruction and Computing Symposium (2003): 1-12. Web. 14 Feb. 2016. http://www.micsymposium.org/mics2003/Kunkel.PDF [11] Leader, I.B. “Ramsey Theory.” University of Cambridge Department of Pure Mathematics and Mathematical Statistics (2000): 29. Web. 26 Jan. 2016. [12] Lynn, Ben. “Quadratic Residues.” Number Theory. University of Stanford, n.d. Web. 9 Feb. 2016. https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html. [13] Ngo, Hung Q.“The Probabilistic Method - Basic ideas.” SUNY at Buffalo, 2005. Web. 1 Mar. 2016. [14] Radziszowski, Stanislaw P. “Small Ramsey Numbers.” The Electronic Journal of Combinatorics DS1.14 (2014): 1-94. Web. 29 Jan. 2016. 23