Videos

Maximal stream, minimal cutset and maximal flow in d-dimensional first passage percolation

Presenter
January 12, 2012
Keywords:
  • lattice theory
  • lattice models in mechanics
  • SLE
  • graph theory
  • graph theory algorithms
  • min cut/max flow
  • percolation
  • porous media
MSC:
  • 05C85
  • 60K35
  • 60J65
  • 60J67
  • 60Jxx
  • 60-xx
  • 82-xx
  • 06-xx
  • 76Sxx
  • 76S05
Abstract
We consider the standard first passage percolation model in the rescaled graph Z^d/n for d ≥ 2. We interpret it as a model of porous medium: the edges of the graph are small tubes, to which we associate a family of i.i.d. random capacities. Let Ω be a domain of Rd and denote by Γ its boundary. Let Γ1 and Γ2 be two disjoint open subsets of Γ, representing the parts of Γ through which some water can enter and escape from Ω. A law of large numbers for the maximal flow from Γ1 to Γ2 in Ω in Z^d/n, when n goes to infinity, is already known. We investigate here the asymptotic behaviour of a maximal stream and a minimal cutset. A maximal stream is a vector measure μ max that describes how the maximal amount of fluid can circulate through Ω. Under conditions on the regularity of the domain and on the law of the capacities of the edges, we prove that a.s. the sequence (μ max) converges weakly, when n goes to infinity, to the set of the solutions of a continuous non-random problem of maximal stream in an anisotropic network. A minimal cutset is a set of edges whose capacities restrict the flow. It can been seen as the boundary of a set Emin that separates Γ1 from Γ2 in Ω and whose random capacity is minimal. Under the same conditions, we prove that a.s. the sequence (Emin) converges for the topology L^1, when n goes to infinity, towards the set of the solutions of a continuous non-random problem of minimal cutset. We deduce from this a continuous non-random max-flow min-cut theorem, and a new proof of the law of large numbers for the maximal flow.
Supplementary Materials