DIMACS
DIMACS REU 2014

General Information

me
Student: Shannon Jordan
Office: Core 450
School: Morgan State University
E-mail: S_Jordan311@yahoo.com
Project: Graph theory

Project Description


Weekly Log

Week 1:
This week was a basic graph theory review. We put together a presentation on some Graph theory concepts such as digraphs, adjacency matrix, vector coloring, graph isomorphism, competition graph, and interval graph. Lastly, we gathered information on finger printing background. We then questioned how they relate. Suppose we get this finger print, how can we compare it to a finger print in the huge data base. You can label the differnt parts of the finger print with vertex, each part you identify ; loops, delta, ridges and island, get a differnt color vertex. With the vertices you can put a weight on the edges by counting the ridges in between the teo vertex.
Week 2, Monday :
For starters, we gather information on competition and digraphs. Before go into research head on, we want to know whats out there so that nothing is being reinvented.
Week 2, Thursday:
As I read up on information on interval graphs, competition graphs of semiorders and their conditions, and m-step competition, the one that stood out was the m-step competition graphs. My immediate question was "Whats the difference between m-step Competition Graphs and Dyck Paths?" With that brought up another question " Is there a competition between Dyck Paths and Competition Graphs?" My next step is to find a relationship between the two and see where that takes me.
Week 3:
This week I focused on posets. I observed the different properties of posets. Some properties are Maximal, minimal, upper bound, lower bound, least upper bound of Y, Greatest Upper Bound of Y, chain, and Anti-Chain. Then I tried to find a comparison to the Dyck Paths. I chose the Dyck Path with relation to the Catalan Numbers. I started with 14, and counted the number of paths, excluding the paths with UUUUDDD AND UDUDUD. Once that was done I randomly picked a starting set and an ending set. I hand drew the diagram; it is still a little unclear if the diagram that I drew is an actual poset. Because it takes a lot of time to write out the different combinations or ways to get to a specific number, I?m going to try and create a code and see if that helps.
Week 4:
Since Week 3 ended I started to take another route. Im still going to be working with posets but instead of Dyck Paths, Im leaning towards digraphs and their competition graph in the space Rn. This week my group came up with some forbidden graphs in the space Rn, because Im already looking at posets, I started to prove how to categorize all the forbidden subgraphs in this Rn space into a poset. Once that is done, the question then remains, whether or not we have found all of the forbidden subgraphs in the space Rn. With the proof of poset for the forbidden graphs, the next thing to think about is if we look any digraph can we immediately find its competition graph and vice versa.
Week 5:
Instead of categorizing the forbidden subgraphs as posets, I categorized the digraphs in the Rn space as a poset. I taught myself how to use LaTex so that I can type up my proof. Once my advisor read it over, we met to talk about the structure of how he wanted my proofs done in the future. Once that was done, I rewrote my proof. The next step is looking at the digraphs on Dyck Paths which have the same start and end. Im looking to see if, D represents a poset, and what are the forbidden subgraphs of the competition graphs.
Week 6:
Week 7:
Week 8:

Presentations


Additional Information