On families of weakly dependent random variables
Volume 95 / 2011
Abstract
Let $\mathcal{G}^{(k)}_n$ be a family of random independent $k$-element subsets of $[n]=\{1,2,\dots,n\}$ and let $\mathcal H(\mathcal{G}^{(k)}_n,\ell)=\mathcal H_n^{(k)}(\ell)$ denote a family of $\ell$-element subsets of $[n]$ such that the event that $S$ belongs to $\mathcal H_n^{(k)}(\ell)$ depends only on the edges of $\mathcal{G}^{(k)}_n$ contained in $S$. Then, the edges of $\mathcal H_n^{(k)}(\ell)$ are `weakly dependent', say, the events that two given subsets $S$ and $T$ are in $\mathcal H_n^{(k)}(\ell)$ are independent for vast majority of pairs $S$ and $T$. In the paper we present some results on the structure of weakly dependent families of subsets obtained in this way. We also list some questions which, despite the progress which has been made for the last few years, remain to puzzle researchers who work in the area of probabilistic combinatorics.
