(DREI 999)



DREI will be selling their annual program T-shirt for $ 10.00 per shirt. The T-shirt includes the DIMACS and DREI logo and the title for the current year. Please detach and fill out the bottom portion of the sheet and send it with your payment to:


DIMACS / DREI '99 T- shirts

96 Frelinghuysen Road

Piscataway, NJ 08854


Please detach the bottom portion and mail it to us with your payment.






FIRST NAME:________________________ LAST NAME:__________________________




CITY:____________________________________ STATE:________ ZIP CODE:_________


DAYTIME PHONE:_________________________ E-MAIL:_______________________________






AMOUNT ENCLOSED: $___________________


Sorry, we do not accept credit cards!




Ecologists study the relationships among organisms in communities. From the point of view of biology, this study is a crucial step in the understanding of the "web of nature." From the point of view of society, this study is important to understand how social endeavors would perturb ecosystems. In ecology, a species is sometimes characterized by the ranges of all of the different environmental factors which define its normal healthy environment. For example, the normal healthy environment is determined by a range of values of temperature, of light, of pH, of moisture, and so on. If there are n factors in all, and each defines an interval of values, then the corresponding region in n-space is a box. This box corresponds to what is frequently called in ecology the ecological niche of the species. Hutchinson for example, defines the ecological niche as "the sum of all the environmental factors acting on an organism; the niche thus defined is a region of n-dimensional hyper-space, comparable to the phase-space of statistical mechanics." For this reason, the n-dimensional Euclidean space defined by the n factors is sometimes called ecological phase space.' Suppose we have some independent information about when different species' niches overlap. We can then ask how many dimensions are required of an ecological phase space so that we can represent each species by a niche or box in this space and so that the niches overlap if and only if the independent information tells us they should. This question can be formulated graph-theoretically. Draw a niche overlap graph whose vertices are a collection of species from an ecosystem, and which has an edge between two species if and only if their ecological niches overlap. We wish to determine the smallest n so that the niche overlap graph is the intersection graph of boxes in n-space, i.e., we wish to determine the boxicity of the niche overlap graph.

How do we define the niche overlap graph? One way is to use the notion of competition. For it is an old ecological principle that two species compete if and only if their ecological niches overlap. By studying the species in an ecosystem, we can obtain information about which species prey on which others. We can represent this information in a digraph, whose vertices are the species in question and which has an arc from species x to species y if and only if x preys on y. This digraph is called a food web. Given a food web, we shall assume, following Cohen that two species have overlapping niches (at least along trophic or "feeding" dimensions) if and only if they have a common prey. That is, niche overlap occurs if and only if the species compete for food.The figure below shows a food web and the corresponding niche overlap graphs. Note, for example, that species 1 and 4 both prey on species 5; hence there is an edge between vertices 1 and 4 in the niche overlap graph.The niche overlap graph of the figure is a rather simple graph, and it is easy to see that it is an interval graph which is incomplete. Hence, its boxicity is 1. The conclusion is that one dimension suffices to account for niche overlap in this ecosystem.

From Food web and niche overlap graph for the Strait of Georgia, British Columbia. From data of Parsons and LeBrasseur , as adapted by Cohen.