Robert Jamison (UIUC Math and Clemson University) Sum-Tolerance Graphs with Eutactic Rank Abstract: This talk will focus on certain classes of rank-tolerance graphs that generalize the co-threshold-tolerance (co-TT) graphs introduced by Monma, Reed, and Trotter. In a rank-tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance, which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if and only if their joint rank exceeds (or equals) their joint tolerance. This study is motivated by the class SP of sum-product graphs, introduced by Golumbic and RJ, where the tolerance coupling function is the sum of the two tolerances and and the rank coupling function is the product of the two ranks. Many properties of sum-product graphs remain valid when product is replaced by a general eutactic function --- one that satisfies a certain convexity condition. The class of eutactic functions is quite broad. For example, it includes all symmetric polynomials (in two variables) with positive coefficients. We show that SP strictly contains co-TT as well as all complete bipartite graphs $K_{2,n}$, and we survey a number of other results. My advisor Victor Klee vowed as graduate student that he would avoid formulae involving binomial coefficients. I vowed that I would never get involved with multidimensional calculus. In the talk I will explain (briefly) why we were both wrong. |