Graphon Limit and Large Independent Sets in Uniform Random Cographs

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


Duration: 45:21
191 views
4

Valentin Féray (Université de Lorraine)
https://simons.berkeley.edu/node/22606
Graph Limits, Nonparametric Models, and Estimation

Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs.

Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.



Other Videos By Simons Institute for the Theory of Computing


2022-10-01Optimality of Variational Inference for Stochastic Block Model
2022-10-01Machine Learning on Large-Scale Graphs
2022-10-01Survey on Sparse Graph Limits + A Toy Example
2022-10-01Long Range Dependence in Evolving Networks
2022-09-30Stochastic Processes on Sparse Graphs: Hydrodynamic Limits and Markov Approximations
2022-09-30Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of...
2022-09-30Longitudinal Network Models, Log-Linear Multigraph Models, and Implications to Estimation and...
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


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Graph Limits Nonparametric Models and Estimation
Valentin Féray