Author: Robert A. McGuigan, Department of Mathematics, Westfield State College.
Prerequisites: The prerequisites for this chapter are basic concepts of graph theory. See Sections 9.1 and 9.2 of Discrete Mathematics and Its Applications.
Introduction A food web is a directed graph modeling the predator-prey relationship in an ecological community. We will use this directed graph to study the question of the minimum number of parameters needed to describe ecological competition. For this purpose we will consider how graphs can be represented as intersection graphs of families of sets.
We will also investigate the axiomatic description of measures of status in food webs.
Competition In an ecological system, the various species of plants and animals occupy niches defined by the availability of resources. The resources might be defined in terms of factors such as temperature, moisture, degree of acidity, amounts of nutrients,
226 Applications of Discrete Mathematics
and so on. These factors are subject to constraints such as temperature lying in a
certain range, pH lying within certain limits, etc. The combination of all these constraints for a species then defines a region in n-dimensional Euclidean space, where n is the number of factors. We can call this region the ecological niche of the species in question.
For example, suppose we restrict ourselves to three factors, such as tem- perature, nutrients, and pH. Assume that the temperature must be between t1 and t2 degrees, the amount of nutrients between n1 and n2 and the pH be- tween a1 and a2. Then the ecological niche these define occupies the region of 3-dimensional Euclidean space shown in Figure 1.
Figure 1. An ecological niche.
Euclidean space which has as dimensions the various factors of tempera- ture, pH, etc., is called an ecological phase space. Generally, no two distinct species will have the same ecological niche in phase space; however, two species compete if their ecological niches have non-empty intersection. A basic prin- ciple of ecology, known as the principle of competitive exclusion, dictates that species whose niches are too similar, or overlap too much, cannot coexist. If the factors defining the niche are independent, then the niche in phase space would be a box such as that in Figure 1. If the factors are not independent, i.e. the level of one depends on levels of others, then the niche would be some other type of set, e.g. convex, but not a box.
For example, consider the two factors temperature (t) and per cent humid- ity (h). We might have constraints such as: t must be between 0 and 100, and h must be between 0 and 100t − t2. In this case temperature and humidity are not independent; the possible values of h depend on the values of t. The region in two-dimensional space defined by these constraints is not a rectangle.
Our discussion of ecological communities and related concepts such as
Chapter 13 Food Webs 227
species, food webs, and competition will be somewhat oversimplified in order to make a brief presentation possible. Interested readers should consult refer- ence  for an in-depth treatment of these topics. Our mathematical treatment follows that of reference .
Food Webs It may be difficult to know all the factors which determine an ecological niche, and some factors may be relatively unimportant. Hence it is useful to start with the concept of competition and try to find the minimum number of dimensions necessary for a phase space in which competition can be represented by niche overlap.
One approach to this question is to consider the notion of the food web of an ecological community.
Definition 1 A food web of an ecological community is a directed graph with a vertex for each species in the community and a directed edge from the vertex representing species A to the vertex representing species B if and only if A preys on B.
Figure 2 shows a simple food web for a community of seven species: robin, fox, grasshopper, raccoon, salamander, milksnake, and toad.
Figure 2. A simple food web.
We can define competition using the food web. Two species compete if and only if they have a common prey. Thus, in the example of Figure 2, raccoon and fox compete (since robin is a common prey), milksnake and raccoon compete,
228 Applications of Discrete Mathematics
while salamander and robin do not compete. We use this competition relation to define a graph called the competition graph.
Definition 2 The competition graph of a food web is a simple graph with a vertex for each species. Two vertices are joined by an (undirected) edge if and only if the species they represent have a common prey.
Example 1 Find the competition graph for the food web of Figure 2.
Solution: The competition graph for this food web is shown in Figure 3.
Figure 3. A competition graph.
To represent the competition relation in phase space we want to assign to each vertex of the competition graph a subset of Euclidean space of some di- mension in such a way that two vertices are joined by an edge in the competition graph if and only if the sets assigned to these vertices have non-empty inter- section. Figure 4 shows a representation of the competition graph of Figure 3, using an interval for each vertex. We have thus represented the competition graph using only one dimension.
Figure 4. Interval representation of a competition graph.
We can now state a general mathematical problem, but first we need to develop some terminology.
Chapter 13 Food Webs 229
Definition 3 A graph is an intersection graph for a family of sets if each vertex is assigned a set in such a way that two vertices are joined by an edge if and only if the corresponding sets have non-empty intersection.
Definition 4 A graph is called an interval graph if it is the intersection graph for a family of closed intervals.
Our goal is the representation of competition graphs of families of sets in Euclidean n-space. Clearly the simplest case would be that of competition graphs that are interval graphs. This would mean that only one ecological factor is necessary to describe niche overlap.
Example 2 Find the interval graph for the family of closed intervals A = [1, 3], B = [2, 6], C = [5, 8], D = [4, 5].
Solution: We use the definition of intersection graph to obtain the graph of Figure 5.
Figure 5. An intersection graph.
Example 3 Prove that the 4-cycle graph C4 of Figure 6 is not an interval graph.
Solution: The proof depends on the order properties of the real numbers. Let the interval corresponding to vertex n be [nl, nr]. Since the intervals for vertices 1 and 2 overlap, we must have either 1l ≤ 2l ≤ 1r ≤ 2r or 2l ≤ 1l ≤ 2r ≤ 1r, Assume for specificity that 1l ≤ 2l ≤ 1r ≤ 2r. The argument for the other case is analogous.
Since the interval for vertex 3 must meet that for vertex 2 and must not meet that for vertex 1, we must have 1l ≤ 2l ≤ 1r < 3l ≤ 2r. Now the interval for vertex 4 must meet those for both vertices 1 and 3, so we have to have 1l ≤ 4l ≤ 1r and 3l ≤ 4r ≤ 3r since interval 1 lies entirely to the left of interval 3. However, since 2l ≤ 1r < 3l ≤ 2r, the intervals for vertices 2 and 4 overlap, which is forbidden.
230 Applications of Discrete Mathematics
Figure 6. A graph that is not an interval graph.
The 4-cycle can, however, be represented as the intersection graph of a family of boxes in Euclidean 2-space, as shown in Figure 7.
There are several methods known for determining whether a simple graph is an interval graph. A detailed discussion of this topic may be found in Roberts’ book . We simply state the characterization due to Gilmore and Hoffman  without proof. Before the characterization can be stated, we need some definitions.
Figure 7. A box representation.
Definition 5 A graph H is a generated subgraph of a graph G if the vertices of H are a subset of the vertices of G and vertices in H are adjacent in H if and only if they are adjacent in G.
Definition 6 The complement of a graph G is the graph G where the vertices of G are the vertices of G, and two vertices in G are adjacent if and only if they are not adjacent in G.
Definition 7 An orientation of a graph G is an assignment of a direction to each edge in G (which makes G into a directed graph).
An orientation is transitive if whenever (u, v) and (v, w) are directed edges, then (u, w) is a directed edge.
Chapter 13 Food Webs 231
The characterization due to Gilmore and Hoffman is given by the following theorem.
Theorem 1 A graph G is an interval graph if and only if it satisfies the following two conditions:
(i) The four-cycle C4 is not a generated subgraph of G, (ii) The complement of G is transitively orientable.
Our goal in our study of ecological competition is the representation of niches in Euclidean space and competition by niche overlap. It seems desirable in an ideal representation that the factors determining the dimension of the eco- logical phase space would be independent and the niches would be represented as “boxes”, or Cartesian products of intervals. This leads us to the next part of this discussion, namely, when can we represent a graph as the intersection graph of a family of boxes in n-space.
Definition 8 The boxicity of a graph G is the smallest n such that G is the intersection graph of a family of boxes in Euclidean n-space.
Note that an interval graph is simply a graph with boxicity equal to 1. It is not entirely clear that every simple graph has a boxicity. The following theorem resolves this difficulty.