Sparse Random Graphs with Many Triangles

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=IcIbOe6g8CQ


Duration: 51:26
355 views
15

Suman Chakraborty (Leiden University)
https://simons.berkeley.edu/node/22599
Graph Limits, Nonparametric Models, and Estimation

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.



Other Videos By Simons Institute for the Theory of Computing


2022-09-30Graphon Games
2022-09-30Vertexons and Embedded Graphon Mean Field Games
2022-09-30Motif Counting via Subgraph Sampling
2022-09-29Graphon Limit and Large Independent Sets in Uniform Random Cographs
2022-09-29Graphon-valued Stochastic Processes
2022-09-29Higher-order Fluctuations in Dense Random Graph Models
2022-09-29A theory for graph embedding methods and...
2022-09-28Recent Developments on Graph Norms
2022-09-28The Degree-Restricted Random Process Is Far From Uniform
2022-09-28On the Second Kahn-Kalai Conjecture
2022-09-28Sparse Random Graphs with Many Triangles
2022-09-28Efficiently Exploiting Model Structure in Network Causal Inference with and without...
2022-09-28Symmetry and Convergence
2022-09-28Higher Order Fluctuations in Dense Random Graph Models
2022-09-27A Deterministic Theory of Low Rank Matrix Completion
2022-09-27Common Graphs with Arbitrary Chromatic Number
2022-09-27Higher-Order Graphon Theory: Fluctuations, Inference, and Degeneracies
2022-09-27A Large Deviation Principle for Block Models
2022-09-27Mean-field approximations for high-dimensional Bayesian Regression
2022-09-27Response of Graphs to Competing Constraints
2022-09-27Sparse Random Graphs: Interplay of Local and Global Structure


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