Mathematics Colloquium
Date:Lincoln NE 68508
Affiliation: UNL
Local Host: Jamie Radcliffe
Title: An Introduction to Graph Limit Theory
Additional Public Info:
In recent decades, the study of very large networks has become important to many of the sciences. Examples of these networks include the Internet, social networks, and the human brain. These networks often have billions of nodes, and it is often impossible to describe them completely. How, then, can we measure, model, and approximate these large networks?
In recent years, the work of László Lovász and co-authors has provided one approach to these complex questions in the form of a theory of limits of sequences of dense graphs (that is, graphs that contain a positive proportion of the number of possible edges). This theory provides a notion of convergence for sequences of dense graphs.
Graph limit theory asks questions about combinatorial objects, but it often uses analysis to answer them. In particular, the limit of a convergent graph sequence can be represented by a symmetric, measurable, real-valued function on the unit square. Moreover, the theory of convergent graph sequences leads to interesting topological and algebraic questions.
In this talk, I will present a brief introduction to this theory and discuss a few of its applications. In particular, I will describe a joint result with Svante Janson on the number and typical structure of graphs that satisfy an arbitrary monotone graph property, and I will discuss one or two connections between graph limit theory and other fields.
Refreshments will be served in 348 Avery, 3:30-4:00. The talk is free and open to the public.