DIMACS logo

Herman Sameisky

REU 2011


General Information

Email:
hjs66@cornell.edu
Office:
244 CoRE, Rutgers Busch Campus
School:
Cornell University
Project:
Pebbling and k Class-0 Subgraphs
Mentor:
Eugene Fiorini
Partner:
Cristina Cabrera

Week 1

During this adjustment period I did the basic work to introduce myself to the wonderful world that is pebbling. I also found that I have a great interest in Graham's Conjecture and am hoping to pursue related topics.

Week 2

I expanded on previous results that had shown that for any k there exists a complete graph that is k Class-0. I then moved to studying the 2 pebbling property (2pp) which seems to play a central role in the field of pebbling. I also looked at the complexity of finding the pebbling number of a graph and have attempted to look into finding a formula for a higher bound for the pebbling number of a graph.

Week 3

Gene helped us decide on a project which we can definitely make progress on over the course of the summer. We are looking at a specific graph of size 6, diameter 2 and girth 3. It's semi regularity and high symmetry make it an excellent model for future generalizations. We are going to attempt to show that this graph multiplied by itself follows Graham's Conjecture.

Week 4

We have determined that the pebbling number of the given graph is 7. Therefore the pebbling number of the product must be less than or equal to 49. Since it is a rather large graph, size 36, any straight forward approach has failed. It is not at all obvious how to proceed or how one can pebble such a large graph. Perhaps only working on general principles would be easier.

Week 5

We have made great progress in proving the pebbling number of the graph is less than or equal to 49. We found a sufficient condition which seems a lot easier to prove, namely that the product of our original graph and the complete graph on three vertices has a 2 pebbling number of less than or equal to 25.

Week 6

This problem has proved to be difficult. However, we have made some prograss by working on cases. We have split the graph into two pieces and are looking at when pebbles are in either piece. Out of the 25 cases we have easily verified 20.

Week 7

We have continued working and with help from Gene we have solved 3 more cases. However, the last two cases seem to be near impossible. I have formulated many ideas on how to pebble these, but they all fail. I am starting to think there may not be a general way of pebbling these cases. Still every arrangement we try is solvable. I am confident our original hypothesis is correct, but whether it can be verified with this approach I am unsure.

Week 8

We have continued trying to solve these 2 cases, but with little success. To be honest this last week was filled with many goodbyes and I didn't get as much work done as I had hoped. Overall I think it was a good summer and I made a lot of good work on my project. I have several new questions which I hope to work on in the future as well as continuing this one.