# How to determine a specific graph process is Markovian or not ?

Say, here is a min-degree graph process, which starts with G_0 = the complement of K_n. Given G_t, choose a vertex u of minimum degree in G_t u.a.r., then a vertex v not adjacent to u in G_t u.a.r. Put A_{t+1}, which is the edge added during period t+1. The process finishes with the complete graph. Question : Is this graph process Markovian ?

Thanks very much !

-
3 questions: 1) are you asking about $G_t$ or about $A_t$? 2)what is u.a.r.? 3) is this homework? –  Ori Gurel-Gurevich Jun 3 '11 at 1:17
1. G_t 2. uniformly at random 3.not homework, just because I am not familiar with Markovian Thanks for your comments –  Nana Li Jun 9 '11 at 19:42

Let me check that I understand you correctly.

Let $Y(t)$ be the $n+1$-dimensional vector $Y(t) = \otimes_{i=0}^n Y^t_i$ where $Y^t_i$ represents the number of verticies with degree $i$ at time $t$. When time increases by $1$, add an edge at random.

So, $Y(0) = (n,0,0,\ldots,0)$, $Y(1) = (n-2,2,0,\ldots,0)$,

$Y(2) = (n-4,4,0,0,\ldots,0)$ if the new edge is not adjacent to the old edge, or $Y(2) = (n-3,2,1,0,\ldots,0)$ if the new edge is adjacent to the old edge.

At time $t$, the new edge is chosen at random by choosing one vertex of degree $i$ with probability $Y^t_i/(n - Y^t_n)$ and another of degree $j$ with probability $Y^t_j/(n - Y^t_n - 1)$ if $j\neq i$ and probability $(Y^t_j-1)/(n - Y^t_n-1)$ if $j=i$.

Assuming $j\neq i$ (a simple adjustment is necessary for the $i=j$ case), the probability moving from $Y(t)$ to $Y(t+1)$ where $Y^{t+1}_k = Y^t_k - 1$ and $Y^{t+1}_k = Y^t_k + 1$ for $k= i,j$ and $Y^{t+1}_k = Y^t_k$ for $k \neq i,j$ is therefore $$\frac{Y^t_i Y^t_j}{2(n - Y^t_n)(n - Y^t_n-1)}$$ Which only depends on the present state, and is independent of the history of the previous $t-1$ steps. Hence it is a Markov chain.

-

Sincerely sorry that I did not make it clear. I think I got the answer. Anyway, the question actually asks whether the vector process { Y_0,Y_1,...Y_{n-1} } is Markovian or not, where Y_{i}(t) is the number of vertices of degree i.

It goes like this, let $G_t$ be the evolving graph at time t, if the muinimum degree of $G_t$ is 0, then the process until now is Markovian, otherwise, when the minimum degree changes to bigger than 0, the graph process is not Markovian.

because there may be edges already present between vertices of degree k and other candicate vertices to join to. And it is essential to notices that it it the vector sequence { Y_{0}, Y_{1}, Y_{2},......Y_{n-1} } that we are considering. I made a mistake eariler.

Thanks very much !

-