×

On families of weakly dependent random variables. (English) Zbl 1238.05250

Nawrocki, Marek (ed.) et al., Marcinkiewicz centenary volume. Proceedings of the Józef Marcinkiewicz centenary conference, June 28–July 2, 2010. Warszawa: Polish Academy of Sciences, Institute of Mathematics (ISBN 978-83-86806-14-0/pbk). Banach Center Publications 95, 123-132 (2011).
Summary: 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.
For the entire collection see [Zbl 1234.00021].

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C65 Hypergraphs
11B25 Arithmetic progressions
05C35 Extremal problems in graph theory
60C99 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI