Graph Limits for some special cases: Threshold Graphs and Interval Graphs

Susan Holmes
Department of Statistics
Stanford University


Wednesday, Feb 2, 2011
4:30 - 5:30 PM
Y2E2 101

Abstract:

I will present a limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples of this special class of graphs which have an underlying variable, very useful in applications. Graphs have important applications in modern systems biology and social sciences. However graphs are not objects which are naturally amenable to simple statistical analyses, there is no natural average graph for instance. Being able to predict or replace a graph by hidden (statisticians call them latent) real variables has many advantages. This talk studies such a class of graphs, that sits within the larger class of interval graphs itself a subset of intersection graphs.

Joint work with Persi Diaconis and Svante Janson

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html