DIMACS REU 2013

General Information

Adrian Galicia
Student: Adrian Galicia
Office: CoRE Building 507
School: San Diego City College
E-mail: adrian_galicia92@hotmail.com
Project: Rado Number Algorithm/web-software

Project Description

  The objective of my project is to create an algorithm to compute Rado numbers, then implement it in a web-friendly language (javascript, php, etc.). Also, the piece of software will visualize the computation and prove the output( Rado numbers) with a certificate (in this case a tree output).

  To understand my project one should understand first Ramsey's theoram which states that; Given some edge-coloring of a complete graph there exist monochromatic subgraphs.More explicitly, if two colors are used (red & blue), for any positive integers (r,s), there exist a positive integer N = R(r,s) where a coloring of K[N] will give K[r] red or K[s] blue.

k_5

 

 

  Take for example , if we color the vertices of a K[5] we can avoid creating blue or red triangles, so we say ramseys theorem does not hold for K[5].

 

 

 

 

k_6

 

 

If else we take a K[6] complete graph we can see that there is no way to color its edges without creating either a blue triangle or a red triangle. So, we can say that the smallest integer for which R[3,3] holds is R[3,3]=6.

 

  Similarly, Rado number states that; given some equations "E" such as x + y = z and some number of colors "r" (r=2; red & blue in this case), find N so that there is no way to color 1 through N without a solution to the equation of the same color. Likewise, we are looking for the least Rado number N for a given equation for which the stated above holds

 


Weekly Log

Week 1:
  During this first week I met my mentor for the first time and we started reviewing some knowledge needed to start my project. I started to code the core of our program which will test each number colouring of any length . I also prepared which was my main focus during this first week. My mentor helped me with the content of my presentation.
Week 2:
I continued to work on my algorithm and my code. I also learned more JavaScript since I never coded before in that programming language.
Week 3:
I already worked on the program's coloring checking function which checks each string coloring of zeros and ones ([0,1,0,0,1] 0=red 1=blue ) to see if it is a valid coloring ( no monochromatic solutions to the equation ) or invalid coloring (monochromatic solutions to the equation. I also worked in a coloring generator function which uses a stack data structure to keep track of the colorings as they are being created and tested with the mentioned coloring checking function. What this coloring generator function basically does is; starts with a zero (red) then adds a zero to the stack and calls the coloring checking function to see if it is valid, if it is valid it will add another zero to the stack and and check again until the coloring is non valid then it replaces that zero with a one, if it is also not valid it will back track erasing the last element of the stack and keep going forever until it changes the index zero of the stack. I will focus a little bit in the visual interface as well as the user output this week. later I will try to make it more efficient in the way it manages memory resources.
Week 4
This week I focused on the visual interface. Previously it prompted the user for an output in input windows (old style). Since I am new to this language still I learned how to manipulate the contents of forms from HTML using JavaScript. As before, it outputs all the colorings tested and says if they are valid or not, it has a button for showing all the colorings tested if the user request it or if the user only wants the N rado's number it outputs it clearly with the equation as well as how many colorings were tested.I also made some minor modifications to the code like adding a function to output the colorings tested as actual colored numbers instead of just representing them with zeros and ones. I will further improve this output next week and I will start working on the tree output.
Week 5
Besides Starting to work on the tree output I added a new thing to the output. The program now tells the what numbers of a coloring make such coloring valid. It highlights them with a different color and shows the equation with those numbers so the user know exactly why a coloring is invalid. Also I put another feature for the user to change the limit N of the number with a default value of 200. In the area of the tree output I tried different approaches but each one failed. I tried doing the tree as the colorings are being generating but to keep track of everything at the same time might be too much. I tried a simple text output with "/" and "\" as branches but the spacing between the nodes is never enough, as the tree becomes larger and larger the space reduces and the nodes sit next to each other ruining the layout of the tree. I try this in several different ways but it seems to be a better way. next week I will try a new idea with a 'List Structure' in a combination with CSS which seems a lot more promising than a simple text layout.
Week 6
This week I started to implement the List Structure into my algorithm. I try to create the List Structure as the colorings are being generated but this did not produced good results. Since it is not possible to know the length of the tree before it is being created it is hard to keep track of every changes each coloring test produce. I meet with my mentor this week and we discus how to make the tree output happen. A way of making the tree is to wait for the Rado Number N to be reached and keep track of the ends of the branches of the tree. using this ends to start creating the list structure by comparing the ends of the tree. This following week I will try to finish this. The tree output was way more complicated than I though but it still not impossible. Also, this following week I am going to do my final presentation.
Week 7
I tried different methods to make the tree output happen that seemed very straight forward at the beginning but turned out to be more complex than needed. As mentioned before, the program outputs all the colorings tested; the valid colorings and the non valid colorings.Within the valid colorings sets there is a subset of colorings which are the largest valid colorings of this set. Within this large colorings other smaller valid colorings are contained. That means that all we need to make the tree is those large colorings which I called 'largests non-extensible colorings' because if extended it becomes non valid, also if a sub-coloring inside this large coloring is extended it becomes non valid. I will use this 'largests non-extensible colorings' to make the tree happen. This week did my presentation. It was delivered not perfect but better than the first one. I was not able to finish the program with the tree output but now I have a clear way to do it.
Week 8
At the beginning of this week I finally made the tree output happen. within those mentioned non-extensible colorings there exist some colorings larger than others. Because those large colorings are basically branches from the tree that are extended from the root to the ends of the trees, and some branches are shorter than others. I placed them in a 2D array, which is basically an array of arrays, then sorted them the opposite way they were sorted, then in a simple loop start creating the list structure from bottom to top , or from right to left in the tree. in finally outputs the tree once the colorings are tested and the biggest N is found. I also added a feature that test only a single user entered coloring with a user entered equation. The user has to enter the coloring with 0's 1's 2's and 3's for red, blue, gree, brown. To make it easier, as the user is entering the coloring they can see the actual coloring with colored numbers. I also performed other minor changes on the code to make it a little bit more efficient. The objective of this project was reached, to make an algorithm to compute Rado numbers and to implement it in a scripting language and finally to visualize a tree output that serves as a certificate to prove that the given N is correct.

program

Presentations


Additional Information