Understading a random graph process

Question

Let $P$ be a graph property that is preserved by the removal of edges.

Let $n \in \Bbb N$ be fixed. We give a construction of Random maximal P-graph, denoted $\textbf{M}_n(P)$, as follows :

1. Set $E(0)=\emptyset$.
2. For each edge $e$ of complete graph $K_n$ on $n$ vertices, let $e$ appear in $E(t)$ independently at exponential rate $\frac 1{1-t}$, for $t \in [0,1)$ provided that property $P$ is not destroyed. Multiple occurrences of an edge are ignored.
3. $\textbf{M}_n(P)=\langle V,E(1) \rangle$.

I am reading a paper by Erdős, Suen, and Winkler which, I've cited below. I have some questions regarding the above-mentioned construction:

• What does it mean that $e$ appears in $E(t)$ independently at exponential rate $\frac 1{1-t}$?
• Does it mean that this process follows an exponential distribution with the varying parameter $\lambda = \frac 1{1-t}$? i.e., do we have probability density function "$F(x)=\lambda e^{-\lambda x}, \;x \ge 0$" here with $\lambda = \frac 1 {1-t}$?
• How to mathematically express/write this process in terms of some probability space and random variable(s) and distributions?

Authors further write that :

Since the probability that a particular edge $e$ has not appeared by time $t$ is $1-t$, $\langle V, E(t) \rangle$ is the classic random graph $G_{n,t}$ of Erdős and Renyi when $P$ is the "improper" property possessed by all graphs.

I feel the first line of this paragraph, namely, "Since the probability that a particular edge $e$ has not appeared by time $t$ is $1-t$..." helps describe the construction, but I am not able to see it correctly.

Erdős, Paul; Suen, Stephen; Winkler, Peter, On the size of a random maximal graph, Random Struct. Algorithms 6, No. 2-3, 309-318 (1995). ZBL0820.05054.

Answer 1

I would take this to mean that an edge that hasn't appeared yet appears in the time interval $[t,t+\mathrm dt]$ with probability $\frac{\mathrm dt}{1-t}$, provided that property $P$ is not destroyed. Then the probability not to appear by time $t$ in the graph for the “improper” property is

$$ \exp\left(-\int_0^t\frac1{1-\tau}\mathrm d\tau\right)=\exp(\log(1-t))=1-t\;. $$

One might think that a simpler way to describe this would be to say that the potential appearance time of each edge is independently uniformly distributed over $[0,1]$, and the edge only appears at that time provided that property $P$ is not destroyed. However, the difference is that in this process the edge would only have one chance to appear, whereas in the process described it might be prevented from appearing at some time but then appear later if this no longer destroys property $P$. The divergence in the appearance rate ensures that the resulting graph is maximal with respect to property $P$: If an edge becomes admissible (with respect to property $P$) at time $\tau_0$ (possibly shortly before $t=1$), the probability that it will then not appear by time $t$ is

$$ \exp\left(-\int_{\tau_0}^t\frac1{1-\tau}\mathrm d\tau\right)=\exp(\log(1-t)-\log(1-\tau_0))=\frac{1-t}{1-\tau_0}\;, $$

so this is still $0$ at $t=1$.