Percolation theory describes the behavior of connected clusters in a random graph.

learn more… | top users | synonyms

0
votes
0answers
15 views

Condition for global cascade

Assume a unidirectional, unweighted network generated according to a degree distribution. Each node is given a value between 0 and 1 called threshold $\phi$. We topple some nodes, the neighbours will ...
1
vote
2answers
45 views

Probability $u, v$ are connected in a random graph model

There is a random graph problem. Given an undirected graph $G(V,E)$ associated with $p_{uv}$ to denote the probability there is an edge between $u$ and $v$ ($p_{uv}$ are independent, maybe different ...
2
votes
0answers
20 views

“Chemists triple point” in percolation theory

This is a vague question asking about the existence of a mathematical object, instead of properties of a well defined one. I am sorry if this is not the correct forum. I know if you have a random ...
3
votes
1answer
39 views

Site percolation model that cannot be obtained from a bond percolation model

It is easy to obtain a site percolation model from a bond percolation model on a graph $G$ using the covering graph $G_c$ of $G$. I wondered if one can obtain any site percolation model from any site ...
0
votes
1answer
18 views

Percolation events

Consider bond percolation on $\mathbb{Z}^d$. How can we prove that the set of configurations $A = \{ \text{there exist an infinite open cluster} \}$ is an event, i.e. that it belongs to the cyllinder ...
0
votes
0answers
11 views

Is it possible to construct graphs with any critical bond percolation probability?

Given some probability $p\in[0,1]$ is it possible to construct a graph $(G,V)$ with critical bond percolation probability $p_c = p$? I know for example that I can get $\frac{1}{m}$ for any natural ...
0
votes
0answers
46 views

Exponential decay

During my study of percolation I came across exponential decay and there are some parts I do not understand about this. The definition of exponential decay is as follows: $f(t)$ decays ...
0
votes
1answer
43 views

Probability on Graphs. Percolation.

I am studying the book Probability on Graphs by Grimett. Grimett tells us that $\mu_1 \leq_{st} \mu_2$ if and only if $\mu_1(f)\leq\mu_2(f)$ for all increasing functions $f:\Omega\to \mathbb{R}$. I ...
1
vote
0answers
30 views

Infrared bound and mean field theory in percolation theory

I have seen various references to the phrases "infrared bound" and "mean field theory", together or separately in the context of various lattice models. (Percolation, Ising Model, Interacting Particle ...
0
votes
1answer
15 views

Stochastic domination preserved by dilution?

Consider an at most countable set $S$ and the corresponding bit space $\{0, 1\}^S$ that is often considered in percolation, interacting particle systems, and other lattice models. Suppose that $\le$ ...
0
votes
0answers
36 views

How do you use renormalization techniques to get the critical exponent for percolation strength?

I've read this and this. The percolation strength, or $P(p) \sim |p-p_c|^{\beta}$, where $p_c$ is the critical probability, is the probability that an arbitrary site in a lattice is part of an ...
1
vote
1answer
30 views

$k$ points of contact for percolation

In Grimmett's book on percolation near the beginning of Ch. 7, he summarizes the plan of proof of the result on percolation of slabs. We are in $\mathbb{Z}^d, d\ge2$, with his usual notation that ...
1
vote
1answer
49 views

What may be the number of connected components of this randomly generated topological space?

I hope there exists some answer to this but I am not very good in probability so i do not know how to tackle this problem. It's contemporary-art related so it might not have a good answer. ...
1
vote
2answers
64 views

Translation invariant event in percolation theory in $\mathbb{Z}^d$

At my probability theory proseminar I had a speech about the percolation theory and one of the topics I presented was the uniqueness of an infinite open cluster in Bernoulli bond percolation in ...
0
votes
0answers
97 views

Bond percolation probability on a Bethe lattice

I derived the bond-percolation probability for a Bethe lattice and my result disagrees with a seemingly reputable reference by Albert & Barabasi (see below). I would be happy if somebody could ...
1
vote
1answer
62 views

Percolation over the integers [closed]

Imagine a simple undirected graph with a countably infinite number of vertices, each labeled with an unique integer $v \in \mathbb{Z}$. Connect the vertices by edges randomly such that Each vertex ...
4
votes
2answers
135 views

amenable groups versus amenable graphs

In operator algebras, one is often concerned with amenable groups, defined by one of many equivalent conditions. http://en.wikipedia.org/wiki/Amenable_group#Equivalent_conditions_for_amenability In ...
0
votes
1answer
37 views

Generalized percolation problem

Consider a simple site percolation problem on, for example, a 2D square lattice. Each vertex is randomly either there or not with some probability. If two neighbouring vertices are present, then the ...
6
votes
0answers
60 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
3
votes
1answer
81 views

Books on random permutations

I'm looking for books or introductory/expository articles about random permutations, in particular with regards to their cycle structure. EDIT: I forgot to mention that I'm especially interested in ...
0
votes
0answers
73 views

How to calculate the critical density estimation for “continuum” percolation model in “3D space” when we have “spatial correlation”?

I want to approximately estimate the critical density (lower bound for density) of balls in a cube to make sure that the upper and lower surfaces of the cube will be connected to each other through ...
0
votes
0answers
75 views

First-hitting probability for the 2D critical site percolation on triangular lattice

Consider critical site percolation on the triangular lattice with mesh-size $\delta$. Let $D$ be the domain $H\backslash[0;i]$ where $H$ is the complex upper half plane. Compute the probability $$ ...
1
vote
0answers
30 views

Reliability polynomial of Cartesian produt of graphs

The all-terminal reliability $R(p)$ of a graph is the probability that the graph remains connected after edges fail independently with probability $p$. Similar the two-terminal reliability ...
0
votes
1answer
108 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
20
votes
2answers
482 views

The Gaussian moat problem and its extension to other rings in $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$

One of my favourite open problems in number theory, an area in which I enjoy only as a hobbyist, is the Gaussian moat problem, namely "Is it possible to walk to infinity in $\mathbb{C}$, taking ...
1
vote
0answers
83 views

Percolation in a finite, 2D rectangular grid

Images: I'd like some hints to the ??? pointed out as well as how to approach the case in which the X,Y are opposite corners. P.S. This is a problem which I came up with after a conversation with ...
0
votes
1answer
108 views

Total number of nodes in critical Galton-Watson process

Consider the following critical Galton-Watson process: initially there is a population of $Z(0) = z_0$. The distribution of children for each node follows a binomial law, with maximum value $d$; i.e. ...
1
vote
0answers
62 views

The probability that two adjacent vertices are connected with percolation probability $p = 1/2$.

I realise there is already a question on this matter, but I wasn't entirely satisfied with the answer given so that's why I am opening a new question. So the problem is to find the probability that ...
20
votes
1answer
478 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
6
votes
1answer
207 views

Colored path in a randomly colored grid

A friend of mine asked this question a while ago which I couldn't find any appropriate answer for it. I'd appreciate any comment or help. If one colors each unit square with black/white of an $m ...
14
votes
0answers
166 views

Size of connected regions on a randomly-colored infinite chessboard

Consider an infinite chessboard where each square is colored white with probability $p$ and black with probability $1-p$. Suppose without loss of generality that the square at $(0,0)$ is white. We ...
7
votes
0answers
132 views

Percolation and number of phases in the 2D Ising model.

Update. As my previous figure had conceptual mistakes I decided to change the picture to another, more instructive After a long time I came back to try to understand an article on the Ising ...
1
vote
0answers
141 views

A spaceship travelling to infinity while avoiding star collisions

Consider placing countably infinitely many points labeled $S_i$ randomly over $\mathbb{R}^2$, with asymptotic density points/area $µ$. Then, what is the largest $r$ such that we can find a a ...
1
vote
1answer
393 views

How is percolation defined and measured in social networks?

From the wikipedia article on percolation it appears that the theory is applicable to graphs in general, and this presentation describes the theory nicely. This review article on complex networks ...
11
votes
2answers
287 views

Edge percolation on $\mathbb{Z}^2$: probability that two neighbouring vertices are connected?

I'm considering edge percolation on $\mathbb{Z}^2$ with parameter $p$, so that edges are present with probability $p$. Is it known how to express the probability $P(p)$ that $(0,0)$ is in the same ...
3
votes
0answers
83 views

2-dimensional percolation and a random graph

Imagine turning the square grid defined by $\mathbb{N}^2$ in the plane into a directed graph. The vertices are $\mathbb{N}^2$ and for each vertex $(x,y)$, there is an edge pointing from it to $(x+1, ...
9
votes
0answers
159 views

Take an m x n grid, and in each box pick two opposite corners at random to connect. What can be said about the resulting pattern?

Inspired by the upcoming book 10 PRINT CHR$(205.5+RND(1)); : GOTO 10 by Nick Montfort et al., whose title derives from this particular example of emergent behavior. Here's an example: (Note that ...
3
votes
0answers
347 views

Does Kolmogorov 0-1 law apply to every translation invariant event?

Let $\Lambda$ be a lattice in $\mathbb{R}^d$, $d \ge 2$, thought of as an infinite graph. In percolation theory we consider properties random subgraphs of $\Lambda$. In site percolation $\Lambda^s_p$ ...
3
votes
0answers
99 views

percolation - number of cycles around the origin

I try to study Percolation Theory by "A mini course on percolation theory" of Jeffrey E. Steif. I am very curios about Exercise 2.4. Show that the number of cycles around the origin of length n is ...
2
votes
1answer
235 views

Percolation theory BK inequality

Let $X_1,\cdots X_n$ i.i.d bernoulli(p) r'v's Let $A = \sum_{i=1}^nX_i \geq l$, and $B= \sum_{i=1}^n X_i \geq k$ Then $A \circ B = \sum_{i=1}^nX_i \geq l+k$ (disjoint occurance of A, B) Im ...
1
vote
0answers
144 views

Branching process question

(Cross-posted from mathoverflow Q 93609) I am trying to analyze the following branching process. We start with a root (level 0) node. Each surviving node has two children, each of which may or may ...
1
vote
1answer
410 views

Translation Invariant Random Variable (Percolation)

I'm currently studying the uniqueness of the infinite cluster in supercritical percolation. In the proof the rv $N$ counts the number of infinite clusters on the infinite 2-D square lattice. The claim ...
2
votes
0answers
74 views

Percolation and hopping, has it been described?

This ultimately relates to a physics question, but It wasn't getting any answers, on physics.stackexchange. As it crosses the boundaries of each subject I was advised to post it here: Has a system ...
3
votes
0answers
282 views

2d Brownian motion hitting a point

Let $\Omega\subset \mathbb C$ be a simply connected domain, $\tau = \exp(2\pi\mathrm i/3)$ and $a(\alpha),a(\tau\alpha),a(\tau^2\alpha)$ are some accessible points of $\Omega$. In this paper by S. ...
21
votes
1answer
734 views

How to create mazes on the hyperbolic plane?

I'm interested in building maze-like structures on the [5, 4] tiling of the hyperbolic plane, where by maze-like I mean something akin to a spanning tree of the underlying lattice: a subgraph of the ...