Infinite paths in random graphs (some intersection lemmas in measure theory)

Joint work with A. Berarducci and M. Novaga

Some existence problems concerning subsequences with special properties, in a context of dynamical systems, ask for special intersection lemmas in measure theory. The archetype of this situation is the recurrence theorem of Poincare', and the Borel-Cantelli lemma. I will discuss some of these intersection problem. For instance, in the simplest form, we have:

PROBLEM. Let ${X_ij}$ be a double sequence of masurable subsets in a probability space Omega, with indices over all pairs $i0$. Is there an increasing sequence of numbers $i_0$

These problems may be restated as percolation problems on infinite random graphs. In particular, given the parameter $\lambda$, we look for sharp estimates on the probability of percolation, that is, for instance, in the above mentioned example, estimates on the measure of the event:

${x \in \Omega$: there exists a sequence $i_0<..$ such that $ x \in X_{i_1,i_2} \cap X_{i_2,i_3} \cap X_{i_3,i_4}....}$.

The computation is made possible after a reduction to a suitable variational problem. While doing this reduction, one is naturally lead to employ various mathematical theories : Ramsey theory; de Finetti's exchangeability theory and its more recent extensions (Aldous-Hoover Kallenberg); transfinite ordinals; elementary ergodic theory.