Response of Graphs to Competing Constraints

          @misc{ scivideos_22590,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22590},
            author = {},
            keywords = {},
            language = {en},
            title = {Response of Graphs to Competing Constraints},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22590 see, \url{https://scivideos.org/simons-institute/22590}}
          }
          

Abstract

Abstract We discuss recent theorems on both smooth and singular responses of large dense graphs to changes in edge and triangle density constraints. Smoothness requires control over typical (exponentially most) graphs with given sharp values of those two densities. In particular we prove the existence of a connected open set S in the plane of edge and triangle densities, cut into two pieces S' and S" by the curve C corresponding to graphs with independent edges. For typical graphs G with given edge and triangle densities, every subgraph density of G is real analytic on S' and S" as a function of the edge and triangle densities. However these subgraph densities are not analytic, or even differentiable, on C. Joint work with Joe Neeman and Lorenzo Sadun.