Abstract
A classic result in probability theory known as de Finetti's theorem states that exchangeable random variables are equivalent to a mixture of distributions where each distribution is determined by an i.i.d. sequence of random variables (an "i.i.d. mix"). Motivated by a recent application and more generally by the relationship of local vs. global correlation in randomized rounding, we study weaker notions of exchangeability that still imply the conclusion of de Finetti's theorem. We say that a bivariate distribution rho is Grealizable for a graph G if there exists a joint distribution of random variables on the vertices such that the marginal distribution on each edge equals rho.
We first characterize completely the Grealizable distributions for all symmetric/arctransitive graphs G. Our main results are forms of de Finetti's theorem for general graphs, based on spectral properties. Let lambda_1(G) >= ... >= lambda_n(G) denote the eigenvalues of the adjacency matrix of G.
1. We prove that if rho is G_nrealizable for a sequence of graphs such that lambda_n(G_n) / lambda_1(G_n) tends to 0, then rho is described by a probability matrix that is positivesemidefinite. For random variables on domains of size D <= 4, this implies that rho must be an i.i.d. mix.
2. If rho is G_nrealizable for a sequence of (n,d,lambda)graphs G_n (dregular with all eigenvalues except for one bounded by lambda in absolute value) such that lambda(G_n) / d(G_n) tends to 0, then rho is an i.i.d. mix.
3. If rho is G_nrealizable for a sequence of directed graphs such that each of them is an arbitrary orientation of an (n,d,lambda)graph G_n, and lambda(G_n) / d(G_n) tends to 0, then rho is an i.i.d. mix.
BibTeX  Entry
@InProceedings{jayram_et_al:LIPIcs:2014:4737,
author = {T. S. Jayram and Jan Vondr{\'a}k},
title = {{Exchangeability and Realizability: De Finetti Theorems on Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {762778},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4737},
URN = {urn:nbn:de:0030drops47375},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.762},
annote = {Keywords: exchangeability, de Finetti’s Theorem, spectral graph theory, regularity lemma}
}
Keywords: 

exchangeability, de Finetti’s Theorem, spectral graph theory, regularity lemma 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) 
Issue Date: 

2014 
Date of publication: 

04.09.2014 