Determining sample space and random variable for a construction of random maximal P-graph

Question

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

We give a construction of a Random maximal $P-$graph, denoted $\textbf{M}_n(P)$, as follows:

1. Fix $V=\{1,2,...,n\}$, $K_n=\text{complete graph on vertex set} \; V$, $E^0=\text{initial edge set}=\emptyset.$
2. For each $i \ge 0$, if $F^i=\{e \in K_n: \text{The graph} \;\langle V, E^i \cup \{e\} \rangle \; \text{satisfies} \; P\}\neq \emptyset$, then $E^{i+1}=E^i \cup \{e\}$ where $e$ is chosen randomly and uniformly from $F^i$.
3. If $F^i=\emptyset$, then $\textbf{M}_n(P)=\langle V,E^i\rangle,$ and the construction is complete.

I am currently reading this paper (also cited below), in which the above construction appears. I want to understand the underlying sample space, probability measure, and the description of $\textbf{M}_n(P)$, which I think, is a random variable. But if it is a random variable, then what is its sample space and what is its co-domain? Is the process of construction a Markov chain? I am confused here.

I have never studied stochastic processes before, but when I came across the definition of the same, I felt that it might be the way here but I am not able to precisely write the things down.

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

The sample space is the set of subgraphs of $K_n$ (though some of these may have probability zero). More precisely, $\mathbf{M}_n(P)$ is concentrated on subgraphs of $K_n$ that satisfy property $P$ and to which no edge can be added while preserving property $P$. The process has not been completely described, in that it is not specified if or how the random choice at time $i+1$ is influenced by the previous random choices. However, I think it's reasonable to assume the choices are independent (i.e., enumerate the elements of $F^i$, choose a random number $N_i$ between $1$ and $|F^i|$ at time $i$ independent of all past random choices, and let $e$ be the $N_i$th element of $F^i$).

The construction is not a Markov process, as illustrated below.

Consider an example where the property $P$ is "there exists an isolated vertex" and $V=\{1,2,3,4\}$. We have:

• $E^0=\emptyset$
• $F^0=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$
• $e=$ a random element from $F^0$, say $e=\{1,3\}$
• $E^1 =\{\{1,3\}\}$
• $F^1 = \{\{1,2\},\{1,4\},\{2,3\},\{3,4\}\}$. Note $\{1,3\}$ is removed because it has already been chosen, and $\{2,4\}$ is removed because choosing it would leave no isolated vertices.
• $e = $ a random element from $F^1$, say $e=\{2,3\}$
• $E^2 = \{\{1,3\},\{2,3\}\}$. Note at this point $4$ is the only vertex that can be isolated in $\mathbf{M}_n(P)$. This is determined by both of our previous edge choices, not just the most recent choice, hence the process is not Markov.
• $F^2 =\{\{1,3\}\}$ since this is the only edge not yet in the random graph that is not incident to $4$.
• $e=$ a random element from $F^2$, i.e., $e=\{1,2\}$.
• $E^3 = \{\{1,2\},\{1,3\},\{2,3\}\}$
• $F^3 = \emptyset$ and the construction terminates.

In this example you should be able to convince yourself that $\mathbf{M}_n(P)$ is uniform on the triangle subgraphs of $K_4$. That is, for any given triangle subgraph, with probability $\frac{1}{4}$ the construction ends in that subgraph. Note that $|F^0|=6$, $|F^1|=4$, and $|F^3|=1$ regardless of the choices we make in this example. So if edges $e_1$, $e_2$, and $e_3$ form a triangle subgraph, then they are chosen with probability $\frac{1}{6}\cdot \frac{1}{4}\cdot 3!=\frac{1}{4}$ (since it doesn't matter which order we choose the edges).

In general it will be much more complicated to calculate the probability distribution of $\mathbf{M}_n(P)$. In my opinion it is best understood as being built by a random process over time.