DIMACS
DIMACS REU

Daniel Solano


About

Student: Daniel Solano
Office: CORE 446
School: Rutgers University, New Brunswick
E-mail: ds1229 dot at scarletmail dot rutgers dot edu
Project: Computational Ramsey Theory

Week 1 June 5 - June 11

Preliminary studies on Ramsey Theory: Ramsey's Theorem, Van der Waerden's Theorem, and Schur's Theorem Began researching Rado's Numbers, Coloring Finite Vector Spaces, and Algorithms
Completed Presentation. slides

Week 2 June 13 - June 17

Practice using Wolfram Mathematica and created basic for-loop algorithm to extrapolate numbers which do not belong to a color set C. This algorithm helped solve 2-Colors. Any number which is not red must be blue and vice versa. The equation being considered is ax+by=cz
Started working on an algorithm for 3-Colors which are far more elusive. Created basic NOT function, replacing the for-loop and 'patch' functions to remove infinity from sets. Implemented a while loop as well. Only not blue and not green numbers are red, and similarly for blue and green.

Week 3 June 20 - June 24

A cleaner version of the previous 3-Coloring was made. Researching recurvsive functions. The need for recursion was discovered when deducing values for all numbers proved to be impossible with out making choices.
A basic recursive algorithm or idea sketched out. Several recursive functions attempted, many errors caused by recursive depth errors.
*** In retrospect, the issues were due to using global variables instead of local ones.

Week 4 June 27 - July 1

First serious '3 Color Draft 1 " created. An attempt to make a nonrecursive function by coding decision making into mod 3 code. For an example:
10202102102001202012010
Reads that the first choice was blue, then red, then green... While attempting to make a recursive function that works, the nonrecursive model was cleaned up.

Week 5 July 5 - July 8

Happy Independence Day! A total start from scratch was made in order to create an error free recursive function defined by local variables. The code is significantly shorter than before.

Week 6 July 11 - July 15

"3 Color Draft 2" was created and is the first successful recursive function. Max[28, Null] issue resolved -- now only numbers are outputs. The recursive function extrapolates new numbers and then uses them all until a decision needs to be made. Then it makes 3 parallel decisions: color the smallest uncolored number Red,Blue, or Green and repeat.
With known solutions, sample equations are tested, numbers smaller than the real Rado numbers come out :-(.

Week 7 July 18 - July 22

BINGO. Code finally gives right answers after using Echo function to allow me to see 'under the hood'. Changes are made in which new numbers are colored (for a given color): only those new numbers which are smaller than the largest colored number M is considered or the smallest new number that is larger than M. Over determination was discovered -- coloring numbers larger than the Rado number that yield monochromatic solutions cause the code to prematurely stop and give the 'Rado number'
The code was made faster by changing a small detail:"only those new numbers which are smaller than the largest colored number M is considered AND the smallest new number that is larger than M." The timing for our most complicated solution R(2x+y=2z) went from above 12 hours and indefinite to 3.255 hours.

Week 8 July 24 - July 28

The code has been made more efficient and solves
x+2y=2z in 0.3 seconds with R = 14
x+2y=z in 33 seconds with R = 43
2x+3y=2z in 3.255 hours with R = 61
3x+y=z in 2.35 hours with R = 79
Several more equations will be attempted to be solve:
3x+y=2z,4x+y=z,kx+y=z,3x+3y=2z,3x+3y=4z,... The final report has been written.


I am indebted to DIMACS (directors and staff) for the support and opportunity to have a math REU 'under my belt' for my career.



Last updated: July 28, 2016