Research Experience for Undergraduates (REU) Seminar

Speaker: Robert E. Jamison, Professor of Mathematical Sciences, Clemson University
Title: Rank Tolerance Graph Classes
Time and location: 12:30 pm - 2 pm, CoRE A, Room 301, Rutgers University.

Lunch will be served.

Abstract

The objects of study in this talk arise from a natural extension of ideas that have grown out of the now classical notion of interval graph. In an interval graph, each vertex is associated with an interval on the real line with two vertices adjacent if and only if their associated intervals intersect. In 1982 Golumbic and others suggested associating "tolerances" with each interval so that now two vertices are joined iff the length of the intersection of their associated intervals is at least the minimum of the two tolerances. In 1987 McMorris and others proposed replacing the min function above by other joint tolerance functions, such as max or sum an arbitrary function phi. In the investigation of phi-tolerance interval graphs, a particular case appeared to be of recurring interest - namely, when all the intervals are nested to form a chain under inclusion. In this case, the length of the intersection is just the minimum of the two lengths, and only the lengths, and not the actual intervals play a role in determining adjacency. One can thus think of a phi-tolerance chain interval graph as arising from the assignment of two numbers tv and rv to each vertex v of the graph. The first of these, tv, is just a tolerance at the vertex v as before. The second, rv, represents a rank (or size) associated with the vertex v. Then two vertices v and w are adjacent provided the minimum of their two ranks exceeds their joint tolerance - that is,

phi(tv,tw) < = min(rv,rw).

In this paper we will explore the extension that arises when the min on the right is also allowed to be replaced by a more general function rho.