# Nathan Sponberg

From REU@MU

## Contents

# Personal Infomation

I am an undergraduate mathematics major from the University of Montana in Missoula Montana; I also have a minor in both computer science and Chinese language. I am currently working with Dr. Kim Factor on the Characteristics of the (i,j)-Step Competition Graphs of Real Food Webs project.

# Summer Research Topics

We will be exploring the theory and behaviour of (i,j)-step competition graphs of real food webs. This research will be informed by Cohen's work from the 1960s developing competition graphs for ecosystems as well as material on bio-math developed by Rutgers University and graph theory texts such as those by Fred Roberts and Michael Parmenter. Some initial areas of interest that we will explore include:

- Using known food webs to help develop conjectures/results concerning properties of (i,j)-step competition graphs based on these real food webs.

- Attempt to find forbidden subgraphs.

- Develop constraints for (i,j)-step competition graphs based on results garnered from actual food webs.

- Implement computer simulations/models of competition graphs and/or food webs using graph theory.

- Examine properties of food webs and their affects on and relation to the food web's corresponding competition graph (e.g. connectedness and completeness of the food web and competition graph).

- Determining the minimum and maximum number of arcs in a food web that generates a competition graph with specific properties.

# Summer Goals/Milestones

## Week 1:

- Complete the education module, “The Biology and Mathematics of Food Webs”, by Friday, 5/31/2013
- Enter the title, description and milestones/goals into the Wiki by Friday, 5/31/2013, midnight
- Update Wiki at end of week or during week to reflect what has been accomplished
- Begin working on graph theory exercises to obtain background

## Week 2:

- Go over basic graph theory material in textbooks, do problems, and have questions ready for meeting with mentor by 11:00 AM Tuesday, 6/4
- Read and discuss “A Characterization of Competition Graphs”
- check out the text Community food webs: Data and theory (Springer-Verlag, New York, 1990) or order from library
- Participate in the talk and luncheon at 12:00 on 6/4
- Participate in the luncheon at 11:30 on 6/6
- Practice LaTeX after Tuesday by typing in some of the background material from the paper into a format you can use in your final paper
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 3:

- Read and discuss paper #2 “Competition Graphs of Strongly Connected and Hamiltonian Digraphs”, and be prepared to present material on Thursday prior to lunch (to mentor)
- Come up with examples of competition graphs of strongly connected digraphs to illustrate the paper
- Find material regarding food webs that answers questions regarding the assumed maximum height of a food web; find examples of real food webs; compare and find the competition graphs of the food webs
- Attend the talk at 12:00 PM on Tuesday, 6/11
- Begin to read paper #3 or “The (1,2)-step Competition Graph of a Tournament”;
- Start to compare the competition graphs and (1,2)-step competition graphs by using some small food webs from the initial food web packet, and by creating your own small food web examples.
- Attend the luncheon at 11:30 AM on Thursday, 6/13
- Try to use LaTeX to write up some of your findings
- Find a way to draw a small food web on the computer; when successful, find a way to import it into your LaTex manuscript.
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 4:

- Begin to look at properties of the (1,2)-step competition graph (connected other than basal species vertices, complete other than basal species, etc.) (Nate, you might want to start looking at some algorithmic directions)
- What must be true about the food web for this to happen?
- What are the min/max number of arcs that allow this property?
- Are there families of digraphs that give this property?
- Are there certain digraph structures that insure the property will never happen (forbidden subdigraphs)?
- Does this change for (i,k)-step competition graphs when we have something other than i=1 and k=2?
- Are there times when there will be no new edges added in the (i,k)-step competition graphs as we increase the values for i and k?
- Continue to write up findings in LaTeX and create figures
- You may, instead, want to look at specific structures of the food web and see what properties they induce in the (1,2)-step competition graph. I would suggest NOT doing both!
- Meet with mentor on Tuesday, 6/18 (time TBD)
- Attend the luncheon at 11:30 AM on Thursday, 6/20 and meet with mentor after
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 5:

- Have a draft 8 – 10 minute talk prepared on what has been learned so far by 11:00 AM Tuesday, 6/25, and be prepared to practice it with your mentor. You should have some things that you can use already in *LaTeX, so hopefully this will not be too labor intensive
- Continue, as time allows, to work on the first bullet point of Week 4
- Present 8 – 10 minute informal talk to peers and mentors on Thursday, 6/27
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 6:

- Continue working on the first bullet point and LaTeX updates
- Go to the talk on Tuesday, 7/2
- Meet with mentor on Tuesday, 7/2 and re-evaluate where you are in your research and where you should be in two weeks; restructure goals and milestones accordingly
- Thursday, 7/4, is a holiday—RELAX and have some fun!
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 7:

- Continue according to re-evaluation of Week 6; we should start to see a very specific goal in our sites by this time and be working toward it. Any computer programs need to be beyond the algorithm-design phase and be in testing phase.
- Go to luncheon on Thursday, 7/11
- Meet with mentor on Tuesday and Thursday
- Paper outline (brief) due to mentor via email by Friday, 7/12 at 5:00 PM
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 8:

- Begin to finalize some of the results you have; enter theorems, etc. into LaTeX and create needed figures
- Initialize your poster draft and email it to mentor by Thursday; comments will be back to you during the weekend for finalization next week
- Participate in the luncheon on Thursday, 7/18
- Meet with mentor on Tuesday and Thursday of this week as needed
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 9:

(Mentor out of town)

- Have updated poster emailed to mentor by 5 PM Monday, 7/22; comments should follow by Tuesday
- Make any changes to the poster on Tuesday; submit the electronic version to both: brylow-reu@mscs.mu.edu and kim.factor@marquette.edu by 12:00 PM on Wednesday, 7/24
- Finalize any results
- Carefully construct a “future research” list that will go into your paper
- Begin to turn your LaTeX writings into a formal paper (base it on papers you have read regarding competition and (i,k)-step competition)
- Go to luncheon on Thursday, 7/25
- Update Wiki at end of week or during week to reflect what has been accomplished

## Week 10:

- Draft of formal talk due 11:00 AM Monday, 7/29 to mentor
- Draft of paper due to mentor by 11:00 Monday, 7/29
- Poster session 1:00 – 3:00 PM on Tuesday, 7/30
- Formal presentations (times TBD) on Thursday and possibly Wednesday (8/1 and 7/31 respectively)
- Paper due electronically Friday, 8/2 by midnight; send to both brylow-reu@mscs.mu.edu and kim.factor@marquette.edu
- Last update of Wiki due Friday, 8/2

# Log

## Week 1

**Tuesday 05/28/2013:**Orientation and program logistics, nothing terribly interesting.

**Wednesday 05/29/2013:**Completed food webs packet and began reading Applied Combinatorics by Fred Roberts (Chapter 3 Intro to Graph Thoery)

**Thursday 05/30/2013:**Continued reading Applied Combinatorics as well as Discrete Mathematics with Graphy Theory. Met with Dr. Factor and Linsey, discussed background material needed for research and presentation guidelines for the end of the program.

**Friday 05/31/2013:**Continued reading Combinatorics as well as Discrete Mathematics with Graphy Theory, started on exercise sets from these books. Typed up some sample proofs in latex as well has some simple graphs using the tikz graphics library in latex. Found python packages for coding graph theory applications, will probably use networkx or python-graph. Entered milestones/goals into wiki page.

## Week 2

**Monday 06/03/2013:**Finished the readings from Applied Combinatorics and Discrete Mathematics with Graph Theory as well as most of the exercise sets from the assigned sections.

**Tuesday 06/04/2013:'**Finished most of the exercises sets from readings, worked on some proofs with Lindsey. Attended the latex and proper citation methods talk. Met with Dr. Factor, Lindsey and Kenny and discussed progress so far and obtained further reading material (journal publications concerning graph theory and food webs). Began reading journal articles.

**Wednesday 06/05/2013:**Continued reading journal articles, discussed them with Lindsey. Looked at ECOWeb food web database.

**Thursday 06/07/2013:**Finished reading first three journal articles and discussed them briefly with Lindsey. Reread graph theory articles to check understanding articles. Found additional graph making packages for LaTeX: tzk-graph and tzk-berge. Began reading final two articles: "Competition Graphs of Strongly Connected and Hamiltonian Digraphs" and "The (1,2)-step competition graph of a tournament."

**Friday 06/08/2013:**Finished "Competition Graphs of Strongly Connected and Hamiltonian Digraphs" and continued with final paper. Continued to investigate graphics packages for LaTeX.

## Week 3

**Monday 06/10/2013:**Finished reading "The (1,2)-step competition graph of a tournament." Began thinking about questions to ask and identifying topics that are still unclear. Played with some graphs and started thinking about ways to characterize competition graphs from non-tournament digraphs. Found more materials and documentation for graphics packages in LaTeX. Generated a few examples of graphs in LaTeX.

**Tuesday 06/11/2013:**Attended Lunch talk on good talks/papers. Reviewed papers and continued to identify questions and areas that where still not fully understood. Made some examples of digraphs and competition graphs in LaTeX.

**Wednesday 06/12/2013:**Continued to review journal articles and double check understanding. Created some examples graphs from the theorems and proofs in the articles. Wrote out rough draft of an algorithm for generating a given digraph's competition and (1,2)-step competition graph. Experimented with using Bibtex for generating bibliographies in a paper.

**Thursday 06/13/2013:**Met with Dr. Factor and reviewed journal articles and check understanding of some concepts, discussed potential research questions and ideas. Attend working lunch and listened to Dr. Factor's sample research talk concerning (1,2)-step competition graphs. Reviewed and checked understanding of material covered with Dr. Factor. Discussed some research ideas with Lindsey. Created a bibliography database for LaTeX papers, included all journal articles read so far. Started writing up some for the results from articles that maybe useful for research. Found another article, "A Characterization of Competition Graphs of Arbitrary Digraphs" by Roberts and Steif (mentioned in a previous article). This maybe useful for helping to characterize (1,2)-step competition graphs of real food webs.

**Friday 06/14/2013**Continued writing up some summaries of the articles that were read and picking out points that seemed particularly relavent. Spend some more time familarizing myself with graphs in latex. Began thinking about and formulating what my specific research topic will be.

## Week 4

**Monday 06/17/2013**Finished summarizing important parts of journal articles. Developed a set of criterion to use for digraphs that could represent real food-webs. I believe this will be the area I will be most of my research in. Played around with digraphs and their corresponding (1,2)-competition graphs in order to start looking at what sort of structures and characteristics the graphs of real food-webs will have.

**Tuesday 06/18/2013**Refined the criterion for a "real" food-web a bit, this may benefit from further restrictions to make it more accurately match the structure of actual food webs. Continued to play around with graphs, started looking at how isolated vertices and components in the (1,2)-competition graph relate to a corresponding digraph. Found a couple of minor results and began writing up proofs.

**Wednesday 06/19/2013**Finished proofs for yesterdays results. Continued playing with digraphs and their competition graphs. No new results today other than some counter examples to a few minor conjectures I had made.

**Thursday 06/20/2013**Attended working lunch with other REU participants and listen to Dennis give a talk on embedded systems. Had a meeting with Dr. Factor and Lindsey to check in with where we were at, discussed further research ideas, proof writing techniques and work so far. Talked with Lindsey briefly afterwards and went over criterion for a digraph that represents a real food-web. I do think it might be good to expand upon this set of restrictions as I can currently construct "real" food webs with many top predators and only a single basal species. Continued to play with graphs, proved a couple more minor results I had been working towards, still need to do a more formal write up of them.

**Friday 06/21/2013**Watched RCR videos in preparation for RCR training next week. Continued to work with graphs looking at isolated vertices. Read some of Cohen, Braind and Newman's book*Community Food Webs*in an attempt to find further restrictions for a real food web.

## Week 5

**Monday 06/24/2013**Started to write up results from last week and began work on putting together the short presentation for Thursday. Had to learn about using beamer in latex and had to rewrite some results from before due to computer issues.

**Tuesday 06/25/2013**Finished writing some initial slides to show to Dr. Factor. Met with Dr. Factor and Lindsey to discuss presentation, go over slides and talk about progress so far. Finished writing up results from last week and sent them to Dr. Factor. Continued to work on presentation.

**Wednesday 06/26/2013**Continued to learn how to use beamer and put together presentation. Attended the RCR training talk. Rewrote some previous results and finished putting together my presentation. Did a practice run of the talk with my roommates.

**Thursday 06/27/2013**Attended peer research talks and presented my own research project summary. Did some editing to previous results and corrected some errors.

**Friday 06/28/2013**Finally was able to focus solely on research today! Reformatted all of my results from before so that they are easier to transfer to other papers and presentations and corrected an error in one of my proofs. Read more from*Community Food Webs*. It seems that it maybe difficult to impose a hard and fast restriction on the proportion of basal, intermediate and top species in a food web. The statistical analysis supports this but has a high degree of variance, will need to consider this further. Additionally I believe I have come up with an initial result regarding the relationship between isolated vertices and basal vertices in a (1,2)-step competition graph. Will write up result next week or over the weekend.

## Week 6

**Monday 07/01/2013**Considered whether or not to try and work more with ratios of basal species to total number of isolated vertices. The restrictions on proportions of basal species and top predator I was considering seem to not be very realistic and the number of non-basal isolated vertices seems to be very dependent on path maximum path length as well. May work on other ideas for now and come back to this later. Also realized that a counter example I had come up with before was incorrect, will investigate related idea further.

**Tuesday 07/02/2013**Attended the talk on what makes a good research poster for lunch to day. Also continued to look at pendant vertices in the (1,2)-step competition graph. Came up with a characterization of a pendant vertex in the competition graph and how it is connected in the related digraph. Began writing up this result. This should lead into a further result for pendant vertices (which I had previously thought I had a counter example for).

**Wednesday 07/03/2013**Still unsure about the result for pendant vertices, may have found a different counter example that actually works. Attempted to write a lemma characterizing a pendant vertex in a competition graph, had some difficulties word it in an easy way to prove, will come back to this. Also started looking at components of a competition graph that are complete subgraphs.

**Thursday 07/04/2013**Walked down to lake, drank beer.

**Friday 07/05/2013**Continued to explore the structure of vertices in an acyclic digraph that induce a component in the competition graph that is complete. I believe I have uncovered a pattern here for the minimum number of direct connects in such a component. However prove this seems like it may not more difficult.

## Week 7

**Monday 07/08/2013**Continued work on minimizing the number of direct connections in a complete component in a (1,2)-competition graph.

**Tuesday 07/09/2013**Continued work from Moday, found a contradiction to my previous formula for the number of direct competitions. Will need to develope a different approach. Met with Dr. Factor and Lindsey today as well, disscussed what our goals should be for the last couple of weeks of research. Think I will focus on this family of digraphs that I have been looking at and see if I can prove that they minimize the number of direct competitions.

**Wednesday 07/10/2013**Continued with work from earlier in the week. Developed new formulas for the number of direct competitions that are generated by the digraphs I have been looking at. These appear to work for any number of vertices and I should be able to prove them using a counting argument, however I will need to prove that the digraphs I am working with always induce a complete component on n vertices. Will work on this tomorrow. An interesting side note, the ratio of direct competetitions to indirect ones that are generated by thsese digraphs appears to converge towards 1/2 as the number of vertices grows.

**Thursday 07/11/2013**Met with Lindesy and Dr. factor again and went to working lunch and discussed grad school with Dennis and Dr. Factor and other REU participants. Generated some graphs in latex of the family of digraphs I have been working with this week. Also wrote up a rough sketch of the iterative constrictive proof for generating the digraphs and their related complete competition graphs. Will finish this tomorrow and start writing up more formal proofs in latex.