Sparse Random Graphs with Many Triangles

          @misc{ scivideos_22599,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22599},
            author = {},
            keywords = {},
            language = {en},
            title = {Sparse Random Graphs with Many Triangles},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22599 see, \url{https://scivideos.org/simons-institute/22599}}
          }
          

Abstract

Abstract It is well known that sparse random graphs (where the number of edges is of the order of the number of vertices) contain only a small number of triangles. On the other hand, many networks observed in real life are sparse but contain a large number of triangles. Motivated by this discrepancy we ask the following two questions: How (un)likely is it that a sparse random graph contains a large number of triangles? What does the graph look like when it contains a large number of triangles? We also ask a related question: What is the probability that in a sparse random graph a large number of vertices are part of some triangle? We discuss these questions, as well as some applications to exponential random graph models.