View source for (i,j)-step competition graphs

'''Researchers:''' [[User:Babcock|Carissa Babcock]] and [[User:Maxblack45|Max Black]]

'''Mentor:''' [http://www.marquette.edu/mscs/facstaff-factor.shtml Dr. Kim A.S. Factor]

=='''Background'''==

[[File:Graphs.jpg|350px|thumb|right|Here are some tournaments and their (1,2)-step competition graphs found in the (1,2)-step competition graph of a tournament paper.]]

Joel E. Cohen, in 1968, began modeling ecosystems with competition graphs; consequently, mathematicians began developing his new mathematical object. Informally, competition graphs are collections of dots and lines representing some "competitive" relationship between two species, players, companies, etc. Formally, if we let "let ''D'' be a directed graph having no multiple edges, the competition graph of ''D'' is an undirected graph G on the same node set as ''D'' and having an undirected edge ''{u<sub>i</sub>, v<sub>j</sub>}'' if and only if there exists a third node ''u''<sub>k</sub> such that ''{v<sub>i</sub>, v<sub>k</sub>}'' and ''{v<sub>j</sub>, u<sub>k</sub>}'' are directed edges in the edge set of ''D'' "[http://reu.mscs.mu.edu/images/3/38/CharacterizingCompetitionGraphs.pdf (Dutton et al)]. Competition graphs, when applied to ecosystems, illuminate previously mysterious properties regarding a community through portraying relationships between species. The relationships they portray help identify primary and secondary extinctions between species, when exploring them. 

(1,2)-step competition graphs expand on competition graphs. We know from Dr. Factor and Dr. Merz's paper, ''The (1,2)-step competition graph of a tournament'', that the competition graph of a digraph ''D'' is contained in (a subgraph of) the (1,2)-step competition graph on D. Specifically, (1,2)-step competition graphs clearly display direct and indirect relationships between vertices; in the language of ecosystems, they display the direct and indirect relationships (up to length 2) between various species within a community. Our formal definition for these graphs comes from Factor and Merz's paper: "the (1,2)-step competition graph of a digraph ''D'', denoted ''C<sub>1,2</sub>(D)'', is a graph on ''V(D)'' where ''{x,y}'' in ''E(C<sub>1,2</sub>(D))'' if and only if there exists a vertex ''z'' not equal to ''x,y'', such that either ''d<sub>D-y</sub>''(x,z) less than or equal to 1 and ''d<sub>D-x</sub>''(y,z) is less than or equal to 2 [or vice versa]." The (1,2)-step competition graph is generalized by the (i,j)-step graph.

(i,j)-step graphs display relationships between vertices of an arbitrary length. That is, since they generalize (1,2)-step competition graphs, our formal definition comes, again, from Factor and Merz's paper: "the (i,j)-step competition graph of a digraph ''D'', denoted ''C<sub>i,j</sub>(D)'', is a graph on ''V(D)'' where ''{x,y}'' in ''E(C<sub>i,j</sub>(D))'' if and only if there exists a vertex ''z'' not equal to ''x,y'', such that either ''d<sub>D-y</sub>''(x,z) less than or equal to ''i'' and ''d<sub>D-x</sub>''(y,z) is less than or equal to ''j'' [or vice versa]". In the (''1,2'')-step competition graph, we saw indirect relationships up to 2; with the (''i,j'')-step competition graph, we can identify indirect relationships up to '' i'' and ''j''. For instance, we could let ''i' = 1, preserving direct relationships, and let ''j'' be the value of ''how'' indirect of relationships we want to  observe. Thus, with the (''i,j'')-step graph, we control the relationships we want to see. 

This project has two main goals: expanding the theory for (''i,j'')-step graphs and exploring their applications. For expanding their theory, this project may explore generalizations, applications to various families of graphs, or explorations with hypergraphs. Concerning their applications, this project may examine and implement various (1,2)-step competition graphs directed towards explaining various relations between species, explaining primary and secondary extinctions, or explaining potential for extinctions within various communities. Throughout the summer, the researchers will take this project in the directions they see fit.

=='''Objectives'''==

During this project, we will examine and explore the following:

<ol style="margin-left: 5em;">
  <li>Previous research regarding competition graphs and (1,2)-step competition graphs of food webs</li>
  <li>Competition graphs and (1,2)-step competition graphs of a specific food web</li>
</ol>

Additionally, we will further previous research by doing the following:

<ol style="margin-left: 5em;">
  <li>Furthering research on (i,j)-step competition graphs by exploring new theory and computation</li>
  <li>Applying competition graphs and (i,j)-step competition graphs in new areas</li>
</ol>

A brief overview of our goals for this 10 week process are listed below. For a complete list of our goals, click [http://reu.mscs.mu.edu/images/2/2a/Milestones.pdf here].

{| class="wikitable"
|-
|'''Week''' || '''Description'''
|-
!Week 1 (5/30/17-6/2/17): Orientation and Introductions
| 
*Complete the education mdule, ''The Biology and Mathematics of Food Webs'', by '''Thursday, 6/1/17'''
*Attend the talk at  '''11:00PM in CU 401'''
*Enter the title, description and milestones/goals into the wiki by '''Friday, 6/2''', by midnight
*Read ''(1,2)-step competition graph of a tournament'' and have questions ready for Wednesday, 6/7/2017
*Update Wiki at end of week or during week to reflect on what has been accomplished
|-
!Week 2 (6/5/17-6/9/17): Experiment with (1,2)-Step Competition Graphs Using Specific Examples
|          
*'''Meeting Wednesday, 6/7,''' with Dr. Factor
*Discuss the paper from last week--prepare to answer questions and/or ask them
*Begin reading Kaitlyn Ryan's master's thesis to explore biological background, mathematical background, and statistical information for the topic. Make notes and questions for Thursday's meeting
*Begin reading ''A Characterization of Competition Graphs''
*Attend Ethics training at '''9:00AM on 6/6 in CU 401'''
*Participate in the talk and luncheon at '''11:30AM on 6/8, CU 401'''
*Start comparing competition graphs and (1,2)-step competition graphs by using some small food webs from the initial food web packet, and by creating our own small food web examples
*Learn LaTex (Carissa--Max can tutor)
*Update Wiki at end of week or during week to reflect on what has been accomplished
|-
!Week 3 (6/12/17-6/16/17): Formulating Research Questions
|     
*Meeting with Dr. Factor on '''Tuesday, 6/13'''
*Meeting with Dr. Factor on  '''Thursday, 6/15'''
*Attend working lunch on '''Thursday, 6/15,''' where lunch will be provided
*Begin thinking about individual research questions. Discuss these during the Tuesday and Thursday meetings
*Write up findings in LaTeX
**Experiment with creating small food webs and competition graphs in LaTeX
*Update Wiki at end of week or during week to reflect on what has been accomplished
|- 
!Week 4 (6/19/17-6/23/17): Refine Research
|
* Begin looking at competition graphs and (1,2)-step (alternately some (i,k)-step) competition graphs for focus areas. Start refining the direction of research
*Continue writing up finding in LaTeX and creating figures
*Optional: meet with Dr. Factor on '''Tuesday, 6/20'''
*Attend the luncheon at '''11:30 AM on Thursday, 6/22'''
*Meet with Dr. Factor on '''Thursday, 6/22,''' focus will be on what to put on slides for next week's mini-presentations
*Update Wiki at end of week or during week to reflect on what has been accomplished
|-
!Week 5 (6/26/17-6/30/17): Mini Presentations
|
*Draft an 8 or so minute talk discussing what has been learned so far by '''11:00AM Tuesday, 6/27''', and be prepared to show it to Dr. Factor, should have some things to use already in LaTeX.
*Continue, as time allows, working on the research and placing in document
*Present mini-presentation to peers and mentors on '''Thursday, 6/29'''
*Short meeting with mentor after mini-presentations
*Update Wiki at end of week or during week to reflect on what has been accomplished
|- 
!Week 6 (7/3/17-7/7/17): Continue Individual research
|
*Continue working on research and LaTeX updates
*Meet with mentor on '''Thursday, 7/6''' to give research updates and discuss research direction
*Atend working lunch at '''11:30 AM on Thursday, 7/6'''; includes talk on making an effective poster
*Update Wiki at end of week or during week to reflect on what has been accomplished
|- 
!Week 7 (7/10/17-7/14/17): Resolve Conjectures
|
*Should have conjectures in individual areas, determine an approach to a solution or support for conjectures
*As needed: mentor meeting on '''Monday, 7/10'''
*Go to working lunch on '''Thursday, 7/13'''
*Meet with Dr. Factor on '''Thursday, 7/13'''
*Paper outline (brief) based on last week and this week's meetings, submit to Dr. Factor via email by '''Friday, 7/14''' by '''5:00 PM'''
*Update Wiki at end of week or during week to reflect on what has been accomplished
|- 
!Week 8 (7/17/17-7/21/17): Begin Finalizing Paper
|
*Meeting with Dr. Factor: '''Monday, 7/17'''; start discussing how to finalize paper and poster
*Begin finalizing results; enter theorems, figures, explanations, etc. into LaTeX and create needed Figures
*Initialize poster draft and email to Dr. Factor by '''Thursday, 7/20''' in time for mentor meeting
*Participate in working luncheon on '''Thursday, 7/20'''
*Update Wiki at end of week or during week to reflect on what has been accomplished
|
|- 
!Week 9 (7/24/17-7/28/17): Posters and Future Research (Dr. Factor Out of Town)
|
*Have updated poster emailed to Dr. Factor by '''8 PM Tuesday, 7/25'''; comments from Dr. Factor will be back by '''10 AM Wednesday'''
*Make any last minute changes and submit electronic version of poster to Dr. Brylow by '''12:00 PM on Wednesday, 7/26'''
*Finalize any results
*Construct a list regarding future research for paper
*Begin turning LaTeX writing into formal paper
*Go to luncheon on '''Thursday, 7/30'''
*Update Wiki at end of week or during week to reflect on what has been accomplished
|- 
!Week 10 (7/31/17-8/4/17): Formal Talks, Posters, Papers, and Goodbyes
|
*Draft formal talk, which is due to Dr. Factor bu '''11:00 AM Monday, 7/31'''
*Draft paper, which is due to Dr. Factor by '''11:00 AM Thursday, 8/3'''
*Attend poster session '''1:00 PM - 3:00 PM on Tuesday, 8/1'''
*Formal presentations
**'''Wednesday, 8/5, 10:00-2:00, CU 401'''
**'''Thursday, 8/6, 10:00-12:00, CU 401'''
*Paper due electronically '''Friday, 8/4''' by '''midnight''', sent to Dr. Brylow
*Update Wiki at end of week or during week to reflect on what has been accomplished
|-
|}

=='''Research Logs'''==

Each researcher keeps a log of the entire process, including reflections at the end of the week. These logs demonstrate the researcher's actual progress on their respective projects. Specifically, this determines whether or not they are actually reaching their milestones and completing their goals. If you would like to read them, click the researcher's name: [[User:Babcock|Carissa Babcock]] or [[User:maxblack45|Max Black]].