Survey on Sparse Graph Limits + A Toy Example

          @misc{ scivideos_22616,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22616},
            author = {},
            keywords = {},
            language = {en},
            title = {Survey on Sparse Graph Limits + A Toy Example},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22616 see, \url{https://scivideos.org/index.php/simons-institute/22616}}
          }
          

Abstract

Abstract The theory of graph limits is an important tool in understanding properties of large networks. We begin the talk with a survey of this theory, concentrating in particular on the sparse setting. We then investigate a power-law random graph model and cast it in the sparse graph limit theory framework. The distinctively different structures of the limit graph are explored in detail in the sub-critical and super-critical regimes. In the sub-critical regime, the graph is empty with high probability, and in the rare event that it is non-empty, it consists of a single edge. Contrarily, in the super-critical regime, a non-trivial random graph exists in the limit, and it serves as an uncovered boundary case between different types of graph convergence.