Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 5 (2008) open journal systems 


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

Tim Austin, University of California at Los Angeles


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 ℤ-systems, which underpins Furstenberg’s ergodic-theoretic proof of Szemerédi’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.

Creative Common LOGO

Full Text: PDF
Austin, Tim, On exchangeable random variables and the statistics of large graphs and hypergraphs, Probability Surveys, 5, (2008), 80-145 (electronic). DOI: 10.1214/08-PS124.

References

[1]   D. J. Aldous. Representations for partially exchangeable arrays of random variables. J. Multivariate Anal., 11(4):581–598, 1981. MR0637937

[2]   D. J. Aldous. On exchangeability and conditional independence. In Exchangeability in probability and statistics (Rome, 1981), pages 165–170. North-Holland, Amsterdam, 1982. MR0675972

[3]   D. J. Aldous. Exchangeability and related topics. In École d’été de probabilités de Saint-Flour, XIII—1983, volume 1117 of Lecture Notes in Math., pages 1–198. Springer, Berlin, 1985. MR0883646

[4]   D. J. Aldous and R. Lyons. Processes on Unimodular Random Networks. Electronic J. Probab., 12:1454–1508, 2007. MR2354165

[5]   D. J. Aldous and J. M. Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. In H. Kesten, editor, Probability on Discrete Structures, volume 110 of Enyclopaedia Math. Sci., pages 1–72. Springer, Berlin, 2004. MR2023650

[6]   N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451–476, 2000. MR1804820

[7]   N. Alon and A. Shapira. A Characterization of the (natural) Graph Properties Testable with One-Sided Error. preprint, available online at http://www.math.tau.ac.il/~nogaa/PDFS/heredit2.pdf.

[8]   N. Alon and A. Shapira. Every monotone graph property is testable. In Proc. of the 37th ACM STOC, Baltimore. ACM Press, 2005. available online at http://www.math.tau.ac.il/~nogaa/PDFS/MonotoneSTOC.pdf. MR2181610

[9]   T. Austin. Razborov flag algebras as algebras of measurable functions. manuscript, available online at arXiv.org: 0801.1538, 2007. MR2371204

[10]   T. Austin and T. Tao. On the testability and repair of hereditary hypergraph properties. preprint, available online at arXiv.org: 0801.2179, 2008.

[11]   H. Becker and A. S. Kechris. The Descriptive Set Theory of Polish Group Actions. Cambridge University Press, Cambridge, 1996. MR1425877

[12]   I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13 pp. (electronic), 2001. MR1873300

[13]   I. Benjamini, O. Schramm, and A. Shapira. Every Minor-Closed Property of Sparse Graphs is Testable.

[14]   Y. Benyamini and J. Lindenstrauss. Geometric Nonlinear Functional Analysis. American Mathematical Society, Providence, 2000. MR1727673

[15]   V. Bergelson. Ergodic Ramsey Theory – an Update. In M. Pollicott and K. Schmidt, editors, Ergodic Theory of ℤd-actions: Proceedings of the Warwick Symposium 1993-4, pages 1–61. Cambridge University Press, Cambridge, 1996. MR1411215

[16]   B. Bollobás. Modern Graph Theory. Springer, Berlin, 1998. MR1633290

[17]   C. Borgs, J. Chayes, L. Lovász, V. T. Sós, B. Szegedy, and K. Vesztergombi. Graph limits and parameter testing. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 261–270, New York, 2006. ACM. MR2277152

[18]   B. de Finetti. Fuzione caratteristica di un fenomeno aleatorio. Mem. R. Acc. Lincei, 4(6):86–133, 1930.

[19]   B. de Finetti. La prévision: ses lois logiques, ses sources subjectives. Ann. Inst. H. Poincaré, 7:1–68, 1937. MR1508036

[20]   P. Diaconis and S. Janson. Graph limits and exchangeable random graphs. Preprint; available online at arXiv.org: math.PR math.CO/0712.2749, 2007. MR2346812

[21]   E. B. Dynkin. Classes of equivalent random quantities. Uspehi Matem. Nauk (N.S.), 8(2(54)):125–130, 1953. MR0055601

[22]   G. Elek. On limits of finite graphs. preprint; available online at arXiv.org: math.CO/0505335, 2005. MR2359831

[23]   G. Elek. A Regularity Lemma for Bounded Degree Graphs and Its Applications: Parameter Testing and Infinite Volume Limits. preprint; available online at arXiv.org: math.CO/0711.2800, 2007.

[24]   G. Elek and B. Szegedy. Limits of Hypergraphs, Removal and Regularity Lemmas. A Nonstandard Approach. preprint; available online at arXiv.org: math.CO/0705.2179, 2007.

[25]   P. Erd~o s and A. Hajnal. Some remarks on set theory, IX. Combinatorial problems in measure theory and set theory. Michigan Math. J., 11:107–127, 1964. MR0171713

[26]   D. G. Fon-Der-Flaass. A method for constructing (3,4)-graphs. Mat. Zametki, 44(4):546–550, 559, 1988. MR0975195

[27]   D. H. Fremlin. list of problems. available online at
http://www.essex.ac.uk/maths/staff/fremlin/problems.htm.

[28]   D. H. Fremlin. Random equivalence relations. preprint, available online at
http://www.essex.ac.uk/maths/staff/fremlin/preprints.htm, 2006.

[29]   D. H. Fremlin and M. Talagrand. Subgraphs of random graphs. Trans. Amer. Math. Soc., 291(2):551–582, 1985. MR0800252

[30]   H. Furstenberg. Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. d’Analyse Math., 31:204–256, 1977. MR0498471

[31]   H. Furstenberg. Recurrence in Ergodic Theory and Combinatorial Number Theory. Princeton University Press, Princeton, 1981. MR0603625

[32]   H. Furstenberg and Y. Katznelson. An ergodic Szemerédi Theorem for commuting transformations. J. d’Analyse Math., 34:275–291, 1978. MR0531279

[33]   H. Furstenberg and Y. Katznelson. An ergodic Szemerédi theorem for IP-systems and combinatorial theory. J. d’Analyse Math., 45:117–168, 1985. MR0833409

[34]   H. Gaifman. Concerning measures in first-order calculi. Israel J. Math., 2:1–18, 1964. MR0175755

[35]   E. Glasner. Ergodic Theory via Joinings. American Mathematical Society, Providence, 2003. MR1958753

[36]   W. T. Gowers. Hypergraph regularity and the multidimensional Szemerédi Theorem. preprint.

[37]   W. T. Gowers. A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 11(3):465–588, 2001. MR1844079

[38]   W. T. Gowers. Quasirandomness, counting and regularity for 3-uniform hypergraphs. Combin. Probab. Comput., 15(1-2):143–184, 2006. MR2195580

[39]   M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Birkhäuser, Boston, 1999. MR1699320

[40]   E. Hewitt and L. J. Savage. Symmetric measures on Cartesian products. Trans. Amer. Math. Soc., 80:470–501, 1955. MR0076206

[41]   D. N. Hoover. Relations on probability spaces and arrays of random variables. 1979.

[42]   D. N. Hoover. Row-columns exchangeability and a generalized model for exchangeability. In Exchangeability in probability and statistics (Rome, 1981), pages 281–291, Amsterdam, 1982. North-Holland. MR0675982

[43]   B. Host and B. Kra. Nonconventional ergodic averages and nilmanifolds. Ann. Math., 161(1):397–488, 2005. MR2150389

[44]   O. Kallenberg. Symmetries on random arrays and set-indexed processes. J. Theoret. Probab., 5(4):727–765, 1992. MR1182678

[45]   O. Kallenberg. Foundations of modern probability. Probability and its Applications (New York). Springer-Verlag, New York, second edition, 2002. MR1876169

[46]   O. Kallenberg. Probabilistic symmetries and invariance principles. Probability and its Applications (New York). Springer, New York, 2005. MR2161313

[47]   J. F. C. Kingman. The representation of partition structures. J. London Math. Soc. (2), 18(2):374–380, 1978. MR0509954

[48]   J. F. C. Kingman. Uses of exchangeability. Ann. Probability, 6(2):183–197, 1978. MR0494344

[49]   R. Kopperman. Model Theory and its Applications. Allyn and Bacon, Boston, 1972. MR0363873

[50]   A. V. Kostochka. A class of constructions for Turán’s (3,4)-problem. Combinatorica, 2:187–192, 1982. MR0685045

[51]   P. H. Krauss. Representation of symmetric probability models. J. Symbolic Logic, 34:183–193, 1969. MR0275482

[52]   L. Lovász and B. Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B, 96(6):933–957, 2006. MR2274085

[53]   B. Nagle, V. Rödl, and M. Schacht. The counting lemma for regular k-uniform hypergraphs. Random Structures and Algorithms, to appear. MR2198495

[54]   A. Razborov. Flag Algebras. J. Symbolic Logic, 72(4):1239–1282, 2007. MR2371204

[55]   A. Razborov. On the minimal density of triangles in graphs. preprint; available online at http://www.mi.ras.ru/~razborov/triangles.pdf, 2007.

[56]   V. Rödl and M. Schacht. Generalizations of the removal lemma. preprint, available online at http://www.informatik.hu-berlin.de/ ~schacht/pub/preprints/gen_removal.pdf.

[57]   R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252–271, 1996. MR1379300

[58]   C. Ryll-Nardzewski. On stationary sequences of random variables and the de finetti’s equivalence. Colloq. Math., 4:149–156, 1957. MR0088823

[59]   O. Schramm. Hyperfinite graph limits. preprint, available online at arXiv.org: math.CO/0711.3808, 2007. MR2334202

[60]   A. Sidorenko. What We Know and What We Do not Know about Turán Numbers. Graphs and Combinatorics, 11:179–199, 1995. MR1341481

[61]   E. Szemerédi. On sets of integers containing no k elements in arithmetic progression. Acta Arith., 27:199–245, 1975. MR0369312

[62]   T. Tao. A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma. J. d’Analyse Mathematique. to appear; available online at arXiv.org: math.CO/0602037. MR2373263

[63]   T. Tao. A quantitative ergodic theory proof of Szemerédi’s theorem. Electron. J. Combin., 13(1):Research Paper 99, 49 pp. (electronic), 2006. MR2274314

[64]   T. Tao and V. Vu. Additive combinatorics. Cambridge University Press, Cambridge, 2006. MR2289012

[65]   P. Wojtaszczyk. Banach spaces for analysts. Cambridge University Press, Cambridge, 1991. MR1144277

[66]   K. Yosida. Functional analysis. Classics in Mathematics. Springer-Verlag, Berlin, 1995. Reprint of the sixth (1980) edition. MR1336382

[67]   T. Ziegler. Universal characteristic factors and Furstenberg averages. J. Amer. Math. Soc., 20(1):53–97 (electronic), 2007. MR2257397

[68]   R. J. Zimmer. Ergodic actions with generalized discrete spectrum. Illinois J. Math., 20(4):555–588, 1976. MR0414832

[69]   R. J. Zimmer. Extensions of ergodic group actions. Illinois J. Math., 20(3):373–409, 1976. MR0409770




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787