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

By Tim Austin. 2008

134 citations recorded by the source corpus.

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 Lovasz and Szegedy [52], Borgs, Chayes, Lovasz, Sos, 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 Szemeredi’s Theorem. The forthcoming paper [10] will make a much more elaborate appeal to the link between exchangeable laws and dense (directed) hypergraphs to establish various results in property testing.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6c78b4647d0bb3f7a6a9a2f34d2b17dcad3b7336

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “The latter defines M via noise outsourcing (Austin, 2008).”
Tensor decompositions for learning latent variable models (2012, background): “The well-known De Finetti’s theorem (Austin, 2008) implies that such exchangeable models can be viewed as mixture models in which there is a latent variable h such that x1, x2, .”
Random graphs with a given degree sequence (2010, background): “See also the related work of Diaconis and Janson [19] and Austin [2] which traces this back to work of Aldous [1] and Hoover [28].”
Estimating and understanding exponential random graph models (2011, background): “(See also the related work of Austin [3] and Diaconis and Janson [18] which traces this back to work of Aldous [1], Hoover [33] and Kallenberg [35].)”
Large Networks and Graph Limits (2012, background): “A notion closely related to testability and to computing a structure, called “local reparability”, was introduced by Austin and Tao [2010]. We only give an informal definition.”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “’ was coined by Lovasz and coauthors in the growing literature on limits of dense graphs [21, 22, 23, 72, 73, 74]. Such functions also arise in the related study of weakly exchangeable random arrays [43, 9, 6, 59]. They have also appeared recently in large deviations [33, 34, 75] and mathematical st”
Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, background): “Alternative perspectives and refinements were given in [8, 94, 187, 188].”
Graphons, cut norm and distance, couplings and rearrangements (2010, background): “(This representation is essentially equivalent to the representation by Aldous and Hoover of exchangeable arrays of random variables, see [43] for details of this representation and [4, 24] for the connection, which is summarized in Appendix D.”
Probability and Mathematical Genetics: More uses of exchangeability: representations of complex random structures (2009, background): “ork started in [47] has been developed further to produce new and interesting results in graph theory – see e.g. [21]. 5.2 Further uses in ﬁnitary combinatorics The remarkable recent survey by Austin [12] gives a more sophisticated treatment of the theory of representations of jointly exchangeable a”
INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES (2012, methodology): “This characterization has also arisen in the theory of dense graph limits; for details see [17] and [5].”
A hierarchical version of the de Finetti and Aldous-Hoover representations (2013, result): “[2], Chapters 7–9 in [11], or [3], [4] and [5] for recent overviews and results) and the g oal of this paper is to study another notion of exchangeability that is motivated by spin glass mo dels and, in particular, by the work of Mézard and Parisi on diluted models, [12].”