Response of Graphs to Competing Constraints

Published on ● Video Link: https://www.youtube.com/watch?v=qMwgUFONojo



Duration: 46:30
157 views
0


Charles Radin (University of Texas)
https://simons.berkeley.edu/node/22590
Graph Limits, Nonparametric Models, and Estimation

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.







Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Graph Limits Nonparametric Models and Estimation
Charles Radin