Probability spaces over graphs: which area has focus on them?

349 Views Asked by At

Suppose a simple graph $G$. Now consider probability space $G(v;p)$ where $0\leq p\leq 1$ and $v$ vertices. I want to calculate globally-determined properties of $G(v;p)$ such as connectivity and expected value of indicator function $$\mathbb E_{p\sim [0,1]^n}(\phi(G))$$ in terms of st-connectedness where $p$ follows let say uniform distribution.

I want to understand which area investigates such structures. Extremal graph theory? Probabilistic Method? Random Graphs? Or some other?

Which area has a focus on probability spaces over graphs?

2

There are 2 best solutions below

4
On BEST ANSWER

For the model defined in the following way: Fix some graph $G$. For any $p \in [0,1]$, each vertex $v$ in $G$ is in the random induced subgraph with probability $p$ independent of other vertices.

This model is an instance of site percolation. Two popular introductory textbooks to Percolation Theory are Percolation by Bela Bollobás and Oliver Riordan and Percolation by Geoffrey Grimmett.

0
On

I start the thread with an observation:

  1. The Probabilistic Method book by Noga Alon has a treament of random graphs on page 155 where they calculate the expected value and the threshold function for graph-theoretic property such as connectedness