Computer Science/Discrete Mathematics Seminar I

To examine the limiting behavior of graph sequences, many discrete methods meet their continuous counterparts, leading to numerous theoretical and applicable advancements. For dense graph sequences, the graph limits have recently been well developed by many researchers, mostly based on Szemeredi's regularity partition and the algebra of graph homomorphisms. For sparse graphs with a linear number of edges, the graph limits have very different behavior and are much less well understood. In this talk, we introduce "graphlets", a spectral version of graph limits, for all graph sequences, unifying previous disparate approaches for dense and sparse graphs. We will discuss a number of advantages of graphlets including universal scalable bases, universal embeddings via heat kernels and the preservation of Cheeger cuts, for example.