On exchangeable random variables and the statistics of large graphs and hypergraphs
From MaRDI portal
Publication:980774
DOI10.1214/08-PS124zbMATH Open1189.60020arXiv0801.1698OpenAlexW3103788012MaRDI QIDQ980774FDOQ980774
Publication date: 29 June 2010
Published in: Probability Surveys (Search for Journal in Brave)
Abstract: De Finetti's classical result of [18] identifying the law of an exchangeable family of random variables as a mixture of i.i.d. laws was extended to structure theorems for more complex notions of exchangeability by Aldous [1,2,3], Hoover [41,42], Kallenberg [44] and Kingman [47]. On the other hand, such exchangeable laws were first related to questions from combinatorics in an independent analysis by Fremlin and Talagrand [29], and again more recently in Tao [62], where they appear as a natural proxy for the `leading order statistics' of colourings of large graphs or hypergraphs. Moreover, this relation appears implicitly in the study of various more bespoke formalisms for handling `limit objects' of sequences of dense graphs or hypergraphs in a number of recent works, including Lov'{a}sz and Szegedy [52], Borgs, Chayes, Lov'{a}sz, S'{o}s, Szegedy and Vesztergombi [17], Elek and Szegedy [24] and Razborov [54,55]. However, the connection between these works and the earlier probabilistic structural results seems to have gone largely unappreciated. In this survey we recall the basic results of the theory of exchangeable laws, and then explain the probabilistic versions of various interesting questions from graph and hypergraph theory that their connection motivates (particularly extremal questions on the testability of properties for graphs and hypergraphs). We also locate the notions of exchangeability of interest to us in the context of other classes of probability measures subject to various symmetries, in particular contrasting the methods employed to analyze exchangeable laws with related structural results in ergodic theory, particular the Furstenberg-Zimmer structure theorem for probability-preserving -systems, which underpins Furstenberg's ergodic-theoretic proof of Szemer'{e}di's Theorem. The forthcoming paper [10]--hereditarytest will make a much more elaborate appeal to the link between exchangeable laws and dense (directed) hypergraphs to establish various results in property testing.
Full work available at URL: https://arxiv.org/abs/0801.1698
Recommendations
Parametric hypothesis testing (62F03) Research exposition (monographs, survey articles) pertaining to probability theory (60-02) Combinatorial probability (60C05) Exchangeability for stochastic processes (60G09) Probabilistic measure theory (60A10)
Cited In (52)
- From flip processes to dynamical systems on graphons
- U-Statistics on bipartite exchangeable networks
- Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
- Semantic limits of dense combinatorial objects
- On a notion of partially conditionally identically distributed sequences
- General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
- Title not available (Why is that?)
- INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
- Random graphs with a given degree sequence
- Decomposition of tournament limits
- Testability and repair of hereditary hypergraph properties
- Natural quasirandomness properties
- On convergence for graphexes
- Hypergraph limits: A regularity approach
- A measure-theoretic approach to the theory of dense hypergraphs
- Matrix estimation by universal singular value thresholding
- Quantum invariant families of matrices in free probability
- Computable Exchangeable Sequences Have Computable de Finetti Measures
- Spin glass models from the point of view of spin distributions
- Cut distance identifying graphon parameters over weak* limits
- A hierarchical version of the de Finetti and Aldous-Hoover representations
- Sampling perspectives on sparse exchangeable graphs
- A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Random projectors with continuous resolutions of the identity in a finite-dimensional Hilbert space
- Deducing the density Hales-Jewett theorem from an infinitary removal lemma
- The full replica symmetry breaking in the Ising spin glass on random regular graph
- Multigraph limits and exchangeability
- Poset limits can be totally ordered
- Algebraic statistics for a directed random graph model with reciprocation
- Estimating and understanding exponential random graph models
- On the rate of convergence in de Finetti's representation theorem
- Invariant measures via inverse limits of finite structures
- Relating the cut distance and the weak* topology for graphons
- A classification of orbits admitting a unique invariant measure
- The limit theorem for maximum of partial sums of exchangeable random variables
- Computable de Finetti measures
- Coalescent results for diploid exchangeable population models
- Graph limits and exchangeable random graphs
- Tensor Decompositions for Learning Latent Variable Models (A Survey for ALT)
- An analytic approach to sparse hypergraphs: hypergraph removal
- Exchangeable interval hypergraphs and limits of ordered discrete structures
- The Cut Metric for Probability Distributions
- Interval graph limits
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- A hypergraph blow-up lemma
- A generalization of hierarchical exchangeability on trees to directed acyclic graphs
- Concentration estimates for functions of finite high‐dimensional random arrays
- Nilspace Factors for General Uniformity Seminorms, Cubic Exchangeability and Limits
- Limits of structures and the example of tree semi-lattices
- A representation of exchangeable hierarchies by sampling from random real trees
- Poset limits and exchangeable random posets
This page was built for publication: On exchangeable random variables and the statistics of large graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q980774)
