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?

  • 1
    $\begingroup$ Do you mean that you have a fixed graph $G$ and a probability distribution on the vertices, and you want to study properties of these two? I'm not sure I understand how this should work, in that I don't see how the probability links to the graph theory. With random graphs, the edges which are present are based on some probability distribution, so there is a clear connection between the two. $\endgroup$ – Ian Apr 24 '16 at 19:16
  • $\begingroup$ Thank you for observation. $ST$-cut can be defined in terms of edges or in terms of vertices: a vertex-cut disconnects vertices $S$ and $T$ where the vertex-cut has a corresponding edge-cut, if $v$ in vertex-cut, then edge-cut contains all edges $\{u,v\}$ where $u$ is adjacent to $v$. Now if $p_{vertex-v}\sim\mathbb{Pr}_1$, then $p_{edge-u-v}\sim \mathbb {Pr}_1$. So here random graph with some probability distribution $\mathbb{Pr}_1$. $\endgroup$ – hhh Apr 24 '16 at 20:30
  • $\begingroup$ I'm confused on the model that you want. Is it one of these two? Fix some graph $G$. First model: For each edge $e$ in $G$, we include this edge in our random (sub)graph with probability $p$ independent of other potential edges. Second model: For each vertex $v$ in $G$, we include this vertex in our random induced (sub)graph with probability $p$ independent of other potential vertices. $\endgroup$ – D Poole Apr 26 '16 at 14:08
  • $\begingroup$ @DPoole the second is the model. $\endgroup$ – hhh Apr 26 '16 at 16:25

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.

  • $\begingroup$ My teacher said that site percolation is not an example of this "Random graph $G(n,p)$ is a probability space over graphs of order $n$ determined by $P[{i,j}\in E(G)]=p$ where $i$ and $j$ are distinct elements of the vertex set $V(G)$. The events $\{i,j\}\in G$ are independent." -- can you understand the meaning? Is the formulation Erdös-Renui or some other random graph model? $\endgroup$ – hhh Jul 10 '16 at 14:52
  • 1
    $\begingroup$ That model is different than the one described in the comments to the original post. In those comments, you said that the vertices were randomly chosen, not the edges. If you take $K_n$, and for each edge you keep it with probability $p$ and delete it with probability $1-p$, then you have the random Erdős–Rényi graph $G(n,p)$. Now if you take $K_n$ (or any other graph), and for each vertex, you keep it with probability $p$ and delete it with probability $1-p$, then you have what is commonly called site percolation. $\endgroup$ – D Poole Jul 11 '16 at 14:38
  • $\begingroup$ So bond percolation is an example of Erdös-Renyi graph $G(n,p)$ where edges removed with probability $p$? Can I mark the probability space over graph $G$ with $G(n,p)$ for site percolation? Or is $G(n,p)$ notation preserved for only the Erdos-Renyi where edges removed with probability $p$ (bond percolation?)? $\endgroup$ – hhh Jul 11 '16 at 15:45
  • 1
    $\begingroup$ I would avoid using $G(n,p)$ unless you mean the Erdős–Rényi random graph. Although you can think of $G(n,p)$ as looking into bond percolation on $K_n$, the types of questions in bond percolation and random graphs are typically different. In bond percolation, the underlying base graph is typically a lattice or some other infinite graph with symmetry rather than $K_n$. Also, the notation for site percolation is usually this: the base graph is $\Lambda$ and the random (sub)graph is denoted $\Lambda_p^s$ or just $\Lambda_p$. The $s$ denotes "site". $\endgroup$ – D Poole Jul 11 '16 at 22:45

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.