On exchangeable random variables and the statistics of large graphs and hypergraphs

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ász and Szegedy [52], Borgs, Chayes, Lovász, Só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 $\mathbb{Z}$-systems, which underpins Furstenberg's ergodic-theoretic proof of Szemeré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.

Published in at http://dx.doi.org/10.1214/08-PS124 the Probability Surveys (http://www.i-journals.org/ps/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Graph limits and exchangeable random graphs
• Universal Characteristic Factors and Furstenberg Averages

Cited by in corpus (25)

• Matrix estimation by Universal Singular Value Thresholding
• Estimating and understanding exponential random graph models
• Random graphs with a given degree sequence
• Spin glass models from the point of view of spin distributions
• Sampling perspectives on sparse exchangeable graphs
• Computable de Finetti measures
• Invariant measures concentrated on countable structures
• Hypergraph limits: a regularity approach
• Decomposition of tournament limits
• The full replica symmetry breaking in the Ising spin glass on random regular graph
• Ranks, copulas, and permutons
• Semantic Limits of Dense Combinatorial Objects
• An example of graph limits of growing sequences of random graphs
• Relating the cut distance and the weak* topology for graphons
• Priors on exchangeable directed graphs
• A classification of orbits admitting a unique invariant measure
• Invariant measures via inverse limits of finite structures
• Cut distance identifying graphon parameters over weak* limits
• Cut-norm and entropy minimization over weak* limits
• Gradient flows on graphons: existence, convergence, continuity equations
• From flip processes to dynamical systems on graphons
• Random projectors with continuous resolutions of the identity in a finite-dimensional Hilbert space
• Stochastic optimization on matrices and a graphon McKean-Vlasov limit
• Zero-one laws for events with positional symmetries
• The Aldous$\unicode{x2013}$Hoover Theorem in Categorical Probability