How can we understand the structure of an enormous network? For dense graphs, Szemerédi regularity is a fundamental tool that has led to a rich theory of graph limits. However, many real-world networks are sparse, and all sparse graphs converge to zero in the dense theory. To distinguish between them, we need a more refined theory. Bollobás and Riordan took an important step in this direction by analyzing sparse graphs without dense spots, but this hypothesis rules out many important cases such as power-law distributions. In this talk, I'll review the theory of graph limits and discuss a broad extension to sparse graphs (which is joint work with Christian Borgs, Jennifer Chayes, and Yufei Zhao).

Henry Cohn is a principal researcher at Microsoft Research New England (where he was one of three founding members in 2008), and an adjunct professor of Mathematics at MIT. He received his Ph.D. from Harvard under the supervision of Noam Elkies. Dr. Cohn's research is in discrete mathematics, with interests including discrete geometry, coding theory, cryptography, combinatorics, computational number theory, and theoretical computer science. He has been the recipient of an American Institute of Mathematics Five-year Fellowship from 2000 through 2005, the Lester R. Ford Award from the MAA in 2005, and gave an invited address in combinatorics at the 2010 International Congress of Mathematicians.