DIMACS
DIMACS REU 2014

General Information

me
Student: Roger Licairac
Office: CoRE 450
School: Rutgers University
E-mail: rlicaira@scarletmail.rutgers.edu
Project: Graph Theory and Competition Graphs.


Project Description

Starting from predator-prey concepts in ecological food webs, Joel Cohen introduced the notion of competition graphs in 1968. Competition graphs arose from analysis of food webs and have applications in biology and network systems. The competition graph C(D) of a digraph D = (V,E) has the same vertex set as D, and two distinct vertices x, y are adjacent in C(D) if there is some vertex z ∈ V (possibly x or y) such that zx,zy ∈ E.

We define a digraph of a relation on ℝn where each element in the set has a vertex there is an edge from
(a1, a2, ..., an) to (b1, b2, ..., bn ) if and only if ai > bi ∀i.

We are interested in finding forbidden subgraphs of competition graphs of this relation on ℝ3.

Weekly Log

Week 1:
This week I reviewed the basic concepts of graph theory and prepared my first project presentation. Some of the basic concepts I reviewed were path, walk, cycle, circuit, directed and undirected graphs. Furthermore, I did some background work on integer sequences and graph isomorphism algorithms. I also looked into developing an algorithm for fingerprint identification and explored several problems in competition graphs. The first presentation has been uploaded to the link at the bottom.
Week 2:
For this week, I reviewed several literatures of graph theory and reviewed adjacency matrices while also writing a program in maple to draw directed graphs and its competition graphs. I continued to look further into the problems of graph theory. Some of the challanges I have been facing is reducing the graphing command to two parameters that will allow the user to modify the number of dimensions and vertices for maple to draw directed graphs and its competition graph. My preliminary program draws a two dimensional digraphs and its competition graphs based on the position and number of vertices.
Week 3:
I continued with the literature review and other additional literatures. I wrote more maple scripts to generate directed graphs and its competition graph. I focused on the problem of finding forbidden subgraphs of its competition graphs by looking at different cases where the number of vertices and the numbers of edges incident to them were different for each graph. Furthermore, I looked into constructing some proofs of the forbidden subgraphs of its competition graphs.
Week 4:
I found one of the family of forbidden subgraphs for the competition graph of our relation. The star graph with n vertices and n-1 edges is a forbidden subgraph of the competition graph. I worked on the proof for this particular family of forbidden subgraph. My coworker Aquia found another family of forbidden subgraph, which was a graph with cycle length of 4 or greater is forbidden for the competition graph of our relation. I started the idea generalizing it to all finite posets. To illustrate, If S is a finite poset, we are trying to categorize the forbidden subgraphs of the competition graph for the corresponding digraph.
Week 5:
I tried to come up with more examples of forbidden subgraphs for the competition graph of our relation in order to find another family of forbidden subgraphs. I continued to focus on finite poset to try to categorize the forbidden subgraphs of the competition graph for the corresponding digraph. Furthermore, I reviewed a recently published literature called "On Competition Graphs of n-tuply partial orders, which both of Dr. Brian Nakamura and my mentor emailed it to my coworkers and me. After meeting with my mentor, he suggest that we look at tree competition graphs with end vertices of degree 1 and try to find a digraph that corresponds to them. To make it simple, we started this with the case on ℝ2. The key idea is to check whether we can find an isolated vertex of the digraph that will give us the desired tree graph with the end vertices of degree 1.
Week 6:
After meeting with my mentor and receiving feedback from him, I revised the proof of the claw graph as a forbidden subgraph for the competition graph of our relation. Furthermore, I started the introduction of my summer report by defining some terms and summarizing some literatures that are relevant to our problem. For this week, I became more proficient using LaTeX to type up my documents. Moreover, I started working on my final presentation, which will be presented on July 18, 2014. I also continued to work on the problem generalized to all finite posets.
Week 7:
I continued to work on the problems while also preparing for a final presentation on Friday. I am also working on final summary report. On my summary report, I included some figures which help illustrate the idea of a definition or proof. I got together with my mentor to get feedback from him so we can properly present our results to the audience. Finally, my coworkers and I presented our results on Friday July 18, 2014. The second presentation has been uploaded to the link at the bottom.
Week 8:
I am working on the summary report and continuing working on the future problems. I have so far completed introduction of the summary report.
Week 9:
This week I will focus on completing my summary report. My coworkers and I will be presenting our project briefly to high school students for the program of Young Scholars. The presentation will last for about 5 minutes. The next 55 minutes will be devoted for high school students to ask questions regarding research or college experience.

Presentations

Literature References

Additional Information